軍用無線自組網中鏈路感知的全網廣播研究

王辛果

【摘要】 全網廣播是一種非常重要的通信模式，可廣泛應用于全網通告、尋呼、路由發現等。在軍用無線自組網中，可靠傳輸非常重要，全網廣播需要確保所有節點都能正確收到廣播消息。然而，由于高速移動、強烈干擾等原因，實際的無線鏈路非常不可靠，有時需要多次重傳，降低了傳輸效率。如何高效地實現全網可靠廣播是軍用無線自組網中需要亟待解決的問題。本文提出了一種高效的全網可靠廣播協議，該協議采用基于鏈路感知的連通支配集選擇算法，產生更高效的廣播虛擬骨干網。

【關鍵詞】 無線自組網 可靠廣播 連通支配集 鏈路感知

The Research of Link-Aware Network-Wide Broadcast in Military Wireless Ad hoc Networks WANG Xin-guo （Southwest China Institute of Electronic Technology， Chengdu 10036）

Abstract： Network-wide broadcast is a very important pattern， and can be applied in network-wide notification， paging， routing discovery， and etc. In military wireless ad hoc networks， reliable transmission is very important and network-wide broadcast must ensure all nodes can receive the broadcasting message. However， due to high mobility and strong interference， the factual wireless links are not reliable， multiple retransmissions are sometimes needed and that decreases the efficiency. How to implement network-wide reliable efficiently is a key problem for military wireless ad hoc networks. This paper proposes a link-aware network-wide broadcast protocol （LANWB）， which uses a link-aware connected dominating set election algorithm to generate the more efficient broadcast backbone.

Keywords： Wireless ad hoc network； Reliable broadcast； Connected dominating set； Link-aware

一、引言

全網廣播是單個節點向網絡中所有節點發送消息的通信模式，可廣泛應用于全網通告、尋呼、路由發現等。在軍用無線自組網中，全網廣播要保證所有節點都能夠正確接收消息，即實現全網覆蓋。然而，由于節點高速移動、強烈的敵方干擾等原因，實際的無線鏈路經常發生丟包。為了實現可靠傳輸，可能需要進行多次重傳，這降低了傳輸效率。

全網廣播協議大致可分為全網洪泛、概率轉發、骨干轉發等三類[1]。全網洪泛是讓網絡中所有節點都參與轉發廣播消息，雖能實現全網覆蓋，但會引發廣播風暴，傳輸效率太低。概率轉發為每個節點分配參與轉發的概率，雖能減少廣播轉發次數，但很難保證全網覆蓋。在骨干轉發的協議中，由于每個節點或者是骨干節點，或者至少與一個骨干節點直接相鄰，且所有的骨干節點保持連通，每個骨干節點只轉發一次就能實現全網覆蓋。

二、單跳模型

發送節點重復廣播發送消息，直到所有N個鄰居節點R={r1， r2， …， rN}都正確收到該消息。接收節點采用ARQ（Auto Repeat Request）機制反饋消息的接收狀態。假設發送節點到N個鄰居節點的丟包率分別為e1， e2， …， eN。將節點ri成功接收消息時的傳輸次數記為隨機變量Xi，則N個鄰居節點都收到該消息時的傳輸次數記為隨機變量Y=maxi∈{1，2，…N} Xi。

假設各條鏈路的丟包事件相互獨立，則

PY≤m=Pmaxi∈1，2，…NXi≤m=i=1N（1-eim） （1）

因此，Y的平均值為

三、虛擬骨干網

已有的全網廣播協議認為虛擬骨干網的規模越小，轉發次數越少，廣播效率越高，因而協議的重點是生成節點數最少的虛擬骨干網。文獻[5]已經證明根據全網拓撲生成最小虛擬骨干網是NP難（Non-deterministic Polynomial）問題，只能尋找近似最優算法。此外，由于獲取和維護全網拓撲的開銷很大，通常只能使用基于局部拓撲的分布式算法，這增加了生成最小虛擬骨干網的難度。如果考慮無線鏈路存在丟包，最高效的虛擬骨干網不是成員數最少的虛擬骨干網，而是總傳輸次數最少的虛擬骨干網。下面將介紹一種基于鏈路感知的虛擬骨干網生成算法，減少總傳輸次數。與其他的分布式生成算法[4]類似，基于鏈路感知的虛擬骨干網生成算法分為初始階段和剪枝階段。在初始階段，根據2跳鄰居信息構建連通度較高的初始骨干網；在剪枝階段，再根據鏈路狀態，從支配集中刪除不必要的低效骨干節點。為方便描述，將節點u的1跳鄰居節點集記為。

3.1初始階段

在初始階段，每個節點周期性廣播HELLO消息。其中，包含了本節點id以及本節點的鄰居節點id。如果節點u存在兩個鄰居節點v， w彼此不相鄰，則節點u成為初始骨干節點。不難證明，如果原來的網絡連通，則初始骨干節點組成的子網也保持連通。如圖1所示，節點p， v， w， z成為初始骨干節點。

3.2剪枝階段

每個初始骨干節點通過統計HELLO消息的正確接收比例或信號強度估算本節點到所有鄰居節點的丟包率，并計算得到本節點的廣播效率：

η=NENY （3）

其中，N為鄰居節點數，ENY為式（2）中計算得到的平均廣播發送次數。η值越大，廣播效率越高，在剪枝階段成為最終骨干節點的優先級越高；η值相同時，id越大的節點的優先級越高。

如圖2所示，c到d的丟包率較高導致c的廣播效率較低，則c放棄成為最終的骨干節點。在文獻[4，5]提出的算法的中，h不會成為骨干節點，但在本協議中h將成為骨干節點，這能避免因b到g的丟包率較高而造成大量重傳。因此，節點b， f， h組成最終的連通支配集。由于鏈路層協議通常都會發送HELLO消息且包含上述兩個階段需要的信息，所以上述機制不會增加額外的開銷。

四、全網廣播協議

1、確認機制。廣播消息由產生該消息的源節點id和序列號進行唯一性確定。在廣播消息的幀頭中，發送節點指明尚未確認收到該消息的鄰居節點列表。由于每個節點可能與多個骨干節點相鄰，節點以廣播方式發送ACK消息進行統一確認。為了減少控制開銷，骨干節點不發送ACK消息進行確認，而是通過轉發該廣播消息進行間接確認。因此，每個節點需要維護與其相鄰的骨干節點列表以及鄰居節點的接收狀態表。

2、延時轉發。由于每個節點可能與多個骨干節點相鄰，從任一節點收到廣播消息即可。骨干節點在轉發廣播消息前從[0，Tmax]中隨機退避一段時間，其中Tmax與重發的次數呈指數關系，Tmax = Tw*2i-1。重傳次數越多，重傳前的退避時間越長。因此，延時轉發能夠自適應地利用虛擬骨干網的冗余性，減少沖突和轉發次數。

五、仿真實驗及結果分析

在邊長為500m的正方形區域內，隨機部署300個通信節點。每個節點的通信半徑為50m。每條鏈路的丟包率為均勻隨機分布，最小的的丟包率為0，最大的丟包率為0.05。圖3中所示的是生成的虛擬骨干網示意圖，大圓表示的是骨干節點，小圓表示的是非骨干節點。其中，骨干節點總數為144，骨干節點形成連通的虛擬骨干網，每個非骨干節點至少與1個骨干節點直接相鄰。

接下來，比較LANWB協議與文獻[3]提出的MI協議在全網可靠廣播中的效率。網絡區域為邊長為200m，節點數在50到250之間。在不同網絡規模下，兩種協議廣播每條消息至全網的總傳輸次數如下圖所示。由于優先選擇了效率更高的節點成為骨干節點和延時轉發等，LANWB協議的總傳輸次數更少，因而廣播效率更高。網絡的節點密度越大，LANWB協議的優勢越明顯。

六、總結

本文提出了一種高效的無線自組網全網可靠廣播協議，LAWNB協議。該協議采用了基于鏈路感知的連通支配集生成算法，選擇廣播效率更高的節點轉發廣播消息。仿真結果表明，在保證可靠傳輸的前提下，LAWNB比MI具有更高的廣播效率。

參 考 文 獻

[1] Wisitpongphan N， etc. Broadcast storm mitigation techniques in vehicular ad hoc wireless networks. [J] IEEE wireless communication. 2007， 14（6）： 84-94.

[2] Wan PJ， Wang L， and Yao F. Two-phased approximation algorithms for minimum CDS in wireless ad hoc networks. [C]// Proceedings of IEEE ICDCS conference， 2008， 337-344.

[3] Sakai K， etc. Timer-based CDS construction in wireless ad hoc networks. [J] IEEE transactions on mobile computing. 2011， 10（10）： 1388-1402.

[4] Dai F and Wu J. An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. [J] IEEE transactions on parallel and distributed systems. 2004， 15（10）： 908-920.

[5] Hong J， etc. Minimum-transmission broadcast in uncoordinated duty-cycled wireless ad hoc networks. [J] IEEE transactions on vehicular technology. 2010， 59（1）： 307-318.