王辛果

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

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

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

二、單跳模型

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

假設(shè)各條鏈路的丟包事件相互獨(dú)立，則

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

因此，Y的平均值為

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

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

3.1初始階段

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

3.2剪枝階段

每個(gè)初始骨干節(jié)點(diǎn)通過(guò)統(tǒng)計(jì)HELLO消息的正確接收比例或信號(hào)強(qiáng)度估算本節(jié)點(diǎn)到所有鄰居節(jié)點(diǎn)的丟包率，并計(jì)算得到本節(jié)點(diǎn)的廣播效率：

η=NENY （3）

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

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

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

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

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

五、仿真實(shí)驗(yàn)及結(jié)果分析

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

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

六、總結(jié)

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

參 考 文 獻(xiàn)

[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.