無線傳感器網(wǎng)絡(luò)多路徑傳輸時延優(yōu)化調(diào)度算法研究
2018-07-24 09:38:42虞志剛
中國電子科學(xué)研究院學(xué)報 2018年3期
趙 晶,虞志剛,馮 旭,陸 洲
(中國電子科學(xué)研究院， 北京 100041)
0 引 言
無線通信技術(shù)具有低成本、易部署、靈活性高等特征，這些特征使得工業(yè)應(yīng)用與無線傳感器網(wǎng)絡(luò)結(jié)合成為應(yīng)用發(fā)展的必然趨勢[1-3]。由于工業(yè)數(shù)據(jù)高質(zhì)量傳輸?shù)男枨螅约皭毫拥墓I(yè)環(huán)境帶來的挑戰(zhàn)，工業(yè)無線標(biāo)準(zhǔn)WirelessHART ISA-100.11a、WIA-PA提出數(shù)據(jù)鏈路層采用TDMA協(xié)議結(jié)合信道跳頻技術(shù)，網(wǎng)絡(luò)層采用圖路由技術(shù)，網(wǎng)絡(luò)采用集中控制模式，集中控制器負(fù)責(zé)網(wǎng)絡(luò)通信質(zhì)量保證、鏈路層調(diào)度和網(wǎng)絡(luò)層路由確定。采用TDMA協(xié)議可以保證端到端傳輸?shù)拇_定性時延，其面臨的問題是時隙和信道的有效分配。多跳傳輸網(wǎng)絡(luò)中，資源調(diào)度不僅要考慮鏈路之間的干擾和沖突，還要考慮路徑中鏈路的次序。
近年來，支持多跳傳輸?shù)臒o線傳感器網(wǎng)絡(luò)資源調(diào)度算法已經(jīng)被廣泛研究?，F(xiàn)有研究已經(jīng)證明在Mesh網(wǎng)絡(luò)中實現(xiàn)最短時延調(diào)度是NP難問題[4]。文獻(xiàn)[5-7]研究的是基于原始數(shù)據(jù)的資源優(yōu)化調(diào)度方案，文獻(xiàn)[8-10]研究的是基于數(shù)據(jù)融合的資源優(yōu)化調(diào)度方案。在許多工業(yè)應(yīng)用中，由于原始數(shù)據(jù)的重要性以及數(shù)據(jù)間相關(guān)性差，中心需要接收到每個原始數(shù)據(jù)。因此，本文設(shè)計的調(diào)度方案不考慮數(shù)據(jù)融合。
上述的調(diào)度研究大多針對單路徑傳輸，工業(yè)標(biāo)準(zhǔn)定義網(wǎng)絡(luò)采用多路徑傳輸提高網(wǎng)絡(luò)可靠性，而數(shù)據(jù)包實際傳輸過程中僅采用一條路徑，其余路徑的通信資源將會被浪費(fèi)。因此，多路徑傳輸?shù)恼{(diào)度方案需進(jìn)行時延優(yōu)化以提高資源利用率。文獻(xiàn)[11-12]研究的是分布式網(wǎng)絡(luò)的多路徑調(diào)度方案，調(diào)度算法主要通過節(jié)點的信息交互獲取可用時隙信道，從而確定調(diào)度方案。這種調(diào)度方案獲取的網(wǎng)絡(luò)信息是有限的，而集中式控制的網(wǎng)絡(luò)可以根據(jù)網(wǎng)絡(luò)的全局信息進(jìn)行優(yōu)化的資源調(diào)度[13-15]。文獻(xiàn)[13]將通信過程中多條路徑包含的鏈路羅列，然后為每條鏈路分配相應(yīng)的通信資源，這種方案沒有進(jìn)行時延優(yōu)化，需要大量的通信資源；文獻(xiàn)[14]提出了采用時隙重復(fù)利用技術(shù)以提高資源調(diào)度的效率，但是該方案只適用于狹窄的網(wǎng)絡(luò)結(jié)構(gòu)；文獻(xiàn)[15]為每個節(jié)點選擇冗余下一跳以保證多路徑傳輸，然后通過將數(shù)據(jù)流分流為不同的下一跳節(jié)點分配資源，從而減少調(diào)度所需的時隙資源，然而這種調(diào)度方案并沒有考慮數(shù)據(jù)重傳的情況，鏈路失效會造成帶寬的下降。
本文研究多路徑傳輸時延優(yōu)化調(diào)度算法，主要內(nèi)容如下：第二章介紹了本文的研究背景，包括采用的通信協(xié)議，方案需要考慮的跨層調(diào)度原則和兩種路由容錯機(jī)制；第三章給出了網(wǎng)絡(luò)模型，介紹了文中涉及的變量；第四章簡單介紹了之前論文提出的圖路由生成算法，基于確定的網(wǎng)絡(luò)拓?fù)浞謩e設(shè)計了復(fù)制機(jī)制和重傳機(jī)制下的資源調(diào)度算法；第五章通過仿真說明兩種調(diào)度算法各自的優(yōu)劣性；第六章對本文進(jìn)行了總結(jié)。
1 研究背景
WirelessHART作為商用的工業(yè)無線標(biāo)準(zhǔn)，定義了工業(yè)無線傳感器網(wǎng)絡(luò)的主要組成：集中控制器、無線接入點和現(xiàn)場設(shè)備。標(biāo)準(zhǔn)定義數(shù)據(jù)鏈路層采用TDMA協(xié)議，該協(xié)議將時間劃分為若干個超幀，超幀進(jìn)一步劃分為若干個時隙，每個時隙可以完成數(shù)據(jù)包的發(fā)送和ACK的接收。工業(yè)無線傳感器網(wǎng)絡(luò)中的現(xiàn)場設(shè)備為半雙工通信，因此，設(shè)備不能同時進(jìn)行數(shù)據(jù)包的收發(fā)。為了避免不同鏈路之間的干擾，WirelessHART網(wǎng)絡(luò)不采用空分復(fù)用接入(Space Division Multiple Access，SDMA)協(xié)議，一個信道在一個時隙內(nèi)只允許一對通信節(jié)點進(jìn)行數(shù)據(jù)傳輸。網(wǎng)絡(luò)層，工業(yè)無線標(biāo)準(zhǔn)提出了圖路由協(xié)議，每個路由圖由圖號標(biāo)識，節(jié)點查詢圖號確定下一跳。圖路由協(xié)議可以減少數(shù)據(jù)包開銷且支持多路徑傳輸。集中控制器負(fù)責(zé)網(wǎng)絡(luò)維護(hù)、拓?fù)湫畔⑹占?、?shù)據(jù)鏈路層調(diào)度和網(wǎng)絡(luò)層路由圖生成以及信息下發(fā)。
1.1 跨層調(diào)度
在多跳傳輸中采用TDMA協(xié)議，時隙調(diào)度需要考慮網(wǎng)絡(luò)層的路徑選擇和傳輸次序，否則會影響數(shù)據(jù)包傳輸?shù)臅r效性，以圖1為例，基于跳數(shù)的路由度量標(biāo)準(zhǔn)，路徑(S→A→B→D)和路徑(S→E→F→D)在網(wǎng)絡(luò)層都是最優(yōu)的。但是在數(shù)據(jù)鏈路層，如果時隙調(diào)度沒有考慮網(wǎng)絡(luò)層的路徑選擇和傳輸次序，選擇路徑(S→E→F→D)的數(shù)據(jù)包經(jīng)過3個超幀才能到達(dá)目的節(jié)點，嚴(yán)重影響了傳輸時延，而路徑(S→A→B→D)由于其時隙調(diào)度順序和鏈路次序相同，使用1個超幀就可以完成數(shù)據(jù)傳輸，傳輸時延小。
圖1 資源的跨層調(diào)度
1.2 路由的容錯機(jī)制
無線網(wǎng)絡(luò)開放的傳輸介質(zhì)，以及能力受限的節(jié)點不可避免地出現(xiàn)數(shù)據(jù)包無法成功傳輸?shù)那闆r。因此，工業(yè)無線標(biāo)準(zhǔn)采用的圖路由協(xié)議支持多路徑傳輸技術(shù)。多路徑傳輸?shù)娜蒎e主要有兩種機(jī)制：復(fù)制機(jī)制(replication mechanism)和重傳機(jī)制(retransmission mechanism)[16]。復(fù)制機(jī)制是將數(shù)據(jù)包復(fù)制多份，通過不同的路徑進(jìn)行傳輸，從而提高數(shù)據(jù)的冗余性。這種容錯方式實現(xiàn)簡單，但是會加大網(wǎng)絡(luò)負(fù)載，造成資源浪費(fèi)。重傳機(jī)制基于不同的丟包檢測方式可分為逐跳重傳(Hop-by-Hop，HbH)和端到端(End-to-End，E2E)重傳兩種[17]。逐跳重傳是指節(jié)點發(fā)送數(shù)據(jù)包后一定時間內(nèi)沒有收到下一跳返回的ACK回復(fù)則進(jìn)行數(shù)據(jù)重傳。端到端重傳是目的節(jié)點負(fù)責(zé)檢測丟包，如果源節(jié)點在一定時間內(nèi)沒有收到目的節(jié)點的ACK回復(fù)則進(jìn)行數(shù)據(jù)重傳。無線傳感器網(wǎng)絡(luò)中，上層協(xié)議相對簡單，重傳的等待時延不好確定。尤其是支持多跳傳輸?shù)木W(wǎng)絡(luò)中，端到端的數(shù)據(jù)包和控制包需要經(jīng)歷多個節(jié)點，在無線網(wǎng)絡(luò)中同樣面臨很高的丟包風(fēng)險。而無線網(wǎng)絡(luò)中單跳的丟包容易確定，重傳機(jī)制大都采用逐跳重傳。
數(shù)據(jù)鏈路層的資源調(diào)度直接決定了節(jié)點的通信行為，不僅要考慮傳輸路徑的選擇，還要考慮在數(shù)據(jù)包發(fā)送失敗的情況下，數(shù)據(jù)包的重傳方式?；谏鲜鰡栴}的考慮，本文首先給出了路由圖的生成算法，然后基于確定的路由圖和重傳機(jī)制，提出了相應(yīng)的資源調(diào)度算法。
2 問題描述
2.1 網(wǎng)絡(luò)模型
本文研究的是多跳的mesh網(wǎng)絡(luò)，網(wǎng)絡(luò)拓?fù)溆蒅=(V，E)表示，其中V={v0,v1,…,vn}代表現(xiàn)場設(shè)備，E代表通信鏈路。鏈路ei,j∈E代表節(jié)點vi可以給節(jié)點vj發(fā)送數(shù)據(jù)包。網(wǎng)絡(luò)節(jié)點vi有多個下一跳節(jié)點，由vj1,vj2,…vjn表示。集中控制器生成的路由圖由Gg=(Vg，Eg)表示。
2.2 鏈路度量
路徑選擇的過程就是節(jié)點選擇鄰居節(jié)點的過程，每個節(jié)點具有鄰居節(jié)點集合Mi,vj1,vj2,…vjn∈Mi。qi為鄰居節(jié)點vj作為vi的轉(zhuǎn)發(fā)節(jié)點的通信度量值，取決于節(jié)點vj的數(shù)據(jù)傳輸成功率和能量消耗。節(jié)點vj將數(shù)據(jù)包成功傳輸?shù)侥康墓?jié)點的傳輸成功概率為Rj，節(jié)點vj的剩余能量為Cj，鏈路ei,j通信所消耗的能量為Ci,j。
路由容錯采用復(fù)制機(jī)制的情況下，任意數(shù)據(jù)包到達(dá)目的節(jié)點即為傳輸成功，因此，節(jié)點的傳輸成功概率Ri為：
Ri=1-(1-P(i,j1)Rj1)(1-P(i,j2)Rj2)…
(1-P(i,jn)Rjn)
(1)
其中，P(i,j)是鏈路ei,j成功發(fā)送數(shù)據(jù)包的概率，Rjn為選擇鄰居節(jié)點vjn為轉(zhuǎn)發(fā)節(jié)點的傳輸成功概率。
路由容錯采用逐跳重傳機(jī)制的情況下，節(jié)點首先向最優(yōu)下一跳節(jié)點發(fā)送數(shù)據(jù)包，如果傳輸失敗，節(jié)點選擇冗余下一跳進(jìn)行重傳。如果所有的下一跳都沒有成功接收數(shù)據(jù)包，則數(shù)據(jù)包發(fā)送失敗。因此，節(jié)點的傳輸成功概率Ri為：
(2)
路由算法選擇下一跳，鏈路度量考慮能耗和傳輸成功率，具體過程如下：
(3)
(4)
其中，ρ1,ρ2>0。上述的路徑度量方式在選擇下一跳節(jié)點時主要考慮傳輸成功率和節(jié)點剩余能量。同時，參數(shù)γ受鏈路能耗Ci,j影響，節(jié)點傾向于選擇鏈路能耗小的節(jié)點發(fā)送數(shù)據(jù)包。新的下一跳集合是從鄰居節(jié)點集合Mi中選出，選擇最大化鏈路度量：
(5)
3 多路徑傳輸資源調(diào)度方案
數(shù)據(jù)鏈路層的資源調(diào)度方案依賴于網(wǎng)絡(luò)層的路徑選擇，本節(jié)首先介紹了作者之前論文提出的一種路由圖生成算法。基于該路由圖的生成算法，論文討論了兩種路由容錯模式下的多路徑傳輸調(diào)度方案，進(jìn)行了分析對比。
3.1 路由圖的生成
算法1路由圖生成算法1: G(V,E)為網(wǎng)絡(luò)圖,構(gòu)建路由圖Gg=(Vg,Eg)2: 初始化Vg←vD,fD=1,f=13: Si為節(jié)點vi的可用鄰居節(jié)點集合,SiVg4:?vj∈Si,vj為節(jié)點vi的鄰居節(jié)點5: 確定Pti,Pti為節(jié)點vi的下一跳節(jié)點集合, Pti=? 6: whilevi?Vgdo 7: 尋找集合Si8: if all vi,?vi∈V-Vg,Si=? then9: 網(wǎng)絡(luò)不是全聯(lián)通的10: return FAIL;11: else12: for all vi, vi∈V-Vgdo13: for all vj ,vj∈Sido14: Sort 通信質(zhì)量qj,考慮已有父節(jié)點Pti15: 選擇最大化通信質(zhì)量qi的節(jié)點vj為父節(jié)點,vj∈Pti16: ifPti=? then17: ri=rj+118: end if19: ifRi≥rridthen20: vi∈Vin,Vin為可靠節(jié)點集合 break;21: else ifSi-vj=? then22: vi∈Ven,Ven為不可靠節(jié)點集合break;23: else24: Si=Si-vj25: end if26: end for27: end for28: end if29: ifVin≠? then30: 選擇節(jié)點vi,vi∈Vin,網(wǎng)絡(luò)等級值ri最小,fi=f+131: 將節(jié)點vi加入到Vg,將鏈路ei,j加入到Eg32: else33: 選擇節(jié)點vi,vi∈Ven,可靠性Ri最大,fi=f+134: 將節(jié)點vi加入到Vg,將鏈路ei,j加入到Eg
35: end if36: end while37: return SUCCESS;
3.2 多路徑傳輸調(diào)度方案
根據(jù)算法1，集中控制器可以為一對通信節(jié)點選定傳輸路徑生成路由圖，然后根據(jù)路由圖及容錯機(jī)制為通信過程分配相應(yīng)的網(wǎng)絡(luò)資源。以一次通信過程為例，節(jié)點S向節(jié)點D發(fā)送一個數(shù)據(jù)包，圖2(a)所示為節(jié)點S到節(jié)點D的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，通過路由圖生成算法可得圖2(b)中數(shù)據(jù)包的傳輸路徑。針對多路徑傳輸模式，路由可以采取兩種容錯機(jī)制——復(fù)制機(jī)制和逐跳重傳機(jī)制。
圖2 通信示例
3.2.1 基于復(fù)制機(jī)制的多路徑傳輸調(diào)度方案
復(fù)制機(jī)制中，路徑中的節(jié)點在收到數(shù)據(jù)包時，如果已經(jīng)收到過該數(shù)據(jù)包，則將數(shù)據(jù)包丟棄；如果沒有收到過該數(shù)據(jù)包，則將數(shù)據(jù)包以廣播的形式發(fā)送給多個下一跳節(jié)點。因此，數(shù)據(jù)包傳輸過程中，路徑包含的每個節(jié)點只需要一次發(fā)送數(shù)據(jù)包的機(jī)會，節(jié)點的傳輸時隙必須早于其下一跳節(jié)點的傳輸時隙，以避免傳輸次序的紊亂。
以圖2中所示通信過程為例，源節(jié)點S將數(shù)據(jù)包同時發(fā)送給節(jié)點B和節(jié)點E；節(jié)點B和E收到數(shù)據(jù)包之后再進(jìn)行轉(zhuǎn)發(fā)，直到目的節(jié)點D，過程如圖3(a)所示。數(shù)據(jù)傳輸過程中，節(jié)點多次收到數(shù)據(jù)包時，僅進(jìn)行一次轉(zhuǎn)發(fā)，如節(jié)點F同時收到節(jié)點B和節(jié)點E發(fā)來的數(shù)據(jù)包，但僅轉(zhuǎn)發(fā)一次該數(shù)據(jù)包。在數(shù)據(jù)傳輸過程中，多條路徑中的每個節(jié)點都可能接收并轉(zhuǎn)發(fā)數(shù)據(jù)包。由于WirelessHART標(biāo)準(zhǔn)定義同一時隙同一信道內(nèi)僅允許一對通信節(jié)點進(jìn)行數(shù)據(jù)傳輸，因此，復(fù)制模式下，節(jié)點采用廣播模式，同一時隙同一信道內(nèi)僅調(diào)度一個節(jié)點作為發(fā)送節(jié)點，如圖3(b)所示。
圖3 復(fù)制模式下資源調(diào)度過程
復(fù)制機(jī)制下，算法2提出了基于節(jié)點的資源調(diào)度方案。節(jié)點調(diào)度的次序需要考慮多條路徑的傳輸次序,節(jié)點的調(diào)度次序取決于路由圖的生成算法，先加入路由圖的節(jié)點不會發(fā)送數(shù)據(jù)包給后加入路由圖的節(jié)點，因此，先加入路由圖的節(jié)點的發(fā)送時隙也較晚。
算法2基于復(fù)制機(jī)制的調(diào)度算法1: 路由圖Gg(Vg,Eg),調(diào)度集合為S={vS}2: lev=1;3: while S≠{vD}, do 4: Sort fi, 其中?vi∈S,5: 選擇節(jié)點vi , fi最大6: 將時隙k*lF+ASN+lev分配給ST->vi和SR->childi7: 其中l(wèi)F為超幀長度,ASN為偏移量,childi為節(jié)點vi的下一跳節(jié)點集合,ST為發(fā)送狀態(tài),SR為接收狀態(tài)8: 將集合childi中的節(jié)點加入到調(diào)度集合S9 end while10:return SUCCESS;
3.2.2 基于重傳機(jī)制的多路徑傳輸調(diào)度方案
重傳機(jī)制中，節(jié)點在數(shù)據(jù)包發(fā)送失敗的情況下進(jìn)行重傳，將數(shù)據(jù)包發(fā)送給冗余下一跳節(jié)點。如果節(jié)點向所有下一跳節(jié)點發(fā)送數(shù)據(jù)包失敗，則數(shù)據(jù)包丟棄。由于多條路徑中數(shù)據(jù)包最終僅通過一條路徑進(jìn)行數(shù)據(jù)傳輸，鏈路的使用情況取決于數(shù)據(jù)包發(fā)送成功與否。因此通過不同路徑中鏈路的虛擬共享實現(xiàn)網(wǎng)絡(luò)資源的優(yōu)化調(diào)度[19]。
以圖2中所示通信過程為例，源節(jié)點S將數(shù)據(jù)包首先發(fā)送給節(jié)點B，如果節(jié)點B成功接收數(shù)據(jù)包，則數(shù)據(jù)包將被發(fā)送給節(jié)點C；如果節(jié)點B收到數(shù)據(jù)包失敗，則節(jié)點S將數(shù)據(jù)包重新發(fā)送給節(jié)點E，如圖4(a)所示。在第二個時隙內(nèi)，鏈路B→C和S→E是在兩種條件下發(fā)生，因此，這兩條鏈路共享同一時隙信道資源并不會產(chǎn)生沖突，從而減少調(diào)度所需的資源。同時，鏈路F→D在兩條路徑中出現(xiàn)，一次出現(xiàn)于S→B成功、B→C失敗、B→F成功的情況下，另一次出現(xiàn)于S→B失敗、S→E成功、E→F成功的情況下。數(shù)據(jù)包最多可能經(jīng)過鏈路F→D一次，因此，這兩次鏈路調(diào)度可以合并為一條，從而減少鏈路的調(diào)度次數(shù)，延長節(jié)點的休眠時間，如圖4(b)所示。
重傳模式下，算法3給出了基于鏈路的資源調(diào)度方案。算法首先以源節(jié)點為根節(jié)點，節(jié)點指向所有下一跳節(jié)點生成路徑樹，然后基于傳輸狀況遍歷路徑樹，確定鏈路的傳輸次序，最后計算路徑樹的等級數(shù)，確定鏈路調(diào)度對應(yīng)的時隙。由于同一鏈路在實際傳輸中最多被使用一次，算法將鏈路進(jìn)行了合并優(yōu)化，最后給出了時隙調(diào)度。調(diào)度算法分為以下幾步：
算法3基于重傳機(jī)制的調(diào)度算法1: 路由圖Gg(Vg,Eg),根節(jié)點為vD2: ASN=0; //記錄調(diào)度的時隙數(shù)3: 建立傳輸?shù)恼{(diào)度方案4: CreateTree(vD, Gg, T) ; //基于路由圖Gg生成路徑樹 5: TraverseTree(T) ; //遍歷路徑樹6: lev=1;7: CalculateLevel(T, lev) ; //計算等級數(shù)8: OptimalTree(T) ; //優(yōu)化路徑樹9: lev=1;10: ScheduleLink(T, lev, F) ; //時隙調(diào)度11: return SUCCESS;
圖4 重傳模式下資源調(diào)度過程
(1)生成路徑樹：基于路由圖Gg，以源節(jié)點為根節(jié)點，記錄節(jié)點的下一跳節(jié)點(有順序)。路徑樹的節(jié)點為條目t
子算法1 CreateTree(v, Gg, T)1: T=&v;2: CreateTree(T->Ldata, Gg,T);3: CreateTree(T->Rdata, Gg, T);4: return SUCCESS;
(2)遍歷路徑樹：從根節(jié)點開始遍歷下一跳節(jié)點，節(jié)點遍歷自己的第一個下一跳節(jié)點，直到到達(dá)目的節(jié)點。在遍歷過程中，如果樹干上還有其他下一跳節(jié)點，則將其指向指針改為當(dāng)前樹干節(jié)點的下一跳節(jié)點。
子算法2 TraverseTree(T)1: 對于任一節(jié)點vi,下一跳節(jié)點集合為{vj1,vj2,…},下一跳個數(shù)為Ni2: TraverseTree(T)3: if T-> vj1, then4: TraverseTree(T-> vj1,)5: end if6: if T->vjn,n≠1 then7: for all n from 2 to Ni do8: T->Lchild->Rchild=T->vjn;9: T->Lchild->Rchild->Rdata = T-> ldata;10: if n≠Nithen11: T->Rchild=vi;12: else13: T->Rchild = NULL;14: end if15: TraverseTree(T->vjn)16: end for17: end if18:return SUCCESS;
(3)計算等級數(shù)：遍歷路徑樹，為節(jié)點計算并存儲等級數(shù)。
子算法3CalculateLevel(T, lev)1: lev = 1;2: CalculateLevel(T, lev)3: T->level=lev; 4: level(T->Lchlid, lev+1);//在左子樹中查找5: level(T->Rchild, lev+1);//在右子樹中查找6: return SUCCESS;
(4)優(yōu)化路徑樹：從最高等級開始，遍歷路徑樹，如果等級低的條目的Ldata和Rdata與等級高的條目相同，則等級低的條目可以合并到等級高的條目中去。
子算法4 OptimalTree(T)1: for all lev from L to 0 d2: for all ti , ti
(5)時隙調(diào)度：根據(jù)優(yōu)化路徑樹，為數(shù)據(jù)傳輸?shù)逆溌贩峙湎鄳?yīng)的時隙，等級相同的條目可以共享同一時隙。其中，超幀長度為lF，Si記錄節(jié)點的調(diào)度信息。
子算法5ScheduleLink(T, lev, F)1: lev=1;2: ScheduleLink(T, lev, F)3: if T->Lchild != NULL then4: 將時隙k*lF+ASN+lev分配給ST->Ldata和SR->Lchild->Ldata//ASN為該傳輸在超幀中的偏移量5: end if6: ifT->Rchild != NULL then7: 將時隙k*lF+ASN+lev分配給ST->Rdata和SR->Rchild->Rdata8: end if9: ScheduleLink(T->Lchild, lev+1, F) //遍歷左子樹10: ScheduleLink(T->Rchild, lev+1, F) //遍歷右子樹11: return SUCCESS;
4 仿真結(jié)果
本節(jié)通過MATLAB仿真平臺實現(xiàn)多路徑傳輸調(diào)度算法，并通過NS-2仿真平臺完成網(wǎng)絡(luò)通信性能的仿真，仿真對比了重傳模式和復(fù)制模式下多路徑資源調(diào)度方案的可靠性、實時性和通信開銷。實驗選擇了由100個節(jié)點組成的工業(yè)無線傳感器網(wǎng)絡(luò)，網(wǎng)絡(luò)深度為8(網(wǎng)絡(luò)深度為所有節(jié)點中最大的網(wǎng)絡(luò)等級值)，節(jié)點的網(wǎng)絡(luò)等級值平均為3.94。實驗過程為網(wǎng)絡(luò)中的100個節(jié)點都產(chǎn)生一個數(shù)據(jù)包，然后將數(shù)據(jù)包發(fā)送給集中控制器，路由圖由算法1生成，傳輸成功率參數(shù)rd設(shè)為0.96，復(fù)制模式和重傳模式下鏈路度量的計算方式不同，實驗結(jié)果為1000次實驗的平均值。
圖5顯示了鏈路傳輸成功率從50%增加到90%的情況下，兩種調(diào)度方案數(shù)據(jù)包成功到達(dá)集中控制器的概率。在采用同樣的傳輸成功率參數(shù)rd的情況下，復(fù)制模式的數(shù)據(jù)傳輸成功率高于重傳機(jī)制，尤其是在鏈路傳輸成功率低的情況下，復(fù)制模式的數(shù)據(jù)傳輸成功率大大高于重傳機(jī)制。復(fù)制模式以其數(shù)據(jù)的冗余性，提高了數(shù)據(jù)包到達(dá)集中控制器的概率。
圖5 不同路由容錯機(jī)制的數(shù)據(jù)傳輸成功率
圖6顯示了鏈路傳輸成功率從50%增加到90%的情況下，兩種調(diào)度方案所需要的時隙數(shù)目，復(fù)制模式所需要的時隙數(shù)也小于重傳機(jī)制。這一方面是由于廣播通信模式下資源的共享效率更高，從而減少調(diào)度所需的時隙數(shù)目；另一方面是由于相同的傳輸成功率參數(shù)，復(fù)制模式需要更少的下一跳，從而減少了需要調(diào)度的鏈路數(shù)目。
圖6 不同路由容錯機(jī)制的調(diào)度時隙數(shù)
對比數(shù)據(jù)傳輸成功率和調(diào)度時隙數(shù)這兩個參數(shù)，復(fù)制模式都優(yōu)于重傳模式。然而，數(shù)據(jù)包傳輸過程中采用廣播模式會造成網(wǎng)絡(luò)中數(shù)據(jù)的大量冗余。圖7對比了兩種模式一次數(shù)據(jù)匯聚過程的鏈路通信次數(shù)，其中復(fù)制模式的鏈路通信次數(shù)大大高于重傳模式。大量的通信次數(shù)造成節(jié)點的計算量增大，節(jié)點緩存數(shù)據(jù)包的增多，節(jié)點能量消耗的增加，從而影響網(wǎng)絡(luò)性能。兩種路由容錯制機(jī)制在不同的性能方面各有優(yōu)劣，因此，在網(wǎng)絡(luò)實際部署時，集中控制器可以根據(jù)不同的網(wǎng)絡(luò)需求采用不同的容錯機(jī)制。
圖7 不同路由容錯機(jī)制的鏈路通信次數(shù)
5 結(jié) 語
本文討論了無線傳感器網(wǎng)絡(luò)中多路徑傳輸時延優(yōu)化的重要性，考慮了跨層調(diào)度的必要性，描述了兩種路由容錯機(jī)制的區(qū)別，并針對不同的容錯機(jī)制提出了兩種不同的調(diào)度方案。兩種方案均通過鏈路共享時隙資源的方式提高資源的利用率，減少調(diào)度所需的時隙數(shù)目，從而降低數(shù)據(jù)包傳輸?shù)臅r延。實驗結(jié)果證明，采用相同的傳輸成功率參數(shù)復(fù)制模式的數(shù)據(jù)傳輸成功率較高且調(diào)度所需的時隙數(shù)目較少，但是增大了鏈路通信次數(shù)，從而帶來了冗余的數(shù)據(jù)包，增加了網(wǎng)絡(luò)負(fù)載。因此，在實際部署情況下，可以根據(jù)網(wǎng)絡(luò)的實際需求和應(yīng)用場景[20]采用不同的路由容錯機(jī)制。
