無線多跳網絡可靠性評估方法研究

鄒青丙 ，何 明 ，3，王 琰 ，雷冬青

1.解放軍理工大學 指揮信息系統學院，南京 210007

2.解放軍理工大學 通信工程學院，南京 210007

3.解放軍第61研究所，北京 710004

4.南京軍區 司令部作戰指揮綜合保障室，南京 210007

1 引言

無線多跳網絡采用分布式、自組織的思想構建網絡，每個網絡節點都具備路由功能，為其他節點的數據傳輸提供路由和中繼服務。其研究起源于20世紀70年代，最早應用于軍方的戰場監測及預警領域[1]。隨著物聯網在應急救援等領域應用的不斷深入，對無線多跳網絡可靠性的要求不斷提高。但是，由于無線多跳網絡中節點間通信由無線鏈路承載，而噪聲、衰減、干擾等因素影響著無線通信效率。同時，無線鏈路的容量相對有線網絡要低很多，穩定性差。網絡拓撲由于受節點的失效、新節點的加入和無線環境的變化的影響而處于動態變化。這些問題會造成網絡不可靠，已經制約了無線多跳網絡的發展[2]。

本文對近年來相關研究成果歸為3類進行了分析：（1）無線多跳網絡可靠性評估算法研究，主要從對網絡可靠性量化的角度，根據相關的可靠性評價指標研究具體網絡可靠性的度量算法；（2）無線多跳網絡可靠性協議，從協議層面研究提高網絡可靠性的網絡協議；（3）無線多跳網絡可靠性設計研究，是從組網的角度研究部署無線多跳網絡的最優化策略。

2 科學問題的提出

無線多跳網絡可靠性研究的目的就是為了正確地分析評價無線多跳網絡的可靠性，發現網絡中的安全隱患和薄弱環節，從而采取有效的優化措施，提高網絡的可靠性。

2.1 網絡動態演化可靠性建模分析問題

在建立無線多跳網絡可靠性解析或仿真模型時，必須考慮如下的問題：首先，網絡入侵、攻擊策略的設計或選擇問題。在研究無線多跳網絡可靠性的建模過程中，一般情況下是以一定的規則將節點或邊移除作為攻擊策略來觀察網絡性能的變化。其次，對遭受攻擊、被入侵的網絡認識水平的假設，目前的研究大多都是基于完美的信息，即假設攻擊者了解網絡的所有信息，然而在實際網絡對抗中，攻擊者對網絡的整體知識是很難全面掌握的，往往只能得到一部分網絡的信息，而對于網絡中的其他部分信息只具有不確定的認識。

2.2 量化網絡動態演化可靠性影響因素問題

目前，學術界一直認為拓撲結構是影響網絡可靠性的主要因素。在研究中發現影響無線多跳網絡可靠性有很多，從網絡拓撲結構出發僅關注的是網絡的靜態可靠性，不考慮節點（邊）失效的動態關聯，在物聯網環境無線多跳網絡更應該關注不同失效模式下網絡中節點的動態行為、網絡流的路由策略等，它們同樣是影響無線多跳網絡可靠性的重要因素。

2.3 網絡效能度量指標制定合理性問題

如何制定合理的網絡功能度量指標，才能進一步進行無線多跳網絡可靠性評價。在對各項可靠性指標研究的基礎上，分析指標之間的相互關系，構建規范、系統的無線多跳網絡可靠性評價指標體系。分析驗證其完備性、系統性及各指標之間的獨立性。根據確定的可靠性評價指標體系，尤其是針對一些NP難的度量參數，設計快速有效的算法。在網絡系統不斷演化發展情況下，使用無線多跳網絡可靠性評價指標，從大量的節點中識別出影響網絡可靠性的“關鍵”節點，綜合評價、度量其可靠性，進而采取有效的防護措施，防止其出現故障，提高整個網絡的可靠性。

3 無線多跳網絡可靠性研究

3.1 無線多跳網絡可靠性評估算法

對于一種具體的網絡，其在生命周期中是否可靠、可靠程度如何、如何度量等，是網絡可靠性研究首先要解決的問題。目前，國內外學者針對這一問題的研究成果較豐富，主要從3種典型無線多跳網絡形式來分別闡述。

（1）無線自組織網絡

在算法設計過程中，研究人員多從網絡特點出發，有針對性地進行設計。例如針對節點移動、易失效等特點，研究人員提出擴展圖論法、2-終端可靠法[3]等，并在此基礎上提出基于構件有效可靠性的構件式系統可靠性測評方法，根據系統構件的可靠性評估系統的可靠性，使測評更加合理[4]。

Cook在文獻[5]中提出了針對MAWN兩終端可靠性的蒙特卡羅算法，算法基于概率計算MAWN的可靠性。在后續的研究中作者又將MAWN節點的移動進行建模，進而提出考慮節點移動的MASN可靠性計算算法[6]。文獻[7]針對移動Ad Hoc網絡端到端通信性能的定量評估，利用連續時間馬爾可夫鏈和M/M/1/K排隊模型，提出一個全面考慮網絡故障、過載和終端移動特性的復合網絡模型，定量地給出Ad Hoc網絡可靠性的評估結果。文獻[8]提出了一種基于節點移動的Ad Hoc網絡可靠性計算方法，并驗證了移動自組織網的可靠性不僅依賴節點、鏈路可靠性，還依賴于網絡拓撲的冗余度和節點在網絡中的分布。

（2）無線傳感器網絡

無線傳感器網絡應用相對特殊，網絡中各節點所處的地位與具體應用密切相關，對于節點重要性的評估非常重要，度量節點重要性算法隨之產生[9]。文獻[10]提出一種無線傳感器網絡中基于網絡編碼的可靠傳輸方案。文獻[11]針對分布式傳感器網絡中的故障點多、導致估計系統可靠性參數困難的特點，提出了一種基于BP三層神經網絡的Markov可靠性模型，降低了誤差，提高了收斂速度。文獻[12]針對網絡節點間的通信損耗，提出建立鄰居節點網，使鄰居節點可利用網絡代碼進行合作，提高網絡的可靠性。

（3）無線Mesh網絡

文獻[13]給出了一種無線Mesh網骨干層2-終端可靠性計算策略，主要是考慮了無線環境下節點故障和節點間鏈路故障同時存在對網絡可靠性的影響，這是一種準確計算可靠性的方法；文獻[14]提出一種基于多徑路由的網絡可靠性評估方法，同時研究了與分解路由比較優劣。為了評價無線Mesh網中可用路徑多樣性帶來的可靠性，何明等在文獻[15]將有線網絡可靠性算法和無線網絡傳輸模型結合，提出一種Mesh網終端對可靠性的計算方法。該方法能夠計算出全部鏈路和節點的故障率，以及基于多跳/多徑鏈路的性能計算出用戶站和基站間鏈路的總故障率。文獻[16]在混合自動重傳和自動重傳請求的基礎上，采用分層機制、Relay ARQ機制、多跳ARQ機制等，提高了無線Mesh網絡數據傳輸的可靠性。

3.2 無線多跳網絡可靠性協議研究

在可靠性協議設計方面，無線多跳網絡研究通常是在對傳統網絡研究的基礎上，修改或構建新的網絡協議來提高其在應用中的魯棒性。與傳統網絡相比，無線多跳網絡節點處于運動狀態，網絡拓撲結構動態變化，為解決這難題學者提出很多卓有成效的研究成果。

（1）無線自組織網絡

無線自組織網絡主要包括四種路由協議：先驗式和反應式；平面和層次型；GPS輔助和非GPS輔助型；單路徑和多路徑型。在設計協議過程中，可采用單一或多種策略。

由于節點具有移動性，協議必須能夠有效處理節點移動帶來的影響，能夠對網絡拓撲的變化及時做出反應。針對這一現實要求，研究人員從協議的角度研究網絡設計問題，提出了DSDV路由算法[17]。目前，無線自組網可靠性計算協議僅能模糊計算，無法做到精確[18]。為增加“可靠鏈路”，文獻[19]提出一種節點部署策略。這一策略有一定的好處，當節點欲部署區域人為無法到達時，該策略具有較好的適應性。在數據傳輸可靠性方面，文獻[20]提出了一種全新的層疊網絡可靠組播傳輸協議LORM，在利用周期性檢測節點信息的方式建立起層疊網絡拓撲的基礎上，通過本地數據丟失恢復與源節點協助數據恢復相結合的方式，對傳輸過程中產生的各種數據丟失情況進行相應的處理，最大程度上地實現組播數據的可靠傳輸。

（2）無線傳感器網絡

為實現數據傳輸的可靠性，所設計的協議大都利用無線傳感器網絡的以下特點：①節點按照數據屬性尋址，而不是IP尋址。②數據被發往網關節點。③節點性能、能量有限，需要節約這些資源[21]。融合基于簇的路由協議可較好地提高網絡可靠性，如文獻[22]利用可靠性框圖（Reliability Block Diagrams，RBD）對分簇通信協議的數據可靠性進行建模，將得出的網絡可靠性值引入簇形成機制中，提出了REECP（Reliable Energy-Efficient Cluster-based Protocol），使無線傳感器網絡生命周期得到有效延長，減少了數據融合時的誤差傳播，進而有效提高了基于分簇通信協議的無線傳感器網絡的可靠性。文獻[23]提出一種分簇協作路由算法，可較好利用物理介質的廣播優勢以及周圍節點的協作優勢，提高了網絡性能，增強了可靠性。為了減少整個網絡的能量消耗，提高全網壽命及可靠性，Ocakoglu O在文獻[24]中提出運用統計方法來設計評估預期的目標，提出了一種隨機的睡眠/喚醒策略。文獻[25]提出一種多信道動態路徑轉發協議，在發送數據前可預測喚醒時間，避免了因依賴長前導而導致的問題，實現了更低能耗并改善了延時性能。

為減少同步誤差的多跳積累，研究人員提出為網絡中的每一個節點保存待選同步動態路徑列表，提高同步過程的可靠性[26]。也有學者從丟包率等方面測試無線網可靠性，對協議效果進行分析[27]。

（3）無線Mesh網絡

為解決在無線網絡環境資源有限情況下，保證網絡信息傳輸的可靠性，文獻[28]提出了一種基于鏈路不相交技術的多路徑路由算法。該算法通過盡可能少的信息交換，獲得了較多的網絡狀態信息，進而在一定程度上保證了網絡的負載平衡。文獻[29]提出了一種多判據加權可靠路由算法。其主要思想是在選擇路由時，綜合考慮節點的移動性、路徑的跳數、時延、鏈路可靠性、鏈路的失效數等性能指標，按重要程度加權整體計算路由的權值，選擇權值最大的路徑作為傳輸路由。但該方法的計算復雜度較高。

3.3 無線多跳網絡可靠性優化設計

無線多跳網絡可靠性研究的最終落腳點是指導網絡的優化設計，確保應用的安全可靠。基于此目標，學者們從不同的角度提出了很多可靠性優化策略，主要可以梳理為以下幾個方面：

（1）最優化拓撲方案設計

網絡拓撲對網絡規劃、管理、可靠性等都有重要的意義，如何設計一個高效可靠的無線傳感器網絡是一個重要的挑戰。Hawick等人[30]應用小世界網絡模型研究了無線傳感器網絡的覆蓋、容錯和壽命問題。研究結果表明，將小世界特征引入無線傳感器網絡，不但使得無線傳感器網絡的平均路徑長度大大減小，而且網絡中出現的孤立簇的數目也大大減少，無線傳感器網絡的整體覆蓋效果和可靠性都大大改善。

（2）容錯性設計

網絡的容錯系統是保證網絡在出現部分故障的情況下，仍能正常向用戶提供有效服務。它使網絡具有自我保護及一定的自我修復能力，以便于管理員和維修人員采取進一步措施。在無線多跳網絡容錯設計中，要把握以下幾個原則：一是緊密結合應用實際進行網絡設計。不同的應用需求，對網絡的容錯性要求不同，不能一概而論，避免資源浪費，節約成本。二是緊貼性能指標要求進行設備選型。網絡設計之初，就應從傳輸介質、接口選用、協議設置及網絡設備選擇等方面，從穩定性、可靠性出發，嚴把質量關。三是緊盯網絡中關鍵部位和骨干成分，只要保證了關鍵部位的可靠性，就可能基本保證整個網絡的可靠性。因此在容錯設計時，就可以一定程度上減少對容錯的要求，進而節約成本。

（3）冗余性設計

確保網絡可靠性的另一個重要的方法就是冗余設計。這種設計策略要求網絡部署時在原有設施的基礎上再額外增加部分備用設備，通過增加備用機制來保障無線多跳網絡的可靠性。正常情況下，備用部分處于監聽狀態，一旦網絡出現故障或異常，冗余部分則根據預定規則加入網絡，保證系統的正常運行。文獻[31]針對WSN的漏斗問題，采用分簇結構平衡內能耗，提出一種基于簇負載平衡冗余節點部署算法。該算法可以有效減少節點能耗，提高了網絡的可靠性。文獻[32]提出了一種基于節點冗余覆蓋的調度算法，通過關閉不必要的冗余節點和盡可能實現負載均衡，有效降低了能量消耗。以上方法從不同的角度提出了相應的冗余節點優化部署方案，對于提高網絡的可靠性具有重要意義。

4 發展趨勢

無線多跳網絡可靠性研究將進一步從網絡可靠性評估基礎理論研究向指導實際需求中網絡可靠性設計轉化，具體體現在以下幾個方面：一是繼續深入研究無線多跳網絡可靠性檢測與評估技術。總體來看，網絡可靠性評估方法研究相對比較成熟，但一些具體應用環境下的網絡可靠性評估理論仍然處于起步階段，亟待研究解決。二是研究適于物聯網應用背景下的網絡可靠性評價指標體系。對于日新月異的復雜應用環境，傳統的網絡可靠性評估指標體系已不能完整覆蓋其所有特性，研究適用于新環境下的可靠性評價指標體系意義深遠。三是研究物聯網系統可靠性評估試驗床。目前，用于各種網絡可靠性評估仿真的環境主要是基于NS2、MATLAB等搭建的虛擬仿真驗證環境，缺乏與物聯網系統實際應用環境相仿的實體試驗環境。進行網絡可靠性評估試驗床研究是未來的一個重要方向。四是研制開發物聯網系統可靠性評估工具。物聯網應用的前景十分廣闊，對于應用系統的可靠性評估仍處在理論研究階段，缺乏切實可用的可靠懷評估工具。

[1]Toh C K.Ad hoc mobile wireless networks：protocols and systems[M].[S.l.]：Pearson Education，2001.

[2]尚鳳軍.無線傳感器網絡通信協議[M].北京：電子工業出版社，2011.

[3]He Ming，Xiao Denghai，Qiu Hangping，et al.Method for reliability evaluation of mobile ad hoc networks[J].Application Research of Computers，2009，26（11）：4282-4285.

[4]郭勇，馬培軍，蘇小紅.考慮構件有效可靠性的構件式系統可靠性測評[J].高技術通訊，2013，23（2）：146-152.

[5]Cook J L，Ramirez-Marquez J E.Two-terminal reliability analyses for a mobile ad hoc wireless network[J].Reliability Engineering & System Safety，2007，92（6）：821-829.

[6]Cook J L，Ramirez-Marquez J E.Reliability method for ad-hoc networks[C]//Proceedings of Institute of Industrial Engineers Annual Conference，2006.

[7]Guo Hong，Lan Julong，Cheng Dongnian，et al.Quantitative modeling and analysis for end to end communication performance evaluation of mobile ad hoc networks[J].Journal of Information Engineering University，2010，11（1）：11-16.

[8]HeMing，ChenGuohua，LaiHaiguang，etal.Methods for evaluating reliability of mobile ad hoc networks in the perception layer of IOT[J].Computer Science，2012，39（6）：104-106.

[9]Xu X，Liang J，Song X.Reliability research of wireless sensor networks with node failures[J].Microelectronics&Computer，2011，6.

[10]Hao J，Feng H，Wu G.Improving data transmission reliability with network coding in wireless sensor network[C]//2010 International Conference on Multimedia Information Networking and Security，2010：159-163.

[11]Jia Huiqin，Liu Junhua.Reliability analysis of distributed sensor network based on back propagation neural network[J].Journal of The China Railway Society，2002，24（5）：80-83.

[12]Ma L，Lin Z，Zhang Z，et al.Improving reliability in lossy wireless networks using network coding[C]//2013 IEEE International Conference on Communications Workshops（ICC），2013：312-316.

[13]趙蘊龍，單寶龍，高振國，等.無線Mesh網骨干層2-終端可靠性計算策略[J].計算機學報，2009（3）：424-431.

[14]He Ming，Qiu Hangping，Bso Guangyu，et al.Reliability evaluation based on multipath routing in WMN[J].Journal of Applied Sciences，2009，27（5）：441-445.

[15]何明，裘杭萍，胡愛群，等.Mesh網的可靠性評價方法研究[J].東南大學學報：自然科學版，2008，38Sup（1）：222-225.

[16]李忠林.無線Mesh網絡中數據傳輸可靠性的保障方法分析[J].信息系統工程，2013（1）：82-83.

[17]Perkins C E，Bhagwat P.DSDV routing over a multihop wireless network of mobile computers[M]//Ad hoc networking.Boston，MA，USA：Addison-WesleyLongman Publishing，2001：29-51.

[18]Luo J，Eugster P T，Hubaux J P.Probabilistic reliable multicastin ad hocnetworks[J].Ad HocNetworks，2004，2（4）：369-386.

[19]Ye Zhenqiang，Krishnamurthy S V，Tripathi S K.A routing framework for providing robustness to node failures in mobile ad hoc networks[J].Ad Hoc Networks，2004：87-107.

[20]Zhao Y，Ma Y，Li X.A link-independence multi-path routing strategy in wireless Mesh networks[J].Journal of Harbin Engineering University，2008，9.

[21]崔莉，鞠海玲，苗勇，等.無線傳感器網絡研究進展[J].計算機研究與發展，2005，42（1）：163-174.

[22]Zhou Zude，Hu Peng，Li Fangmin.Reliable scheme for the cluster-based communication protocol in wireless sensor networks[J].Journal on Communications，2008，29（5）：114-121.

[23]Lee W，Kim Y，Lee S，et al.Reliability analysis of realtime control systems in industrial wireless network[C]//2013 International Conferenceon ICT Convergence（ICTC），2013：1097-1098.

[24]Ocakoglu O，Ercetin O.Energy efficient random sleepawake schedule design[J].IEEE Communications Letters，2006，10（7）：528-530.

[25]謝鯤，孫家奇.無線多跳網絡分簇協作路由算法[J].小型微型計算機系統，2013（2）：210-215.

[26]蔣富龍，劉昊.一種無線傳感器網絡多信道動態路徑轉發協議[J].東南大學學報，2014，44（1）：28-33.

[27]董恩清.基于動態路徑列表的無線傳感器網絡時間同步協議[J].光學精密工程，2013，21（11）：2951-2959.

[28]石曦，馮鋼，張翼德.無線ad-hoc網絡中基于層疊網絡的可靠多播協議[J].通信學報，2010（1）.

[29]張媛.無線Mesh網絡可靠性技術研究[D].哈爾濱：哈爾濱工程大學，2010.

[30]Hawick K A，James H A.Small-world effects in wirelessagentsensornetworks[J].InternationalJournalof Wireless and Mobile Computing，2010，4（3）：155-164.

[31]Zhang Rongbiao，Zhou Fu，Ran Li，et al.A fussy graph theory based redundantnode deploymentalgorithm for multi-hop WSN[J].High Technology Letters，2011，21（3）：5-8.

[32]Zhang D X，Xu M，Tang W S.Self-scheduled redundant coverage algorithm for wireless sensor networks[J].Transducer and Microsystem Technologies，2009，28（3）：24-29.