王辛果

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

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

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

一、引言

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

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

二、單跳模型

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

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

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

因此，Y的平均值為

三、虛擬骨干網(wǎng)

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

3.1初始階段

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

3.2剪枝階段

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

η=NENY （3）

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

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

四、全網(wǎng)廣播協(xié)議

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

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

五、仿真實驗及結果分析

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

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

六、總結

本文提出了一種高效的無線自組網(wǎng)全網(wǎng)可靠廣播協(xié)議，LAWNB協(xié)議。該協(xié)議采用了基于鏈路感知的連通支配集生成算法，選擇廣播效率更高的節(jié)點轉發(fā)廣播消息。仿真結果表明，在保證可靠傳輸?shù)那疤嵯?，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.