代碼分發(fā)協(xié)議中最優(yōu)分塊冗余長度的研究

代碼分發(fā)協(xié)議中最優(yōu)分塊冗余長度的研究

王宇波，施偉斌，和夢琪，樂燕芬(上海理工大學光電信息與計算機工程學院，上海200093)1引言無線傳感器網(wǎng)絡(WSN，WirelessSensorNetwork)是物聯(lián)網(wǎng)(IoT，InternetofThings)的重要組成部分，近年來得到了廣泛的應用[1-3].對于大規(guī)模部署的WSN，通過分發(fā)協(xié)議更新軟件能夠顯著減少系統(tǒng)維護的工作量[4].由于大量WSN節(jié)點以電池供電，如何提高通信效率是代碼分發(fā)協(xié)議設計面臨的挑戰(zhàn)[5，6]，不合理的冗余分組設置、環(huán)境干擾導致的非必要冗余數(shù)據(jù)傳輸和數(shù)據(jù)重傳，是影響分發(fā)協(xié)議效率的主要因素.自動重傳請求[7](ARQ，AutomaticRepeatreQuest)和前向糾錯編碼[8](FEC，F(xiàn)orwardErrorCorrection)是分發(fā)協(xié)議中實現(xiàn)可靠傳輸?shù)膬煞N常用技術.TinyOS中的Deluge協(xié)議[9]是典型的使用ARQ的代碼分發(fā)協(xié)議，由于存在較高的控制消息開銷，當節(jié)點數(shù)量增加或鏈路質量下降時，分發(fā)效率較低.噴泉碼[10]屬于前向糾錯編碼，該編碼具有無碼率的特點，控制消息的開銷較低，且擁有輕量化編解碼算法[11].通信雙方可以完全忽視信道刪除帶來的影響，因此基于噴泉碼的代碼分發(fā)協(xié)議通常有較高的魯棒性.FRP協(xié)議[12]和SYNAPSE協(xié)議[13]均使用噴泉碼作為編碼方案，在分塊傳輸結束后SYNAPSE協(xié)議設計了錯誤恢復階段，利用增量冗余分組使節(jié)點從錯誤中恢復過來.SYNAPSE++協(xié)議[14]對于傳輸每個分塊使用固定數(shù)量的編碼分組，即引入固定分塊冗余長度，在典型分組丟失率(PLR，PacketLossRate)條件(10%)下，某分塊經(jīng)過一次傳輸后，接收節(jié)點可獲得80%以上的解碼成功率.但SYNAPSE++協(xié)議中固定分塊冗余長度的方案在鏈路質量較差的條件下會導致大量增量傳輸，從而使分發(fā)效率下降.為了減少分發(fā)數(shù)據(jù)量，一些協(xié)議采用差異分發(fā)的方法，即僅分發(fā)新舊代碼鏡像文件之間的區(qū)別部分，如Incremental協(xié)議[15]和TinyCubus協(xié)議[16].文獻[17]提出了一種新的差異編譯技術，通過在重編譯時將差異代碼打包為增量腳本，以獲得區(qū)別更小的差異鏡像.但通常由于舊指令存儲地址連續(xù)，為了避免覆蓋，插入新指令將引入大量Flash讀寫操作，從而導致開銷急劇增加.利用網(wǎng)絡編碼可以有效提高網(wǎng)絡吞吐量，提高分發(fā)效率[18]，中繼節(jié)點可以無代價地將分組轉發(fā)至下一跳節(jié)點.但當缺少中繼節(jié)點間的協(xié)調機制時，可能導致過量冗余數(shù)據(jù)傳輸，進而造成分發(fā)效率降低.王開云等人[19]對可靠廣播/多播理論中概率分布函數(shù)進行了近似化處理，得到求解單組數(shù)據(jù)期望重傳次數(shù)的高精度近似公式，有助于廣播/多播系統(tǒng)精確控制單組數(shù)據(jù)播發(fā)次數(shù)，提高系統(tǒng)效率.祝峰等人[20]基于3種可靠多播方案，在考慮分組頭開銷的條件下，提出確定滿足最少傳輸時間的最佳有效負載長度的方法.其中基于LT噴泉碼的多播方案因其可以有效抵抗分組丟失產(chǎn)生的影響而具有最優(yōu)性能.本文主要研究基于噴泉碼的代碼分發(fā)協(xié)議中最優(yōu)分塊冗余長度的選取方法，理論分析和實驗驗證結果顯示，滿足最小通信量條件的分塊冗余長度δm應根據(jù)分組丟失率大小合理選取.在典型室內(nèi)干擾條件下，δm與分組丟失率呈正相關，當分組丟失率上升時，增大分塊冗余長度能減小分發(fā)過程的數(shù)據(jù)通信量.在此基礎上，將自適應調整分塊冗余長度的機制引入現(xiàn)有的代碼分發(fā)協(xié)議，實驗結果表明，通過動態(tài)調整分塊冗余長度能明顯提高分發(fā)效率.2最優(yōu)分塊冗余長度的研究SYNAPSE++協(xié)議是唯一源代碼公開的、完整實現(xiàn)并可以在實際WSN中運行的基于噴泉碼的代碼分發(fā)協(xié)議.實驗結果顯示，該協(xié)議在不同信道條件下，數(shù)據(jù)通信量變化范圍較大，不同規(guī)模的網(wǎng)絡在運行SYNAPSE++協(xié)議時的通信量變化情況如圖1所示.由圖1可以看出隨著網(wǎng)絡中節(jié)點數(shù)量的增加，分發(fā)數(shù)據(jù)量的均值變化幅度比較平緩.然而對于特定規(guī)模的網(wǎng)絡，重復進行的實驗在通信量方面差別卻可能非常顯著，例如節(jié)點數(shù)量為6(不包括Sink節(jié)點)的網(wǎng)絡，最大數(shù)據(jù)通信量比最小數(shù)據(jù)通信量增加了約44%.通信量的增加是由編碼分組的增量傳輸引起的，在分發(fā)過程中，編碼分組會因存在干擾而丟失，導致不同程度的解碼成功率降低，從而引起相應的增量傳輸，最終造成數(shù)據(jù)通信量大幅度波動.下面首先對解碼成功率與分組丟失率的關系進行分析，然后給出確定最優(yōu)分塊冗余長度的方法.2.1分組丟失率對解碼成功率的影響分析設某分塊劃分為K個源數(shù)據(jù)分組，對接收節(jié)點而言，經(jīng)過一次分發(fā)能正確解碼的概率為[14]：(1)為了得到ψ(K+δ-ξ)近似值，按照SYNAPSE++協(xié)議的編解碼算法，使用不同δ取值進行了一系列仿真計算，求得每個ψ(K+δ-ξ)所進行的計算次數(shù)為10000次(使用更大計算次數(shù)得到的結果與圖2中結果之間的誤差可忽略不計).為了便于將上述仿真結果與實際中SYNAPSE++協(xié)議的實驗結果進行對比驗證，取K=32.圖2所示為部分ψ(K+δ-ξ)的計算結果.從圖2可以看出在ξ=5時，分塊冗余長度δ從5增大到8，ψ(K+δ-ξ)將從31.7%提高到89.6%.而在ξ=1時，分塊冗余長度δ從5減小為2，ψ(K+δ-ξ)由97.9%減少為76.7%.因此，存在少量編碼分組丟失時，使用較小的分塊冗余長度δ即可獲得較大的解碼成功率；當編碼分組丟失數(shù)量增大時，相應增大δ能消除編碼分組丟失導致的解碼成功率下降.將ψ(K+δ-ξ)的計算結果帶入到公式(1)中，可以得出在任意給定分組丟失率條件下，一個分塊單次分發(fā)可被接收節(jié)點正確解碼的概率.圖3所示為通過公式(1)計算出的單次傳輸時接收節(jié)點正確解碼的概率與分組丟失率的關系，可以看出在相同分組丟失率情況下，增大δ能夠使單次傳輸接收節(jié)點正確解碼的概率具有較顯著地提升.分塊冗余長度的大小與分發(fā)過程數(shù)據(jù)通信量密切相關，減小分塊冗余長度能減少傳輸數(shù)據(jù)量，但在鏈路質量較差時容易引起較多的增量傳輸；增大分塊冗余長度能提高單次傳輸解碼成功率，但過量的冗余數(shù)據(jù)傳輸可能導致分發(fā)效率下降.下面通過分析給出計算數(shù)據(jù)通信量的方法.2.2數(shù)據(jù)通信量的分析及驗證由公式(1)可得到某分塊解碼失敗概率為：(2)由于節(jié)點存儲資源有限，在實現(xiàn)代碼分發(fā)協(xié)議時通常會設置緩存編碼分組的數(shù)量上限J，如SYNAPSE++協(xié)議中J=50.當對一個分塊首次解碼失敗后，在接收該分塊后續(xù)編碼分組的過程中，如果接收數(shù)量達到J，則后續(xù)收到的分組將覆蓋已接收到的分組.當分組丟失率處于一定范圍內(nèi)(例如≤20%)，每次增量傳輸后，接收到的編碼分組總數(shù)都能達到J.假定所有接收節(jié)點相互獨立，對于某分塊，經(jīng)過g輪分發(fā)可以成功解碼的概率為：(3)其中qr(δr，p)為分發(fā)次數(shù)大于1時某分塊解碼失敗的概率，δr為分發(fā)次數(shù)大于1時對應的分塊冗余長度，δr=J-K，N為接收節(jié)點數(shù)量.為便于計算，同時利用噴泉碼無碼率的特點，取qr(δr，p)≈qs(δr，p)，則公式(3)成為：PR′(g)=(1-qs(δ，p)×qs(δr，p)(g-1))N(4)該分塊在第g輪解碼成功的概率為：P{G=g}=PR′(g)-PR′(g-1)(5)則為了保證可靠傳輸，該分塊被傳輸次數(shù)T的期望可表示為：(6)設代碼鏡像文件大小為F，分塊大小為M，分組長度為L.在整個分發(fā)過程中，傳輸數(shù)據(jù)量C的期望值為：(7)則可定義最優(yōu)分塊冗余長度為：(8)由于ψ(K+δ-ξ)與度分布函數(shù)相關，且無法得到其確切表達式，因此由公式(7)得出最優(yōu)分塊冗余長度δm的解析式較困難，可以通過仿真計算的方法確定最優(yōu)分塊冗余長度的取值.圖4(a)、圖4(b)兩圖顯示了由公式(7)得到的在不同分塊冗余長度條件下分發(fā)過程傳輸數(shù)據(jù)量期望值E(C)與分組丟失率的關系，其中圖4(a)為K=32時公式(7)的計算結果，圖4(b)為K=48時公式(7)的計算結果.在計算中取PR′(g)≥0.999，近似代替可靠分發(fā)，由此計算出保證可靠分發(fā)所需的最小輪數(shù)并帶入公式(7)中得出最終結果.仿真計算參數(shù)如表1所示(表中所有參數(shù)設置可在實際應用中調整).表1仿真計算使用的參數(shù)Table1Parametersusedinsimulationcalculation從圖4(a)、圖4(b)所示的仿真結果可知，不同分組丟失率條件下，滿足最小數(shù)據(jù)通信量的最優(yōu)分塊冗余長度δm取值不同.例如，對于K=32的情況(如圖4(a)所示)，當分組丟失率為15%時δm=9，而當分組丟失率為5%時δm=6.在分組丟失率為10%時，選用最優(yōu)分塊冗余長度δm=9分別比選用δ=1和δ=4減少了31.2%和21.5%的數(shù)據(jù)通信量.因此利用仿真計算方法，對于任意分組丟失率，總能找到滿足最小數(shù)據(jù)通信量的最優(yōu)分塊冗余長度δm.圖4K=32和K=48時E(C)與p的關系Fig.4RelationshipbetweenE(C)andpwhenK=32andK=48為了驗證了上述對δm取值計算的正確性，使用真實的節(jié)點運行SYNAPSE++協(xié)議，在實驗室中進行了實驗.通過改變代碼分發(fā)協(xié)議中分塊冗余長度，在室內(nèi)干擾環(huán)境中進行測試，統(tǒng)計分發(fā)過程中的數(shù)據(jù)通信量.實驗中使用無線局域網(wǎng)(WLAN，WirelessLocalAreaNetwork)數(shù)據(jù)傳輸對WSN進行干擾，設置WSN分組丟失率約為5%(±2%).圖5所示為實際環(huán)境中實驗結果與仿真結果對比，可以看出不同分塊冗余長度δ情況下的測量值與理論值基本相符，證明了上述理論分析結果的正確性.圖5驗證實驗結果與仿真結果對比Fig.5Comparisonofverificationexperimentresultsandsimulationresults2.3基于噴泉碼的分發(fā)協(xié)議的改進現(xiàn)有的基于噴泉碼的代碼分發(fā)協(xié)議在分發(fā)過程使用ADV-REQ-DATA范式，即首先由發(fā)送節(jié)點廣播ADV消息，告知鄰居節(jié)點當前代碼鏡像文件的分塊信息，然后接收節(jié)點發(fā)送REQ消息請求分發(fā).最后發(fā)送節(jié)點傳輸該塊鏡像.為實現(xiàn)分塊冗余長度的自適應調整，對現(xiàn)有系統(tǒng)進行如下修改.首先，在每個DATA分組(編碼分組)中加入序號，該序號在DATA分組成功發(fā)送后遞增1.接收節(jié)點根據(jù)收到DATA分組中序號計算實時分組丟失率.該分組丟失率將作為接收節(jié)點選取δm的參數(shù).由圖4(a)、圖4(b)所示的計算結果可得到在特定分組丟失率范圍內(nèi)滿足最小通信量的δm取值.接收節(jié)點在求出分組丟失率后，利用查表法得到對應的δm值，并將δm附加到REQ消息中，請求發(fā)送節(jié)點按照更新的冗余長度分發(fā)后續(xù)分塊.在分發(fā)開始前，由于接收節(jié)點無法得知當前環(huán)境的分組丟失率信息，因此δm的初值設為0.在分發(fā)過程中，發(fā)送節(jié)點可能收到來自不同接收節(jié)點的多個包含δm的REQ消息，此時發(fā)送節(jié)點取所有REQ消息中δm的最大值以保證處于較差鏈路上的節(jié)點的分發(fā)效率.節(jié)點解碼失敗時，將暫存此次解碼結果，并且請求該分塊的增量傳輸以便接收到足夠數(shù)量的編碼分組后再次嘗試解碼.由于存儲空間的限制，當接收到的編碼分組數(shù)量超過上限時，后續(xù)收到的分組會覆蓋已接收的冗余分組，導致分發(fā)效率降低，因此在接收節(jié)點請求增量傳輸前，應根據(jù)分組丟失率和緩存空間計算出所需的分塊冗余長度δ，然后通過REQ消息向發(fā)送節(jié)點請求.自適應選取最優(yōu)分塊冗余長度的算法偽代碼如算法1所示，其中δR表示接收節(jié)點存入REQ消息的分塊冗余長度.算法1.分塊冗余長度自適應選取算法隨著社會的發(fā)展變化，內(nèi)部審計的辦事方法也從傳統(tǒng)的書面文字改成了會計電算化形式，這樣一來企業(yè)的內(nèi)部審計工作就更加方便、快捷了。當審計信息化進程逐漸加快之時，也正是計算機成為內(nèi)部審計工作主流之勢。一旦企業(yè)內(nèi)部的審計工作可以逐漸被計算機審計功能替代，就會更加的節(jié)省時間，提高辦事效率，也能更加方便、快捷地跟其他企業(yè)的競爭對手相互對比，找出優(yōu)勢、劣勢從而更快地提高工作質量。更嚴謹?shù)貙ζ髽I(yè)資金及各種資產(chǎn)進行密切跟蹤、監(jiān)視，從而盡快地評估出企業(yè)風險的等級指數(shù)充分做好事前的準備工作，和事后的審計工作。1.whiledisseminationisnotover：2.requestablock；3.receiveencodedpacketsoftheblockandcalculatePLR；4.ifsuccessfullydecodetheblockthen5.selectδmfornextblockaccordingtoPLR；6.δR=δm；8.calculateδRforincrementaltransmission；9.endif10.putδRintoREQmessage；11.endwhile3實驗結果與分析為了測試自適應分塊冗余長度調整機制的性能，將SYNAPSE++協(xié)議及其改進版本和Deluge協(xié)議移植到以CC2430[21]為核心的平臺上，在本校光電樓內(nèi)的無線網(wǎng)絡實驗室和9樓辦公區(qū)域分別進行了實驗.實驗中，使用相同大小的可執(zhí)行代碼鏡像文件進行分發(fā)，文件大小38.6KB.所有實驗以各節(jié)點均正確完成代碼更新作為結束條件，并取5次實驗的平均值作為實驗結果.為便于敘述，將增加了分塊冗余長度調整機制的分發(fā)協(xié)議簡稱為FDP-VRL(Fountain-codebasedDisseminationProtocolwithVariableRedundancyLength).3.1實驗室內(nèi)的測試為了測試SYNAPSE++協(xié)議及本文提出的FDP-VRL在不同信道條件下的性能，使用WLAN數(shù)據(jù)傳輸對WSN代碼分發(fā)產(chǎn)生干擾.WLAN由兩臺PC機和一臺路由器組成，設置WLAN信道與WSN信道相互重疊，并通過改變WLAN速率來產(chǎn)生不同強度干擾，WLAN的通信速率通過jperf軟件控制.使用一個CC2531節(jié)點配合Sniffer軟件[22]偵聽WSN數(shù)據(jù)分組，并保存?zhèn)陕牻Y果用于后續(xù)分析.圖6為實驗環(huán)境示意圖.圖6在不同分組丟失率條件下實驗環(huán)境示意圖Fig.6ExperimentalenvironmentunderdifferentPLR在實驗室內(nèi)共進行兩組測試，分別將1個和2個代碼接收節(jié)點布置在如圖6的環(huán)境中.在配置1個接收節(jié)點的測試中，設置WSN節(jié)點分組丟失率分別為1%(±1%)、3%(±1%)、5%(±1%)、10%(±1%).圖7顯示了在不同分組丟失率條件下，SYNAPSE++與FDP-VRL在分發(fā)過程中傳輸?shù)木幋a分組數(shù)量對比，可以看出通過加入分塊冗余長度自適應選取機制，傳輸?shù)木幋a分組數(shù)量在1%的分組丟失率條件下減少了約12.1%.值得注意的是，在環(huán)境干擾變得更強時，F(xiàn)DP-VRL性能表現(xiàn)更優(yōu)，在分組丟失率為10%時傳輸數(shù)據(jù)分組數(shù)量比SYNAPSE++協(xié)議減少了14.8%.在第2組實驗中，將兩個傳感器節(jié)點分別放置在兩臺PC機附近，使兩個節(jié)點受到WLAN干擾盡可能相互獨立(如圖6所示)，分別設置3%(±2%)、10%(±2%)、20%(±2%)共3種不同的分組丟失率.測試結果如圖8所示.當分組丟失率較大時，SYNAPSE++協(xié)議完成單個分塊分發(fā)可能需要較多輪傳輸，而FDP-VRL能在首輪傳輸盡可能請求到足夠的編碼包，即使首輪傳輸后未能正確完成解碼，亦可在后續(xù)傳輸中按照自身接收情況選取合適的分塊冗余長度進行增量傳輸.FDP-VRL在20%的分組丟失率時傳輸數(shù)據(jù)分組數(shù)量相比SYNAPSE++協(xié)議減少了21.7%.3.2在實際環(huán)境中的性能圖9為9樓辦公區(qū)域的網(wǎng)絡部署示意圖，分別設置6個和10個節(jié)點進行兩組分發(fā)實驗，在相同條件下分別對Deluge、SYNAPSE++和FDP-VRL進行測試.辦公區(qū)域的每個辦公室中都設有WLAN路由器，與3.1節(jié)中所述專門設置的WLAN干擾相比，實際環(huán)境中WLAN數(shù)據(jù)傳輸多具有突發(fā)性.實驗中調整各個節(jié)點位置，使它們受干擾的情況盡可能相互獨立.圖10為實際環(huán)境中數(shù)據(jù)通信量的測試結果.由于Deluge協(xié)議中數(shù)據(jù)分組負載長度與基于噴泉碼的代碼分發(fā)協(xié)議不同，因此將分發(fā)過程傳輸數(shù)據(jù)分組的字節(jié)數(shù)量作為評價參數(shù).當使用10個節(jié)點時，F(xiàn)DP-VRL相對于SYNAPSE++減少了13.4%的數(shù)據(jù)通信量，相對于Deluge協(xié)議減少了36.6%的數(shù)據(jù)通信量.圖11所示為整個分發(fā)過程的總通信量，其中包括控制消息開銷.在使用10個節(jié)點的實驗中，F(xiàn)DP-VRL與SYNAPSE++和Deluge協(xié)議相比，分別減少了約15.3%和60.9%的通信量.隨著網(wǎng)絡中節(jié)點數(shù)量的增加，F(xiàn)DP-VRL的總通信量增加了8.1%，而SYNAPSE++和Del