代碼分發(fā)協(xié)議中的自適應機制研究

顧俊卿，施偉斌，余俊男，榮佳樂

（上海理工大學 光電信息與計算機工程學院，上海 200093）

0 引言

無線傳感器網(wǎng)絡（Wireless Sensor Networks，WSN）末梢擁有數(shù)以萬計可以感知和檢查外部世界的傳感器，可通過無線通信的方式形成自組織網(wǎng)絡，現(xiàn)已廣泛應用于智能電網(wǎng)、環(huán)境監(jiān)測、醫(yī)療護理等領域［1-4］。近年來，傳統(tǒng)WSN技術與云計算技術的結合［5］使其應用場景更加豐富。為應對現(xiàn)實場景中多變的需求，通過多跳自組織網(wǎng)絡遠程將新版本代碼從源節(jié)點分發(fā)到其他節(jié)點成為WSN 領域的一個重要課題。由于大規(guī)模部署的節(jié)點依靠干電池供電，為提高能量效率和延長網(wǎng)絡壽命，需研究如何以最小的能量及時間消耗實現(xiàn)可靠的代碼分發(fā)。

1 相關研究

數(shù)字噴泉碼是一種前向糾錯碼，因其具有輕量化的編解碼算法，現(xiàn)已被廣泛應用于WSN 中的批量數(shù)據(jù)傳輸［6］。例如，文獻［7］提出的SYNAPSE++是一種基于噴泉碼的代碼分發(fā)協(xié)議，采用混合自動重傳請求機制；文獻［8］在噴泉碼的基礎上提出一種加權在線噴泉碼，結合緩存占有率和已發(fā)送的編碼符號來估計恢復率，以此調整后續(xù)編碼符號的度；文獻［9］提出一種基于在線噴泉碼的無線廣播方案，通過接收節(jié)點的反饋信息更新編碼符號度；文獻［10-11］分別通過生成最小化差異補丁和使用網(wǎng)絡編碼的方式減少重編程過程中耗費的能量；文獻［12-13］分別提出基于自適應廣播半徑和鏈路質量的自適應代碼分發(fā)機制；文獻［14］設計了一種提前喚醒路由協(xié)議，路由路徑中的節(jié)點可以在節(jié)點發(fā)送數(shù)據(jù)包之前被喚醒。

WSN 所處的環(huán)境中通常存在與其共享2.4 GHz 頻段的其他無線設備，這種共存會導致WSN 中的數(shù)據(jù)傳輸受到干擾，因此當信道飽和導致系統(tǒng)性能下降時，通常采用跳頻或擴頻抗干擾技術改善。例如，文獻［15］提出一種基于接收信號強度的無線傳感器網(wǎng)絡跳頻通信機制；文獻［16］將傳感器節(jié)點與認知無線電節(jié)點結合起來，利用許可信道將傳感器數(shù)據(jù)路由到匯點，提高了網(wǎng)絡吞吐量；文獻［17］提出的HM-MAC 協(xié)議在鄰居節(jié)點間根據(jù)信號與干擾加噪聲比建立空閑信道表，并篩選出最優(yōu)數(shù)據(jù)信道集合以供選擇；文獻［18］將通信信道分為普通信道和數(shù)據(jù)信道，節(jié)點通過在普通信道偵聽鄰居節(jié)點所發(fā)送的清除消息中包含的信道信息確定空閑的數(shù)據(jù)信道編號。然而，上述方法應用于代碼分發(fā)會產(chǎn)生大量與鄰居節(jié)點的通信開銷，且會增加原有代碼分發(fā)協(xié)議的復雜度。

為提高抗信道干擾能力，本文提出一種基于噴泉碼的代碼分發(fā)協(xié)議自適應機制。在文獻［19］方法的基礎上對動態(tài)冗余機制進行改進，并添加多信道機制。實驗結果表明，在存在干擾的環(huán)境中，通過增加自適應機制可使通信量以及分發(fā)時間明顯減少。

2 冗余長度自適應調整

SYNAPSE++中的噴泉碼編碼包冗余長度為固定值，只有在特定信道條件下（對應丟包率為q）才具有最小通信量。當信道質量下降，丟包率明顯高于q時，接收節(jié)點解碼成功率顯著降低，需要通過大量增量傳輸（重新發(fā)送數(shù)據(jù)分塊）實現(xiàn)成功解碼，導致通信量上升、節(jié)點能耗增加。因此，以下將分析動態(tài)冗余長度條件下的數(shù)據(jù)通信量，并給出根據(jù)丟包率選取最佳冗余長度的方法。

2.1 動態(tài)冗余長度條件下的數(shù)據(jù)通信量分析

為適應動態(tài)變化的信道條件，每輪分發(fā)前接收節(jié)點計算上一輪分發(fā)的丟包率，據(jù)此選取最佳編碼包冗余長度δo以獲得最小通信量，并將δo反饋給sink 節(jié)點，sink 節(jié)點選取δo中的最大值作為下一輪分發(fā)的冗余長度，以此增加鏈路質量較差節(jié)點的解碼成功率。不同丟包率q對應的最佳冗余長度將通過以下公式推導以及仿真得到。

2.1.1 首輪分發(fā)傳輸數(shù)據(jù)量的期望值

設一輪分發(fā)中數(shù)據(jù)分塊的源數(shù)據(jù)包數(shù)量為K個，δ為可變的冗余長度，F(xiàn)（1）為首輪解碼成功的概率均值估計。P｛X=i｝=C（K+R，i）（1-q）iqK+R-i為接收到i個編碼包的概率，q為丟包率，Ψ（i）為首輪接收到i個編碼包后解碼成功的概率，此處的Ψ（i）以及以下部分的Ψ 函數(shù)均按照SYNAPSE++協(xié)議的編解碼算法［7］通過仿真得到近似值。

E（C1）為傳輸數(shù)據(jù)量的期望值，其中NB為分塊數(shù)量，編碼包中的數(shù)據(jù)量為X字節(jié)。

2.1.2 增量傳輸后傳輸數(shù)據(jù)量的期望值

當首輪分發(fā)解碼失敗后，需要增量傳輸使得節(jié)點接收到足夠數(shù)量的編碼包后才能解碼成功。兩輪內(nèi)成功解碼的概率均值為：

增量傳輸后，接收的數(shù)據(jù)量超出數(shù)據(jù)緩存大小B，超出的數(shù)據(jù)會覆蓋緩存內(nèi)的數(shù)據(jù)，意味著冗余長度的錯誤估計會導致非必要的通信開銷。為此，本文采用按需分發(fā)策略，發(fā)送節(jié)點根據(jù)丟包率和緩存空間容量確定每次分發(fā)的數(shù)據(jù)包長度。Θ（x）為丟包率q條件下增量編碼包長度的估計。表示為：

式（5）、式（6）分別為增量傳輸?shù)木幋a包數(shù)量期望值以及兩輪傳輸數(shù)據(jù)量的期望值。表示為：

當產(chǎn)生第二輪增量傳輸后，3 輪傳輸內(nèi)解碼成功的概率均值估計為：

式（8）、式（9）分別為第二輪增量傳輸?shù)木幋a包數(shù)量期望值以及3輪傳輸數(shù)據(jù)量的期望值。表示為：

當存在n個節(jié)點時，經(jīng)過r輪分發(fā)能夠成功解碼的概率為F（r）n，則在第r輪成功解碼的概率為F（r）n-F（r-1）n，r≥1。令F（0）=0，在整個分發(fā)過程中，傳輸數(shù)據(jù)量C的期望值近似為：

2.2 最佳冗余長度選取

為得到不同冗余長度通信量隨丟包率變化的規(guī)律，并確定特定信道條件下使數(shù)據(jù)通信量最小的最佳冗余長度，本文利用上述公式進行了仿真，結果見圖1?？梢钥闯?，不同冗余長度δ在不同信道條件下的性能有所差異，當丟包率由0 開始逐漸增大時，較小的δ對應的數(shù)據(jù)通信量快速增加，而較大的δ對應的數(shù)據(jù)通信量隨丟包率變化得比較緩慢。當丟包率增大到一定程度時，較小的δ對應的數(shù)據(jù)通信量隨著丟包率的增加逐漸趨于近似線性變化，而較大的δ對應的數(shù)據(jù)通信量隨丟包率變化的斜率逐漸增大。

Fig.1 Simulation result圖1 仿真結果

圖2 為丟包率p∈（0，0.3］時的最佳冗余長度δo，當p∈（0.2，0.3］，δo不再上升，維持在18 后又快速下降至2。這是由于受到緩存空間大小的限制，無法再提供更大的冗余長度，若不考慮緩存空間，則δo應有持續(xù)上升的趨勢。

Fig.2 The optimal redundancy length圖2 最佳冗余長度

2.3 動態(tài)冗余長度機制實現(xiàn)

現(xiàn)有代碼分發(fā)協(xié)議SYNAPSE++采用ADV、REQ、DATA 3 種消息類型，一輪分發(fā)的時間被分為3 個固定時隙分別收發(fā)這3 種消息。發(fā)送節(jié)點通過廣播ADV 消息告知鄰居節(jié)點當前已有的數(shù)據(jù)分塊信息，鄰居節(jié)點接收到ADV消息后向其申請某一數(shù)據(jù)分塊，發(fā)送節(jié)點將數(shù)據(jù)分塊編碼后發(fā)出。為能根據(jù)當前信道質量自適應調整冗余長度，接收節(jié)點將根據(jù)上一輪傳輸計算實時丟包率，據(jù)此選取最佳冗余長度δo，并添加于REQ 消息中反饋給發(fā)送節(jié)點。發(fā)送節(jié)點統(tǒng)計所有鄰居節(jié)點REQ 消息中的δo，取其中的最大值以提高鏈路質量較差節(jié)點的解碼成功率，進而減少增量傳輸，提高分發(fā)效率。

3 多信道機制

當WSN 遭受嚴重信道干擾，例如丟包率大于15%時，采用冗余長度的自適應調整機制仍然會產(chǎn)生大量冗余編碼包的傳輸，并且分發(fā)時間也會顯著增加，因此在抗干擾能力上具有一定的局限性。為此，本文進一步提出代碼分發(fā)的多信道機制，將通信信道分為控制信道和數(shù)據(jù)信道，當受到嚴重干擾時，通過更換數(shù)據(jù)信道避免持續(xù)的增量傳輸。

3.1 外部干擾與WSN信道配置

由于WSN 與其他無線設備共同工作于2.4 GHz 頻段，該頻段下存在ZigBee、WIFI、Bluetooth 等多個標準，因此WSN 易受到采用這些標準的無線設備的干擾，其中最為典型的干擾來自WLAN 設備［20］。本節(jié)主要討論WSN 如何有效避免來自WLAN 的干擾。

圖3為WSN信道與WLAN信道示意圖。WSN信道的帶寬為2 MHz，中心頻率間隔為5 MHz；參照IEEE802.11n［21］標準，WLAN 信道常用帶寬為20 MHz。在2.4～2.483 5 GHz 頻率范圍內(nèi)，WSN 的11-25 信道與WLAN 的1-13 信道重疊，WLAN 的14 信道在中國并未授權使用，且WLAN 的13 信道中心頻率為2 472 MHz，對中心頻率為2 480 MHz 的26信道干擾較?。?2］，因此WSN 的26信道具有較高的可靠性。

Fig.3 WSN channels and WLAN channels圖3 WSN信道與WLAN信道示意圖

分發(fā)協(xié)議的多信道機制采用固定控制信道結合可切換數(shù)據(jù)信道的方式，將26 信道作為控制信道，用于傳輸ADV、REQ 信息；11-25 信道作為可用的數(shù)據(jù)收發(fā)信道，數(shù)據(jù)收發(fā)階段結束后從數(shù)據(jù)信道切換回控制信道。假設當前WSN 的數(shù)據(jù)信道為n，受到工作于同一頻段的WLAN 設備Xs 的干擾，導致傳輸效率顯著下降時，則切換至n+4，跳出Xs 當前信道的頻率覆蓋范圍。為提高信道利用率并降低多信道協(xié)議的復雜度，數(shù)據(jù)信道將以WLAN 信道的帶寬為間隔在11-25 信道循環(huán)切換。例如，當數(shù)據(jù)信道為11 信道，數(shù)據(jù)的收發(fā)受到工作于信道1 的WLAN 設備干擾時，則數(shù)據(jù)信道切換至15 信道避免干擾；若依舊存在較強干擾，則繼續(xù)更換數(shù)據(jù)信道。以上針對WLAN 信道所設計的多信道機制可使WSN 有效避開WLAN 干擾。

3.2 更換數(shù)據(jù)信道的條件

確定更換信道的條件需綜合考慮通信量、分發(fā)時間和系統(tǒng)存儲空間的限制。隨著丟包率的上升，通信量和分發(fā)時間相應增加。圖4 為分發(fā)時間隨丟包率變化的情況，可以看出當丟包率大于10%時，分發(fā)時間隨丟包率上升的斜率明顯增大。系統(tǒng)數(shù)據(jù)存儲器的空間限制了冗余包數(shù)量的最大值，因此本文將更換數(shù)據(jù)信道的條件設置為丟包率p≥0.14，對應于通信量增加超過50%（相對于p=0 時），即當連續(xù)兩輪傳輸?shù)膩G包率皆超過閾值（14%）且后一輪的丟包率高于前一輪時，則切換數(shù)據(jù)信道。例如，設某一接收節(jié)點第n輪分發(fā)的丟包率為PLRn（n≥1），n+1 輪分發(fā)的丟包率為PLRn+1，當PLRn+1>PLRn>14%時，接收節(jié)點將REQ 消息負載中的信道切換標志位，sink 節(jié)點接收到REQ 消息后將廣播新的數(shù)據(jù)信道編號，并切換至該信道進行第n+2 輪的分發(fā)。

Fig.4 Mean of dissemination time corresponding to packet lost rate圖4 分發(fā)時間均值隨丟包率變化的情況

3.3 多信道分發(fā)協(xié)議

基于上述原理，本文設計了一種多信道代碼分發(fā)協(xié)議（Dynamic Redundancy and Multi-channel，DRD&MCN），并在TinyOS 中實現(xiàn)了該協(xié)議。為實現(xiàn)網(wǎng)絡在控制信道與數(shù)據(jù)信道間的切換，增加消息類型SW，該消息負載的內(nèi)容為需切換的信道編號。多信道的代碼分發(fā)過程如圖5所示。

Fig.5 Multi-channel code distribution process圖5 多信道代碼分發(fā)過程

接收節(jié)點完成編碼包的接收后，計算上一輪圖5 分發(fā)的丟包率并完成信道決策，置位或復位REQ 消息的信道切換標志位，sink 節(jié)點統(tǒng)計收到的REQ 消息后，廣播SW 消息使接收節(jié)點切換至指定數(shù)據(jù)信道接收DATA 包。為保證接收節(jié)點能及時切換回控制信道接收ADV 消息，獲取其中的時間戳，完成與sink 節(jié)點的時間同步。傳輸完成后，sink 節(jié)點再次廣播SW 消息切換回控制信道，若未收到SW消息，則會在數(shù)據(jù)傳輸階段結束后切換回控制信道。

4 實驗結果與分析

4.1 動態(tài)冗余機制在實際環(huán)境中的性能

實驗采用以CC2430 為核心的硬件平臺運行SYNAPSE++以及改進后的代碼分發(fā)協(xié)議，CC2531 作為偵聽節(jié)點偵聽WSN 信道中的消息包。實驗環(huán)境為上海理工大學光電大樓9 樓的辦公區(qū)域，平面示意見圖6。分別將sink節(jié)點、偵聽節(jié)點以及5 個接收節(jié)點布置于該環(huán)境中，由一臺路由器以及兩臺PC 機組成WLAN。

Fig.6 Sketch map of experimental environment圖6 實驗環(huán)境平面示意圖

為驗證“2.3”節(jié)仿真的可靠性，在實驗室隨機的信道環(huán)境中進行實驗，分別選取不同冗余長度進行3 次實驗，實測值與仿真值比較見圖7，其中曲線圖與柱狀圖分別為不同分塊冗余長度對應的平均傳輸數(shù)據(jù)量和丟包率。可以看出，實測數(shù)值與仿真值較為接近，驗證了理論分析的正確性。

Fig.7 Comparison of experiment and simulation results圖7 實測值與仿真值比較

設置代碼分發(fā)協(xié)議工作在與WLAN 信道頻段重疊的WSN 信道上進行，通過iperf［23］控 制WLAN 中UDP（User Datagram Protocol）流的帶寬以對WSN 產(chǎn)生不同程度干擾。在相同實驗條件下分別測試SYNAPSE++協(xié)議以及添加自適應動態(tài)冗余長度機制的代碼分發(fā)協(xié)議（Dynamic Redundancy，DRD），從總通信量大小以及分發(fā)時間兩個方面考察兩者在不同強度信道干擾下的性能，將分發(fā)過程的平均丟包率作為信道干擾強度的度量值。圖8、圖9 分別為總通信量和分發(fā)時間的比較結果?？梢钥闯?，隨著丟包率的上升，動態(tài)冗余機制使通信量與分發(fā)時間顯著減少，當丟包率p∈（0.10，0.15］時，通信量與分發(fā)時間分別平均減少了20.45%和37.39%。DRD 協(xié)議根據(jù)實時計算的丟包率以及剩余緩存容量選擇最佳編碼包冗余長度，因此即使存在信道干擾也能以相對較少的冗余開銷提升接收節(jié)點的解碼成功率，避免過多的增量傳輸，提升了分發(fā)效率。

Fig.8 Comparison of traffic圖8 總通信量比較

Fig.9 Comparison of dissemation time圖9 分發(fā)時間比較

當信道環(huán)境惡劣時，DRD 協(xié)議會通過使接收節(jié)點向發(fā)送節(jié)點申請更多冗余編碼包的方式抵抗信道干擾，但這同樣會導致通信量大幅上升，分發(fā)效率降低。如圖9 和圖10所示，當丟包率p∈（0.15，0.20］時，DRD 協(xié)議相比SYNAPSE++減少了14.78%的通信量，分發(fā)時間減少了6.39%，但相比丟包率p∈（0，0.03］的情況，通信量增加了84.09%，分發(fā)時間增加了189.88%?？梢娫趤G包率過高時，動態(tài)冗余機制性能有所下降。

Fig.10 Comparison of code dissemination traffic圖10 總通信量比較

4.2 多信道機制在實際環(huán)境中的性能

為考察結合動態(tài)冗余與多信道機制的代碼分發(fā)協(xié)議DRD&MCN 的性能，在圖6 實驗環(huán)境中進行測試。使用4臺PC 與兩臺路由器組成兩個WLAN，以此對WSN 的11-22 信道形成干擾。如圖10 和圖11 所示，當丟包率p∈（0，0.10］時，DRD&MCN 與DRD 的總通信量相差不超過6.98%，分發(fā)時間相差不超過16.09%。由于分發(fā)過程平均丟包率未超過設定閾值，引起信道切換的次數(shù)較少，動態(tài)冗余機制在抵抗信道干擾中起主要作用，兩者總通信量與分發(fā)時間差距較小。當丟包率p∈（0.10，0.25］時，此時超過了預設閾值，因此數(shù)據(jù)信道通過3 次更換從11 信道切換至空閑的23 信道，DRD&MCN 相較DRD 和SYNAPSE++總通信量平均分別減少了42.58%和53.08%，分發(fā)時間平均分別減少了59.89%和64.05%。由于23 信道未受到干擾，因此切換至該信道后，總通信量和分發(fā)時間較為穩(wěn)定，且顯著少于另外兩種協(xié)議，說明多信道機制可有效避免在受干擾嚴重的信道中持續(xù)進行數(shù)據(jù)分發(fā)的情況。

Fig.11 Comparison of dissemation time圖11 分發(fā)時間比較

5 結語

本文對代碼分發(fā)協(xié)議的自適應機制進行研究，提出一種動態(tài)冗余長度與多信道機制相結合的方法，根據(jù)受干擾程度分別采用動態(tài)冗余機制和多信道機制減小干擾影響。實驗結果表明，在存在干擾的條件下，與現(xiàn)有分發(fā)協(xié)議相比，本文方法可使通信量與分發(fā)時間顯著減少，有效提高了分發(fā)效率，有利于延長WSN 的生存時間。

動態(tài)冗余機制的原理是通過計算上一輪傳輸?shù)膩G包率選取最佳編碼包冗余長度，雖然當前節(jié)點成功解碼該輪傳輸?shù)木幋a包，但是之后發(fā)送節(jié)點還為其他節(jié)點提供了數(shù)輪增量傳輸，即當前節(jié)點計算的丟包率反映的并不是當前時刻的信道狀況，這會導致選擇的冗余長度并不匹配當前鏈路質量，進而造成不必要的增量傳輸。后續(xù)可考慮建立不同丟包率下的通信參數(shù)數(shù)據(jù)集，通過機器學習算法建立模型估計鏈路質量。該方法不需要探測包，具有更高的實時性。