代碼分發協議中的自適應機制研究

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

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

0 引言

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

1 相關研究

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

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

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

2 冗余長度自適應調整

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

2.1 動態冗余長度條件下的數據通信量分析

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

2.1.1 首輪分發傳輸數據量的期望值

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

E（C1）為傳輸數據量的期望值，其中NB為分塊數量，編碼包中的數據量為X字節。

2.1.2 增量傳輸后傳輸數據量的期望值

當首輪分發解碼失敗后，需要增量傳輸使得節點接收到足夠數量的編碼包后才能解碼成功。兩輪內成功解碼的概率均值為：

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

式（5）、式（6）分別為增量傳輸的編碼包數量期望值以及兩輪傳輸數據量的期望值。表示為：

當產生第二輪增量傳輸后，3 輪傳輸內解碼成功的概率均值估計為：

式（8）、式（9）分別為第二輪增量傳輸的編碼包數量期望值以及3輪傳輸數據量的期望值。表示為：

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

2.2 最佳冗余長度選取

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

Fig.1 Simulation result圖1 仿真結果

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

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

2.3 動態冗余長度機制實現

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

3 多信道機制

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

3.1 外部干擾與WSN信道配置

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

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

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

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

3.2 更換數據信道的條件

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

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

3.3 多信道分發協議

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

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

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

4 實驗結果與分析

4.1 動態冗余機制在實際環境中的性能

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

Fig.6 Sketch map of experimental environment圖6 實驗環境平面示意圖

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

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

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

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

Fig.9 Comparison of dissemation time圖9 分發時間比較

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

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

4.2 多信道機制在實際環境中的性能

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

Fig.11 Comparison of dissemation time圖11 分發時間比較

5 結語

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

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