無線傳感器網(wǎng)絡(luò) 第10章 服務(wù)質(zhì)量

1、無線傳感器網(wǎng)絡(luò)技術(shù)無線傳感器網(wǎng)絡(luò)技術(shù)講義講義第九章、服務(wù)質(zhì)量保證內(nèi)容提要1.無線傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量概述 2.無線傳感器網(wǎng)絡(luò)感知QoS研究3.無線傳感器網(wǎng)絡(luò)傳輸QoS研究4.參考文獻(xiàn)內(nèi)容提要1.無線傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量概述 2.無線傳感器網(wǎng)絡(luò)感知QoS研究3.無線傳感器網(wǎng)絡(luò)傳輸QoS研究4.參考文獻(xiàn)無線傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量(QoS)概述 服務(wù)質(zhì)量（QoS）背景與概述服務(wù)質(zhì)量(QoS)定義服務(wù)質(zhì)量(QoS)支持機(jī)制 無線傳感器網(wǎng)絡(luò)QoS研究服務(wù)質(zhì)量（QoS）背景與概述 圖10-1簡單QoS模型網(wǎng)絡(luò)服務(wù)質(zhì)量指標(biāo) 可用性 ：當(dāng)用戶需要時(shí)網(wǎng)絡(luò)即能開始工作的時(shí)間百分比。 吞吐量：一定時(shí)間段內(nèi)對網(wǎng)絡(luò)流量的度量。

2、 時(shí)延變化：同一業(yè)務(wù)流中不同分組所呈現(xiàn)的時(shí)延不同 。 丟包率 ：是指網(wǎng)絡(luò)在傳輸過程中數(shù)據(jù)包丟失的比率。 服務(wù)質(zhì)量服務(wù)質(zhì)量(QoS)支持機(jī)制支持機(jī)制 Int-serv集成業(yè)務(wù) Diff-serv區(qū)分業(yè)務(wù) MPLS多協(xié)議標(biāo)簽交換 無線傳感器網(wǎng)絡(luò)(QoS)研究無線傳感器網(wǎng)絡(luò)自身特點(diǎn)使得傳統(tǒng)網(wǎng)絡(luò)的QoS支持機(jī)制不適用： 節(jié)點(diǎn)資源非常有限 負(fù)載不均衡 大量冗余節(jié)點(diǎn) 網(wǎng)絡(luò)異構(gòu)圖10-2 無線傳感器網(wǎng)絡(luò)參考體系結(jié)構(gòu)內(nèi)容提要1.無線傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量概述 2.無線傳感器網(wǎng)絡(luò)感知QoS研究3.無線傳感器網(wǎng)絡(luò)傳輸QoS研究4.參考文獻(xiàn)無線傳感器網(wǎng)絡(luò)覆蓋算法設(shè)計(jì)方式和目標(biāo)無線傳感器網(wǎng)絡(luò)覆蓋算法設(shè)計(jì)方式和目標(biāo)節(jié)點(diǎn)部署

3、方式網(wǎng)絡(luò)節(jié)能傳感與通信距離網(wǎng)絡(luò)可擴(kuò)展無線傳感器網(wǎng)絡(luò)覆蓋算法分類無線傳感器網(wǎng)絡(luò)覆蓋算法分類 節(jié)點(diǎn)部署方式分類節(jié)點(diǎn)部署方式分類確定性覆蓋確定性覆蓋隨機(jī)覆蓋隨機(jī)覆蓋 覆蓋目標(biāo)分類覆蓋目標(biāo)分類區(qū)域覆蓋區(qū)域覆蓋點(diǎn)覆蓋點(diǎn)覆蓋柵欄覆蓋柵欄覆蓋圖 10 4 區(qū)域覆蓋、點(diǎn)覆蓋與柵欄覆蓋區(qū)域覆蓋控制算法區(qū)域覆蓋控制算法-輪換活躍輪換活躍/休眠節(jié)點(diǎn)的覆蓋協(xié)議休眠節(jié)點(diǎn)的覆蓋協(xié)議需要解決的問題： （1）網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)如何判斷自應(yīng)該處于活動還是休眠狀態(tài)； （2）網(wǎng)絡(luò)中節(jié)點(diǎn)如何進(jìn)行狀態(tài)轉(zhuǎn)換。輪換活躍輪換活躍/休眠節(jié)點(diǎn)的覆蓋協(xié)議休眠節(jié)點(diǎn)的覆蓋協(xié)議-節(jié)點(diǎn)覆蓋休眠準(zhǔn)則圖10 5 節(jié)點(diǎn)覆蓋圖 輪換活躍/休眠節(jié)點(diǎn)的覆蓋協(xié)議-節(jié)點(diǎn)調(diào)

4、度機(jī)制節(jié)點(diǎn)調(diào)度機(jī)制采用周期輪換工作方法，每個(gè)周期包括： self-scheduling 階段：每個(gè)節(jié)點(diǎn)根據(jù)節(jié)點(diǎn)覆蓋休眠準(zhǔn)則，來判斷自己是否進(jìn)入休眠狀態(tài) 。 sensing階段： 執(zhí)行傳感操作輪換活躍/休眠節(jié)點(diǎn)的覆蓋協(xié)議-鄰居信息獲取 各節(jié)點(diǎn)在每一輪開始時(shí)向傳感半徑內(nèi)鄰居節(jié)點(diǎn)廣播位置通告消息PAM 其中包括節(jié)點(diǎn)ID和位置(若傳感半徑不同則包括發(fā)送節(jié)點(diǎn)傳感半徑)。輪換活躍/休眠節(jié)點(diǎn)的覆蓋協(xié)議-退避自調(diào)度在判斷節(jié)點(diǎn)是否可以休眠時(shí)，如果相鄰節(jié)點(diǎn)同時(shí)檢查到自身的傳感任務(wù)可由對方完成并同時(shí)進(jìn)入“休眠狀態(tài)”，就會出現(xiàn)如圖所示的“盲點(diǎn)”。 abcdefabcd圖10 6 網(wǎng)絡(luò)中出現(xiàn)的盲點(diǎn)連通傳感器覆蓋 在選取

5、網(wǎng)絡(luò)中哪些節(jié)點(diǎn)處于活動狀態(tài)時(shí)，需要考慮滿足以下兩個(gè)因素： (1)覆蓋：活動節(jié)點(diǎn)集合的傳感區(qū)域能夠覆蓋整個(gè)監(jiān)測區(qū)域；(2)連通：網(wǎng)絡(luò)活動節(jié)點(diǎn)集合中任意兩個(gè)節(jié)點(diǎn)都能夠互相通信，使得傳感節(jié)點(diǎn)采集的數(shù)據(jù)能夠被發(fā)回基站。 連通傳感器覆蓋 OGDC算法 定理定理1：假設(shè)在任何有限區(qū)域中，節(jié)點(diǎn)的數(shù)目有限。則保證區(qū)域被節(jié)點(diǎn)全覆蓋即網(wǎng)絡(luò)全連通的充要條件是節(jié)點(diǎn)通信半徑大于兩倍的傳感半徑。 定理定理2：假設(shè)傳感節(jié)點(diǎn)的傳感區(qū)域是以節(jié)點(diǎn)為中心的圓形區(qū)域，該區(qū)域相對待監(jiān)測區(qū)域小很多。多個(gè)傳感區(qū)域在其中相互相交。如果該區(qū)域中所有的交叉點(diǎn)都被覆蓋，則該待監(jiān)測區(qū)域也被完全覆蓋。 定理定理3：如果所有傳感節(jié)點(diǎn)的傳感半徑相等，并且

6、能夠完全覆蓋監(jiān)控區(qū)域。減少網(wǎng)絡(luò)中活動節(jié)點(diǎn)個(gè)數(shù)等效于減小所有節(jié)點(diǎn)傳感覆蓋區(qū)域的重疊。柵欄覆蓋控制算法柵欄覆蓋控制算法最壞與最佳情況覆蓋最壞與最佳情況覆蓋 最壞覆蓋是指如何在網(wǎng)絡(luò)中找到一條路徑，使得沿該路徑前進(jìn)的目標(biāo)被網(wǎng)絡(luò)中節(jié)點(diǎn)發(fā)現(xiàn)的概率最小。該路徑稱為最大突破路徑(maximal breach path)，即最大化該路徑上點(diǎn)到周圍最近傳感器的最小距離。 最佳覆蓋是指網(wǎng)絡(luò)中找到一條路徑，使得沿該路徑前進(jìn)的目標(biāo)被網(wǎng)絡(luò)中節(jié)點(diǎn)發(fā)現(xiàn)的概率最大。該路徑稱為最大支撐路徑(maximal support path)，即最小化路徑上的點(diǎn)到周圍最近傳感器的最大距離。 最壞覆蓋與最大突破路徑最壞覆蓋與最大突破路徑(1

7、) 基于各節(jié)點(diǎn)的位置產(chǎn)生網(wǎng)絡(luò)Voronoi圖;(2) 為Voronoi圖中每一條邊界賦一個(gè)權(quán)值。該值表示這條邊界到離他最近的傳感器節(jié)點(diǎn)的距離;(3) 利用二分查找法和寬度優(yōu)先查找算法來獲取最大突破路徑。圖 10 7最大突破路徑Voronoi圖 (c) (d)(a) (b)最壞覆蓋與最大突破路徑最壞覆蓋與最大突破路徑最佳覆蓋與最大支撐路徑最佳覆蓋與最大支撐路徑以Delaunay三角取代Voronoi圖作為幾何結(jié)構(gòu)。圖中每條邊的權(quán)值算法變?yōu)橛?jì)算該邊到周圍最近傳感器節(jié)點(diǎn)的最大距離。查找參數(shù)由突破權(quán)值變?yōu)橹螜?quán)值，查找網(wǎng)絡(luò)中支撐權(quán)值最小的邊 圖 10 8傳感器網(wǎng)絡(luò)Delaunay三角以及最大支撐路徑

8、最佳覆蓋與最大支撐路徑最佳覆蓋與最大支撐路徑暴露穿越暴露穿越問題(Exposure)：即觀察傳感區(qū)域內(nèi)目標(biāo)的平均期待能力，或一個(gè)傳感函數(shù)的積分，該積分值依賴于目標(biāo)移動原點(diǎn)至終點(diǎn)的路徑到傳感節(jié)點(diǎn)的距離。暴露穿越算法將連續(xù)問題域轉(zhuǎn)化為離散域應(yīng)用圖理論抽象利用Dijkstra的單源最短路徑算法(Single-Source-Shortest-Path algorithm)圖 10 9全節(jié)點(diǎn)強(qiáng)度模型下所獲得的最小暴露路徑。網(wǎng)格精度區(qū)別：n=8,m=1(左)；n=16,m=2(中)；n=32,m=8(右)。暴露穿越算法圖 10 16最近節(jié)點(diǎn)全節(jié)點(diǎn)強(qiáng)度模型下所獲得的最小暴露路徑。網(wǎng)格精度區(qū)別：n=8,m=1

9、(左)；n=16,m=2(中)；n=32,m=8(右)。暴露穿越算法內(nèi)容提要1.無線傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量概述 2.無線傳感器網(wǎng)絡(luò)感知QoS研究3.無線傳感器網(wǎng)絡(luò)傳輸QoS研究4.參考文獻(xiàn)無線傳感器網(wǎng)絡(luò)服務(wù)區(qū)分參數(shù) 數(shù)據(jù)包抵達(dá)概率(可靠性) ：高優(yōu)先級的數(shù)據(jù)包傳送至基站節(jié)點(diǎn)的概率更高。 時(shí)延：高優(yōu)先級的數(shù)據(jù)包抵達(dá)基站節(jié)點(diǎn)的時(shí)延要少于低優(yōu)先級數(shù)據(jù)包。 可靠數(shù)據(jù)傳輸造成數(shù)據(jù)包丟失的原因主要有三個(gè)方面： 無線傳感器網(wǎng)絡(luò)所使用的無線信道較之有線鏈路有更大的不穩(wěn)定性以及更高的誤碼率， 很容易受到周圍環(huán)境噪聲的影響造成數(shù)據(jù)包的丟失。另外在無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)的布撒密度非常高，不同節(jié)點(diǎn)在發(fā)送數(shù)據(jù)時(shí)極易發(fā)

10、生信道競爭沖突以及碰撞造成數(shù)據(jù)包丟失。 當(dāng)無線傳感器網(wǎng)絡(luò)中發(fā)生擁塞時(shí)，擁塞節(jié)點(diǎn)緩沖區(qū)溢出造成數(shù)據(jù)包丟失。接收節(jié)點(diǎn)因?yàn)閿?shù)據(jù)包到達(dá)過快來不及處理造成數(shù)據(jù)包丟失。差錯(cuò)避免可靠傳輸 ACK確認(rèn)重傳機(jī)制確認(rèn)重傳機(jī)制 數(shù)據(jù)包冗余傳輸機(jī)制數(shù)據(jù)包冗余傳輸機(jī)制 多路徑傳輸機(jī)制多路徑傳輸機(jī)制 FEC前向糾錯(cuò)碼機(jī)制前向糾錯(cuò)碼機(jī)制 單分組傳遞：ReInForm路由ReInForm方法是基于在多條路徑上發(fā)送數(shù)據(jù)包的多個(gè)拷貝來提高數(shù)據(jù)包傳輸可靠性。從數(shù)據(jù)源節(jié)點(diǎn)開始，根據(jù)數(shù)據(jù)傳輸可靠性、信道質(zhì)量以及傳感器節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的跳數(shù)，確定需要的傳輸路徑數(shù)目，以及下一跳節(jié)點(diǎn)數(shù)目和相應(yīng)的節(jié)點(diǎn)。鄰居節(jié)點(diǎn)在接收到數(shù)據(jù)源節(jié)點(diǎn)的數(shù)據(jù)后，將自己

11、視作數(shù)據(jù)源節(jié)點(diǎn)，重復(fù)上述數(shù)據(jù)源節(jié)點(diǎn)的選路過程。實(shí)現(xiàn)滿足可靠要求的數(shù)據(jù)傳輸。 圖 10 10ReInform所需傳送概率為70%時(shí)數(shù)據(jù)轉(zhuǎn)發(fā)舉例。(A)圖是源節(jié)點(diǎn)在鏈路差錯(cuò)率為0時(shí)傳遞1個(gè)數(shù)據(jù)包；(B)圖是源節(jié)點(diǎn)在鏈路差錯(cuò)率為0時(shí)傳遞10個(gè)數(shù)據(jù)包；(C)是源節(jié)點(diǎn)在鏈路差錯(cuò)率為30%時(shí)傳遞1個(gè)數(shù)據(jù)包(D)是源節(jié)點(diǎn)在鏈路差錯(cuò)率為30%時(shí)發(fā)送10個(gè)單分組 圖 10 11洪泛、單路徑轉(zhuǎn)發(fā)以及40%、70%可靠性要求的多路徑轉(zhuǎn)發(fā)在鏈路出錯(cuò)率增加時(shí)所能保證的可靠性比較 圖 10 12洪泛、單路徑轉(zhuǎn)發(fā)以及40%、70%可靠性要求的多路徑轉(zhuǎn)發(fā)在鏈路出錯(cuò)率增加時(shí)為保證可靠性所引發(fā)的開銷 數(shù)據(jù)塊傳輸:RMST 無線傳

12、感器網(wǎng)絡(luò)中，有時(shí)需要傳輸大量的數(shù)據(jù)。比如在傳送圖像、聲音等數(shù)據(jù)時(shí)，或者當(dāng)網(wǎng)絡(luò)需要重新配置，基站將新的代碼發(fā)送至節(jié)點(diǎn)。 相對于單數(shù)據(jù)包的可靠性傳輸，保證數(shù)據(jù)塊傳輸?shù)目煽啃詸C(jī)制有很大的不同。 數(shù)據(jù)塊傳輸:RMST Fred Stann等人認(rèn)為在無線傳感器網(wǎng)絡(luò)中，無線鏈路不穩(wěn)定及易受干擾的特點(diǎn)是造成網(wǎng)絡(luò)傳輸不可靠的主要原因. 除了在物理層實(shí)現(xiàn)高效的糾錯(cuò)碼之外，如何在MAC層、傳輸層以及應(yīng)用層提供可靠性是實(shí)現(xiàn)可靠傳輸?shù)闹匾ＷC。 在MAC層實(shí)現(xiàn)可靠性保證的重要性體現(xiàn)在，它除了能為傳輸層提供跳段之間的錯(cuò)誤恢復(fù)之外，還是實(shí)現(xiàn)路由發(fā)現(xiàn)及維持的保證。 數(shù)據(jù)塊傳輸:RMST圖10- 13每跳鏈路出錯(cuò)率為10%，

13、數(shù)據(jù)傳輸 40跳時(shí)，傳輸成功概率數(shù)據(jù)塊傳輸:RMST圖10-14數(shù)據(jù)傳輸6跳時(shí)，傳輸成功概率比較 數(shù)據(jù)塊傳輸:RMST 802.11中提供了數(shù)據(jù)包分片與重組的方法，但是并沒有提供傳輸可靠性保證。 而傳統(tǒng)有線網(wǎng)絡(luò)中的傳輸層TCP協(xié)議提供的傳輸可靠保證主要是為解決網(wǎng)絡(luò)擁塞問題而提出的，并不適用于無線網(wǎng)絡(luò)。 RMST提出了兩種傳輸層可靠性保證方法:端到端選擇請求NACK和跳段之間選擇請求NACK。 數(shù)據(jù)塊傳輸:RMSTl 端到端選擇請求NACK是當(dāng)基站節(jié)點(diǎn)發(fā)現(xiàn)接收的數(shù)據(jù)包有丟失或損壞時(shí)，沿著基站到源節(jié)點(diǎn)的反向增強(qiáng)路徑發(fā)送重傳請求。當(dāng)重傳請求到達(dá)源節(jié)點(diǎn)后，源節(jié)點(diǎn)將重傳所需數(shù)據(jù)。端到端選擇請求NACK方

14、法只需在基站和源節(jié)點(diǎn)緩存數(shù)據(jù)，中間節(jié)點(diǎn)無需緩存數(shù)據(jù)。l 跳段選擇請求NACK方法是在路由路徑上的每個(gè)節(jié)點(diǎn)都緩存數(shù)據(jù)，當(dāng)節(jié)點(diǎn)發(fā)現(xiàn)有數(shù)據(jù)包丟或損壞時(shí)直接向其上一跳節(jié)點(diǎn)發(fā)送重傳請求。擁塞控制 無線傳感器網(wǎng)絡(luò)大部分時(shí)間都處于零負(fù)載或輕負(fù)載，只有在異常事件發(fā)生時(shí)，網(wǎng)絡(luò)中才會突發(fā)性的產(chǎn)生較大的數(shù)據(jù)量。這些數(shù)據(jù)非常重要，需要在不影響系統(tǒng)性能的前提下可靠的傳送給基站。但是這種突發(fā)性的大數(shù)據(jù)量傳輸很容易導(dǎo)網(wǎng)絡(luò)不同程度擁塞的發(fā)生。 網(wǎng)絡(luò)吞吐量隨源速率的增加而減小. 節(jié)點(diǎn)數(shù)量越大，實(shí)際吞吐量減少的越大. CODA擁塞控制方案擁塞控制方案擁塞場景 :(1)節(jié)點(diǎn)密集分布的網(wǎng)絡(luò)中，當(dāng)有異常事件發(fā)生時(shí)，源節(jié)點(diǎn)會突發(fā)性產(chǎn)生大

15、量數(shù)據(jù)。在源節(jié)點(diǎn)附近(幾跳范圍內(nèi))形成持續(xù)擁塞區(qū)域。 (2)在節(jié)點(diǎn)分布稀疏并且源節(jié)點(diǎn)數(shù)據(jù)發(fā)送速率較低的網(wǎng)絡(luò)中，不會在源節(jié)點(diǎn)附近產(chǎn)生持續(xù)的擁塞，而可能在遠(yuǎn)離源節(jié)點(diǎn)的網(wǎng)絡(luò)區(qū)域中任意位置產(chǎn)生短暫的擁塞。 (3)在節(jié)點(diǎn)分布稀疏并且源節(jié)點(diǎn)數(shù)據(jù)發(fā)送速率較高的網(wǎng)絡(luò)中，有可能在網(wǎng)絡(luò)區(qū)域的任意位置發(fā)生短暫或持續(xù)的擁塞。 CODA擁塞控制方案擁塞控制方案1. 基于接收者的擁塞檢測；2. 開環(huán)跳段反向壓力信標(biāo)機(jī)制(open-loop hop-by-hop backpressure)；3. 閉環(huán)多源調(diào)整機(jī)制(closed-loop multi-source regulation) 。 CODA擁塞控制方案擁塞控制方案

16、-擁塞檢測 CODA將節(jié)點(diǎn)緩沖區(qū)管理方法與鏈路負(fù)載監(jiān)測方法二者相結(jié)合，提出了一個(gè)能量高效基于接收者的擁塞檢測方法。 在CODA中，只有當(dāng)節(jié)點(diǎn)緩沖區(qū)隊(duì)列不為空時(shí)，才啟動鏈路負(fù)載監(jiān)測。當(dāng)節(jié)點(diǎn)緩沖區(qū)隊(duì)列為空時(shí)，表明沒有擁塞發(fā)生，鏈路負(fù)載監(jiān)測將關(guān)閉。 由于CSMA在發(fā)送數(shù)據(jù)前需要監(jiān)聽信道判斷信道是否空閑，所以將鏈路負(fù)載監(jiān)測放在該段時(shí)間一起進(jìn)行將不會帶來任何額外的開銷。 CODA擁塞控制方案擁塞控制方案-開環(huán)跳段反向壓力信標(biāo)機(jī)制開環(huán)跳段反向壓力信標(biāo)機(jī)制 檢測到網(wǎng)絡(luò)發(fā)生擁塞時(shí)，節(jié)點(diǎn)將向鄰居節(jié)點(diǎn)廣播一個(gè)反向壓力信標(biāo)，同時(shí)采用相應(yīng)的數(shù)據(jù)包丟棄策略或調(diào)整數(shù)據(jù)發(fā)送速率來防止擁塞的進(jìn)一步傳播。 當(dāng)上游節(jié)點(diǎn)接收到反向

17、壓力信標(biāo)后，它將根據(jù)局部擁塞策略選擇直接丟棄到來的數(shù)據(jù)包以防止緩沖區(qū)溢出，而不繼續(xù)傳送反向壓力信標(biāo)。 如果節(jié)點(diǎn)當(dāng)前的緩沖區(qū)溢出，則選擇向上游節(jié)點(diǎn)繼續(xù)傳送該信標(biāo)。 CODA擁塞控制方案擁塞控制方案-閉環(huán)多源調(diào)整機(jī)制閉環(huán)多源調(diào)整機(jī)制 CODA中提出的閉環(huán)多源調(diào)整機(jī)制，能夠在無線傳感器網(wǎng)絡(luò)中發(fā)生持續(xù)擁塞時(shí)，通過基站節(jié)點(diǎn)對源節(jié)點(diǎn)進(jìn)行擁塞控制。 當(dāng)源事件速率r小于最大理論帶寬Smax的一定百分比時(shí)(即rSmax時(shí)，該源節(jié)點(diǎn)認(rèn)為網(wǎng)絡(luò)很可能發(fā)生了擁塞，因此將觸發(fā)閉環(huán)多源調(diào)整機(jī)制。 數(shù)據(jù)率控制算法為避免或者解除無線傳感器網(wǎng)絡(luò)擁塞，可以通過數(shù)據(jù)率控制方法控制網(wǎng)絡(luò)中節(jié)點(diǎn)的傳輸速率。當(dāng)節(jié)點(diǎn)的速率保持一定時(shí)，可以通過

18、控制在此速率下發(fā)送數(shù)據(jù)的節(jié)點(diǎn)個(gè)數(shù)來達(dá)到控制網(wǎng)絡(luò)流量的目的。 基于基于Gur Game的的QoS控制算法控制算法l River等人將無線傳感器網(wǎng)絡(luò)QoS定義為傳感器網(wǎng)絡(luò)中任意時(shí)刻向基站發(fā)送傳感數(shù)據(jù)的節(jié)點(diǎn)個(gè)數(shù)，并提出了一種新的QoS控制算法。l 在該算法中，基站利用廣播信道來與各個(gè)傳感器節(jié)點(diǎn)進(jìn)行QoS信息通信，并使用Gur Game 分布式算法來動態(tài)調(diào)整網(wǎng)絡(luò)中節(jié)點(diǎn)的狀態(tài)。l 通過該算法，網(wǎng)絡(luò)中節(jié)點(diǎn)可選擇周期性睡眠實(shí)現(xiàn)節(jié)能，同時(shí)還保證網(wǎng)絡(luò)中有足夠的活動節(jié)點(diǎn)向基站發(fā)送信息?；诨贕ur Game的的QoS控制算法控制算法 圖 10 17Gur Game函數(shù) 基于基于Gur Game的的QoS控制算法

19、控制算法 算法賦予每個(gè)玩家一個(gè)有限離散時(shí)間自動機(jī)用來記憶其之前的選擇。 每個(gè)有限狀態(tài)自動機(jī)由一組連續(xù)狀態(tài)所組成，狀態(tài)個(gè)數(shù)為2N代表玩家的記憶容量，參數(shù)N稱為記憶參數(shù)。從最左邊的狀態(tài)開始，給每個(gè)狀態(tài)順序編號-N到-1，再從1編號到N。基于基于Gur Game的的QoS控制算法控制算法 任何時(shí)刻玩家只能處于一種狀態(tài)，而且玩家狀態(tài)的改變只能在狀態(tài)j, j+1, j-1之間進(jìn)行(即相鄰狀態(tài)之間)。當(dāng)玩家狀態(tài)為N(或-N)時(shí)，狀態(tài)將在N(-N)與N-1(-N+1)之間改變。 當(dāng)裁判公布獎勵概率r后，玩家如果處于狀態(tài)j，就以概率r轉(zhuǎn)到狀態(tài)j+1, 以概率1-r轉(zhuǎn)到狀態(tài)i-1。當(dāng)玩家處于正狀態(tài)時(shí)，他將投票選

20、擇“是”，處于負(fù)狀態(tài)選擇“否”。排除隨機(jī)波動的影響，在經(jīng)過i輪循環(huán)后，裁判接收到“是”的票數(shù)將收斂到k。基于基于Gur Game的的QoS控制算法控制算法圖 10 18Gur Game 狀態(tài)機(jī) (N=2) 基于基于Gur Game的的QoS控制算法控制算法圖 10 19網(wǎng)絡(luò)活動節(jié)點(diǎn)個(gè)數(shù) 實(shí)時(shí)數(shù)據(jù)傳輸 在某些無線傳感器網(wǎng)絡(luò)應(yīng)用中，需要保證采集的傳感數(shù)據(jù)實(shí)時(shí)地傳送到匯聚節(jié)點(diǎn)。比如在無線監(jiān)控系統(tǒng)應(yīng)用中，傳感數(shù)據(jù)與基站間的通信延遲直接影響系統(tǒng)的跟蹤質(zhì)量和效果。 SPEED路由 RPAR路由SPEED路由協(xié)議 為滿足數(shù)據(jù)包傳輸?shù)臅r(shí)延需求，Tian He等人設(shè)計(jì)了一個(gè)基于反饋控制和無狀態(tài)算法，支持實(shí)時(shí)通信

21、的路由協(xié)議SPEED SPEED是地理位置信息相關(guān)的路由協(xié)議，它面向?qū)崟r(shí)應(yīng)用提供端到端數(shù)據(jù)包傳輸速率保證。 SPEED協(xié)議中實(shí)現(xiàn)了網(wǎng)絡(luò)擁塞控制、負(fù)載平衡以及路由空洞避免機(jī)制，能有效提高數(shù)據(jù)包傳輸成功率、節(jié)省能量消耗、延長網(wǎng)絡(luò)壽命。 該協(xié)議是無狀態(tài)的結(jié)構(gòu)，節(jié)點(diǎn)只需保持其鄰居節(jié)點(diǎn)信息，無須保存路由表全局信息，有很好的擴(kuò)展性。無須MAC層提供QoS或?qū)崟r(shí)性支持。 SPEED路由協(xié)議圖 10 20SPEED路由協(xié)議模塊 SPEED路由協(xié)議-鄰居信標(biāo)交換機(jī)制 SPEED協(xié)議中每一個(gè)節(jié)點(diǎn)向鄰居節(jié)點(diǎn)周期廣播信標(biāo)數(shù)據(jù)包。該周期信標(biāo)用于鄰居節(jié)點(diǎn)之間交換地理位置信息。 除了鄰居信標(biāo)之外，SPEED還有延遲估計(jì)信標(biāo)

22、和反向壓力信標(biāo)。延遲估計(jì)信標(biāo)用于在節(jié)點(diǎn)與鄰居節(jié)點(diǎn)之間傳輸延遲估計(jì)。當(dāng)節(jié)點(diǎn)發(fā)現(xiàn)網(wǎng)絡(luò)發(fā)生擁塞時(shí)，SPEED使用反向壓力信標(biāo)通知上游節(jié)點(diǎn)做出相應(yīng)調(diào)整。 SPEED路由協(xié)議-延遲估計(jì) 在發(fā)送端，發(fā)送節(jié)點(diǎn)在數(shù)據(jù)包進(jìn)入到網(wǎng)絡(luò)輸出隊(duì)列時(shí)打上時(shí)間戳，然后在接收到該數(shù)據(jù)包ACK時(shí)，從收發(fā)時(shí)間差中減去接收端的處理時(shí)間得到一跳的通信延遲。 在接收端，接收節(jié)點(diǎn)處理ACK數(shù)據(jù)包的時(shí)間將作為ACK的一個(gè)字段發(fā)送回去。通過將新計(jì)算的延遲值與原延遲值進(jìn)行指數(shù)加權(quán)平均來更新延遲值。 考慮到無線傳感器網(wǎng)絡(luò)的傳播距離，在延遲計(jì)算中忽略了傳播延遲。SPEED路由協(xié)議-SNGF算法 節(jié)點(diǎn)利用局部地理信息和傳輸速率信息在鄰居節(jié)點(diǎn)中選擇下

23、一跳路由。 鄰居節(jié)點(diǎn)定義為處于當(dāng)前節(jié)點(diǎn)通信范圍內(nèi)的節(jié)點(diǎn)。節(jié)點(diǎn)在其鄰居節(jié)點(diǎn)中，選擇比自己距離目標(biāo)區(qū)域更近的節(jié)點(diǎn)組成候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集合（forwarding candidate set, FCS）。 節(jié)點(diǎn)利用前面介紹的延遲估計(jì)獲得到所有鄰居節(jié)點(diǎn)的延遲。根據(jù)該延遲及節(jié)點(diǎn)間的距離，節(jié)點(diǎn)可計(jì)算其FCS集合中每個(gè)節(jié)點(diǎn)的傳輸速率。SPEED路由協(xié)議-SNGF算法根據(jù)傳輸速率是否滿足預(yù)定的傳輸速率域值，F(xiàn)CS集合中的節(jié)點(diǎn)分為兩類：大于速率域值的鄰居節(jié)點(diǎn)集合和小于速率域值的鄰居節(jié)點(diǎn)集合。若大于速率域值的鄰居節(jié)點(diǎn)集合不為空，則在該集合的節(jié)點(diǎn)中按照一定的概率分布選擇下一跳節(jié)點(diǎn)，節(jié)點(diǎn)的傳輸速率越大，被選中的概率也越大；

24、若大于速率域值的鄰居節(jié)點(diǎn)集合為空，則在小于速率域值的鄰居節(jié)點(diǎn)集合中，使用鄰居反饋循環(huán)NFL算法計(jì)算轉(zhuǎn)發(fā)概率，并按這個(gè)概率決定是否丟棄分組。如果決定轉(zhuǎn)發(fā)分組，F(xiàn)CS集合內(nèi)的節(jié)點(diǎn)按照一定的概率分布選擇為下一跳節(jié)點(diǎn)。SPEED路由協(xié)議-鄰居反饋循環(huán)策略 鄰居反饋循環(huán)策略NFL(Neighbor Feedback Loop)是SPEED協(xié)議中保證網(wǎng)絡(luò)單跳傳輸速度的關(guān)鍵部分。當(dāng)節(jié)點(diǎn)將數(shù)據(jù)包發(fā)送到轉(zhuǎn)發(fā)速度小于傳輸速率閾值的節(jié)點(diǎn)或者發(fā)生了數(shù)據(jù)包丟失時(shí)，節(jié)點(diǎn)認(rèn)為發(fā)生了傳輸差錯(cuò)。NFL策略將統(tǒng)計(jì)當(dāng)前節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)傳輸差錯(cuò)率，并使該差錯(cuò)率收斂為0。MAC層收集差錯(cuò)信息，并將傳輸差錯(cuò)率反饋到轉(zhuǎn)發(fā)比例控制器(Re

25、lay Ratio Controller)。轉(zhuǎn)發(fā)比例控制器是一個(gè)多輸入單輸出的控制器，將根據(jù)這些差錯(cuò)率計(jì)算轉(zhuǎn)發(fā)概率，供SNGF路由算法作路由選擇。轉(zhuǎn)發(fā)比例控制器只有當(dāng)大于速率域值的鄰居節(jié)點(diǎn)集合為空時(shí)才會啟動。 SPEED路由協(xié)議-鄰居反饋循環(huán)策略圖 10 21鄰居反饋循環(huán) RPAR(Real-time Power-Aware Routing)路由 Octav Chipara認(rèn)為在無線網(wǎng)絡(luò)中傳輸功率與通信延遲之間存在一個(gè)折衷。為分析無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的傳輸功率對通信延遲的影響，他在XSM2節(jié)點(diǎn)上進(jìn)行了實(shí)驗(yàn)分析。 實(shí)驗(yàn)結(jié)果如圖10-22所示RPAR路由圖 10-22發(fā)射功率和跳段距離對傳輸速度的影

26、響 RPAR路由實(shí)驗(yàn)表明： 節(jié)點(diǎn)的發(fā)射功率對數(shù)據(jù)包傳輸速度有著非常明顯的影響。 當(dāng)固定節(jié)點(diǎn)發(fā)射功率不變，改變跳段距離時(shí)，數(shù)據(jù)包傳輸速度一開始有所增加，當(dāng)?shù)竭_(dá)一定距離后會急劇下降。 數(shù)據(jù)包傳輸速度在最開始增加是由于數(shù)據(jù)包每跳的傳輸距離更遠(yuǎn)了，而之后的急劇下降是因?yàn)榫嚯x超過了發(fā)射功率范圍。 在輕負(fù)載時(shí)，發(fā)射功率調(diào)整將是控制通信延遲的有效方法。但是增加功率也有其它的一些負(fù)面影響：由于提高了發(fā)射功率會增加信道的競爭和干擾，從而導(dǎo)致網(wǎng)絡(luò)的最大可用吞吐量下降。 RPAR路由協(xié)議組成 動態(tài)速度分配策略 轉(zhuǎn)發(fā)策略 延遲估計(jì) 鄰居管理器。 RPAR路由協(xié)議-動態(tài)速度分配策略動態(tài)速度分配策略在節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包之前，

27、它將根據(jù)到目的節(jié)點(diǎn)的距離和數(shù)據(jù)包所剩時(shí)限slack，使用動態(tài)速度分配策略計(jì)算出所需速度。應(yīng)用在源節(jié)點(diǎn)初始化slack時(shí)限，在每一條節(jié)點(diǎn)需要根據(jù)緩沖隊(duì)列延遲、競爭延遲、傳輸延遲更新數(shù)據(jù)包中的slack時(shí)限值。為計(jì)算緩沖隊(duì)列延遲，節(jié)點(diǎn)在接收到數(shù)據(jù)包和數(shù)據(jù)包成為傳輸隊(duì)列頭時(shí)分別打上時(shí)戳，這樣當(dāng)數(shù)據(jù)包成為傳輸隊(duì)列頭時(shí)，數(shù)據(jù)包所需速度按下面公式計(jì)算：)()()(),(),(StStSslackDSdDSvrecheadrecreqRPAR路由協(xié)議-轉(zhuǎn)發(fā)策略轉(zhuǎn)發(fā)策略 當(dāng)節(jié)點(diǎn)接收到數(shù)據(jù)包，并利用動態(tài)速度分配策略計(jì)算出其所需速度后，它需要在其鄰居表中查找能夠滿足當(dāng)前速度需求的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。下一跳節(jié)點(diǎn)所能提供

28、的速度保證由下面公式給出：)( ,(),(),(),( ,(pN,SdelayDNdDSdPNDSvprovRPAR路由協(xié)議-延遲估計(jì)延遲估計(jì) 延遲估計(jì)負(fù)責(zé)對估計(jì)各個(gè)不同轉(zhuǎn)發(fā)選擇的延遲。源節(jié)點(diǎn)使用功率p發(fā)送數(shù)據(jù)包到鄰居節(jié)點(diǎn)N的延遲時(shí)間取決于多個(gè)因素：競爭信道延遲、數(shù)據(jù)包和ACK報(bào)文傳輸延遲，以及傳輸次數(shù)。 RPAR路由協(xié)議-鄰居管理器鄰居管理器 RPAR中的鄰居管理器負(fù)責(zé)動態(tài)發(fā)現(xiàn)可用高效的轉(zhuǎn)發(fā)選擇并管理節(jié)點(diǎn)鄰居表。當(dāng)鄰居表中的所有節(jié)點(diǎn)都不能滿足當(dāng)前數(shù)據(jù)包速度要求時(shí)，鄰居管理器被觸發(fā)。鄰居管理器為發(fā)現(xiàn)新的可用轉(zhuǎn)發(fā)選擇提供了兩種機(jī)制：調(diào)整鄰居表中節(jié)點(diǎn)的發(fā)射功率(功率調(diào)整)和發(fā)現(xiàn)新鄰居。 功率調(diào)整： 當(dāng)轉(zhuǎn)發(fā)策略無法在鄰居節(jié)點(diǎn)中發(fā)現(xiàn)滿足速度要求的節(jié)點(diǎn)時(shí)，鄰居管理器將從鄰居中選擇一個(gè)節(jié)點(diǎn)增大它的發(fā)射功率以取得更快的傳輸速度。在鄰居節(jié)點(diǎn)中，如果節(jié)點(diǎn)通過增大發(fā)射功率能夠減少傳輸次數(shù)，則該節(jié)點(diǎn)能夠作為增大發(fā)射功率的候選節(jié)點(diǎn)。 當(dāng)節(jié)點(diǎn)處于以下情況時(shí)，則不適于繼續(xù)增大