多跳無(wú)線網(wǎng)絡(luò)中無(wú)需鄰節(jié)點(diǎn)信息的空間覆蓋廣播算法

劉靖永 李樂(lè)民 景小榮

①(電子科技大學(xué)通信與信息工程學(xué)院 成都 610054)②(重慶郵電大學(xué)信號(hào)與信息處理重慶市重點(diǎn)實(shí)驗(yàn)室 重慶 400065)

1 引言

在多跳無(wú)線網(wǎng)絡(luò)中，用傳統(tǒng)的洪泛(flooding)方法實(shí)現(xiàn)廣播會(huì)產(chǎn)生大量不必要的冗余轉(zhuǎn)發(fā)，從而引發(fā)額外的沖突甚至造成網(wǎng)絡(luò)擁塞，稱為廣播風(fēng)暴(broadcast storm)問(wèn)題[1]。廣播風(fēng)暴問(wèn)題加劇了網(wǎng)絡(luò)帶寬和節(jié)點(diǎn)能量的消耗，同時(shí)，大量的沖突和網(wǎng)絡(luò)擁塞造成丟包，加上無(wú)線信道引發(fā)的傳輸錯(cuò)誤，嚴(yán)重降低了傳輸?shù)目煽啃?。因此，減少轉(zhuǎn)發(fā)冗余、提高廣播的傳輸效率不但可以提高節(jié)點(diǎn)能量和網(wǎng)絡(luò)帶寬的利用率，而且能夠減少?zèng)_突造成的丟包，從而提高廣播的可靠性。

針對(duì)多跳無(wú)線網(wǎng)絡(luò)中的廣播風(fēng)暴問(wèn)題，近年來(lái)提出了很多改善傳輸效率的廣播方法。這些方法主要分為以下幾類：基于概率的方法(probabilitybased methods)[2]，基于面積(或距離)的方法(areabased methods)[1?4]以及基于鄰節(jié)點(diǎn)信息的方法(neighbor information-based methods)[5?11]等。基于概率的方法中節(jié)點(diǎn)使用預(yù)定義的概率p或接收次數(shù)C決定是否轉(zhuǎn)發(fā)廣播包；基于面積的方法選擇附加覆蓋面積較大的節(jié)點(diǎn)優(yōu)先轉(zhuǎn)發(fā)。這兩類廣播方法不需要記錄接收狀態(tài)，無(wú)需維護(hù)節(jié)點(diǎn)鄰節(jié)點(diǎn)信息，但是，由于使用預(yù)定義的門(mén)限值，在節(jié)點(diǎn)密度或網(wǎng)絡(luò)負(fù)載變化時(shí)其性能會(huì)變差；并且轉(zhuǎn)發(fā)節(jié)點(diǎn)之間由于不了解相互的位置關(guān)系，使得轉(zhuǎn)發(fā)節(jié)點(diǎn)分布不合理，在某些非冗余節(jié)點(diǎn)出現(xiàn)錯(cuò)誤時(shí)會(huì)導(dǎo)致丟包甚至無(wú)法繼續(xù)轉(zhuǎn)發(fā)[6]。基于鄰節(jié)點(diǎn)信息的方法又分為鄰節(jié)點(diǎn)指派方法(neighbor-designated methods)和自剪枝方法(self-pruning methods)[12]。鄰節(jié)點(diǎn)指派方法由發(fā)送節(jié)點(diǎn)指定部分節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，比較典型的協(xié)議包括文獻(xiàn)[6,7]中提出的方法和MPR[13]，邊緣轉(zhuǎn)發(fā)協(xié)議[14]等。自剪枝方法則由接收節(jié)點(diǎn)判斷其鄰節(jié)點(diǎn)是否都收到了廣播包來(lái)決定是否轉(zhuǎn)發(fā)，主要包括FSP[12]協(xié)議和基于最小連通支配集(MCDS)的方法[9?11]?；卩徆?jié)點(diǎn)信息的廣播協(xié)議其基本思想是在發(fā)送節(jié)點(diǎn)的所有鄰節(jié)點(diǎn)中，選擇部分節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，使得所有兩跳鄰節(jié)點(diǎn)能夠被這個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)集合覆蓋[1]，本文稱為基于節(jié)點(diǎn)覆蓋的方法?；诠?jié)點(diǎn)覆蓋的方法會(huì)產(chǎn)生過(guò)多的傳輸范圍重疊(transmission overlap)，影響了傳輸效率的提高；而且，基于鄰節(jié)點(diǎn)信息的協(xié)議需要節(jié)點(diǎn)維護(hù)一跳或多跳鄰節(jié)點(diǎn)信息，一般通過(guò)節(jié)點(diǎn)發(fā)送和接收hello消息來(lái)實(shí)現(xiàn)，會(huì)增加額外的帶寬和存儲(chǔ)消耗，并且在節(jié)點(diǎn)密度增大時(shí)使協(xié)議性能降低；此外，鄰節(jié)點(diǎn)指派方法通常選擇靠近傳輸范圍邊緣的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)以增加附加覆蓋面積，在節(jié)點(diǎn)移動(dòng)頻繁或信道狀況出現(xiàn)變化時(shí)可能會(huì)導(dǎo)致轉(zhuǎn)發(fā)節(jié)點(diǎn)出現(xiàn)傳輸錯(cuò)誤而使轉(zhuǎn)發(fā)失敗。

本文提出了一種無(wú)需鄰節(jié)點(diǎn)信息的空間覆蓋廣播(Space-Covered Broadcast，SCB)算法，該算法基于最優(yōu)空間覆蓋的思想，即通過(guò)優(yōu)化轉(zhuǎn)發(fā)節(jié)點(diǎn)的空間分布達(dá)到利用最少數(shù)目的轉(zhuǎn)發(fā)節(jié)點(diǎn)實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)的覆蓋，從而減少了轉(zhuǎn)發(fā)節(jié)點(diǎn)個(gè)數(shù)和轉(zhuǎn)發(fā)節(jié)點(diǎn)傳輸范圍之間的重疊面積。通過(guò)分析，每個(gè)發(fā)送節(jié)點(diǎn)只需3個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)即可實(shí)現(xiàn)對(duì)整個(gè)網(wǎng)絡(luò)空間接近雙重的覆蓋，能夠保證較高的傳輸可靠性?；诳臻g覆蓋的思想也使得SCB算法對(duì)節(jié)點(diǎn)密度和拓?fù)渥兓幻舾?，具有較好的可擴(kuò)展性。而且，SCB算法在接收節(jié)點(diǎn)處分布式選擇最優(yōu)的轉(zhuǎn)發(fā)節(jié)點(diǎn)，能夠評(píng)估信道的狀態(tài)，有效地避免無(wú)線信道不穩(wěn)定和傳輸范圍邊緣的灰色區(qū)域(gray zone)[4]等問(wèn)題造成的傳輸錯(cuò)誤，因此對(duì)物理信道的變化具有自適應(yīng)性。此外，由于不使用鄰節(jié)點(diǎn)信息且無(wú)需了解網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，SCB算法不產(chǎn)生額外的帶寬和存儲(chǔ)開(kāi)銷，減小了計(jì)算量。算法所需的唯一網(wǎng)絡(luò)信息是節(jié)點(diǎn)的位置信息，可以通過(guò)GPS，虛擬節(jié)點(diǎn)位置方法以及接收信號(hào)強(qiáng)度等方法很容易獲得。

本文以下部分首先分析理想情況下發(fā)送節(jié)點(diǎn)的最優(yōu)分布方式，給出相應(yīng)的廣播方法；然后對(duì)實(shí)際網(wǎng)絡(luò)中的SCB算法進(jìn)行詳細(xì)描述；最后對(duì)協(xié)議性能進(jìn)行仿真和數(shù)值結(jié)果分析。

2 理想情況下最優(yōu)發(fā)送節(jié)點(diǎn)分布方式及空間覆蓋廣播方法

假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)是理想分布的，所有節(jié)點(diǎn)具有相同的傳輸半徑R，本節(jié)對(duì)實(shí)現(xiàn)可靠廣播的最優(yōu)發(fā)送節(jié)點(diǎn)分布方式進(jìn)行分析，給出理想情況下的最優(yōu)轉(zhuǎn)發(fā)方法。

2.1 最優(yōu)發(fā)送節(jié)點(diǎn)分布方式

首先引入平面空間的圓盤(pán)覆蓋問(wèn)題，即用最少個(gè)數(shù)半徑為R的圓盤(pán)無(wú)縫地覆蓋整個(gè)平面的問(wèn)題。如圖1所示，將平面劃分為邊長(zhǎng)為R的正六邊形空間，在每一個(gè)正六邊形處做外接圓，則外接圓的半徑為R，圓盤(pán)的這種排列方式是實(shí)現(xiàn)對(duì)平面空間覆蓋的最有效方式[15]。

把圓盤(pán)看作節(jié)點(diǎn)的傳輸范圍，則節(jié)點(diǎn)分別位于每個(gè)圓盤(pán)的圓心，此時(shí)節(jié)點(diǎn)間的距離大于R，不能互相通信。將圖1 中所有圓盤(pán)圓心位置移動(dòng)到對(duì)應(yīng)六邊形的同一方位的頂點(diǎn)，可以分別得到圖2中所有實(shí)線圓盤(pán)或所有虛線圓盤(pán)所示的兩種排列方式，這兩種圓盤(pán)排列方式與圖1中所示的方式是等價(jià)的。將這兩組等價(jià)圓盤(pán)按照網(wǎng)格對(duì)齊疊加在一起，如圖2 所示，得到雙重覆蓋空間的最有效圓盤(pán)排列方法，即用最小數(shù)目的圓盤(pán)實(shí)現(xiàn)了對(duì)空間的雙重覆蓋。

把每個(gè)圓盤(pán)看作一個(gè)發(fā)送節(jié)點(diǎn)的傳輸范圍，此時(shí)發(fā)送節(jié)點(diǎn)分別位于每個(gè)正六邊形的頂點(diǎn)處，每個(gè)發(fā)送節(jié)點(diǎn)與3個(gè)其它發(fā)送節(jié)點(diǎn)互相連接。這種發(fā)送節(jié)點(diǎn)分布方式利用數(shù)目最少的發(fā)送節(jié)點(diǎn)實(shí)現(xiàn)了對(duì)網(wǎng)絡(luò)的雙重覆蓋，并且發(fā)送節(jié)點(diǎn)傳輸范圍之間的重疊面積也最小。此外，任意兩個(gè)發(fā)送節(jié)點(diǎn)之間都有至少3條路徑相連接，因此該分布方式保證了必要的連接冗余，即使少數(shù)節(jié)點(diǎn)失效仍可實(shí)現(xiàn)網(wǎng)絡(luò)的完全覆蓋，有利于增強(qiáng)容錯(cuò)能力。

2.2 理想情況下的最優(yōu)空間覆蓋廣播方法

在節(jié)點(diǎn)分布理想的情況下，設(shè)置每個(gè)正六邊形頂點(diǎn)處的節(jié)點(diǎn)為發(fā)送節(jié)點(diǎn)即可實(shí)現(xiàn)可靠的廣播傳輸。如圖3所示，理想情況下的最優(yōu)空間覆蓋廣播方法為：數(shù)據(jù)包從源節(jié)點(diǎn)S以廣播方式發(fā)出，經(jīng)最近的3個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)；在每個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)之后由另外兩個(gè)節(jié)點(diǎn)繼續(xù)轉(zhuǎn)發(fā)，位于重合位置的節(jié)點(diǎn)只轉(zhuǎn)發(fā)一次；所有轉(zhuǎn)發(fā)節(jié)點(diǎn)重復(fù)此過(guò)程，直到數(shù)據(jù)包到達(dá)網(wǎng)絡(luò)邊緣。

3 實(shí)際網(wǎng)絡(luò)中的SCB算法

稱圖3中轉(zhuǎn)發(fā)節(jié)點(diǎn)所在的位置為理想位置，轉(zhuǎn)發(fā)節(jié)點(diǎn)的分布方式為理想分布。在實(shí)際網(wǎng)絡(luò)中，節(jié)點(diǎn)是隨機(jī)分布的，轉(zhuǎn)發(fā)節(jié)點(diǎn)的位置通常會(huì)偏離理想位置，因此無(wú)法獲得理想的轉(zhuǎn)發(fā)節(jié)點(diǎn)分布。而由于理想情況下轉(zhuǎn)發(fā)節(jié)點(diǎn)能夠雙重覆蓋網(wǎng)絡(luò)，少量節(jié)點(diǎn)無(wú)效時(shí)仍然能夠完成廣播。因此，在實(shí)際的網(wǎng)絡(luò)中只要選擇最靠近理想位置的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，就可以盡量完全地覆蓋網(wǎng)絡(luò)，如圖4所示。當(dāng)節(jié)點(diǎn)密度較大時(shí)，轉(zhuǎn)發(fā)節(jié)點(diǎn)的分布接近理想分布。

SCB算法的思想為：源節(jié)點(diǎn)以廣播方式發(fā)送數(shù)據(jù)包；接收節(jié)點(diǎn)收到包后進(jìn)行處理并通過(guò)延時(shí)轉(zhuǎn)發(fā)機(jī)制實(shí)現(xiàn)轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇：首先根據(jù)發(fā)送節(jié)點(diǎn)和自己的位置信息計(jì)算一個(gè)轉(zhuǎn)發(fā)時(shí)延，在此時(shí)延內(nèi)如果再次收到該轉(zhuǎn)發(fā)包則取消發(fā)送，否則仍以廣播方式進(jìn)行轉(zhuǎn)發(fā)。由于不同位置的節(jié)點(diǎn)轉(zhuǎn)發(fā)時(shí)延不同，通過(guò)時(shí)延差使得距離理想位置較近的節(jié)點(diǎn)優(yōu)先發(fā)送，而較遠(yuǎn)節(jié)點(diǎn)的轉(zhuǎn)發(fā)受到抑制，從而選擇出最優(yōu)的轉(zhuǎn)發(fā)節(jié)點(diǎn)。同時(shí)，延時(shí)轉(zhuǎn)發(fā)機(jī)制實(shí)現(xiàn)了錯(cuò)開(kāi)不同轉(zhuǎn)發(fā)節(jié)點(diǎn)發(fā)送時(shí)間的功能，從而減小了節(jié)點(diǎn)之間的干擾。此外，轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇在成功收到包的接收節(jié)點(diǎn)處實(shí)現(xiàn)，使得SCB算法能夠自動(dòng)適應(yīng)信道狀況，有效地避免信道變化造成的傳輸錯(cuò)誤。

3.1 SCB算法的工作過(guò)程

(1)源節(jié)點(diǎn)以廣播方式發(fā)送數(shù)據(jù)包，數(shù)據(jù)包中攜帶發(fā)送節(jié)點(diǎn)(sender)和上一跳發(fā)送節(jié)點(diǎn)(pre_sender)的位置坐標(biāo)。

(2)節(jié)點(diǎn)接收到數(shù)據(jù)包后，檢查是否已收到過(guò)該包，如果是則丟棄；否則將該包轉(zhuǎn)交上層協(xié)議并進(jìn)行轉(zhuǎn)發(fā)。

(3)接收節(jié)點(diǎn)根據(jù)自己的位置坐標(biāo)和sender以及pre_sender的位置坐標(biāo)計(jì)算理想轉(zhuǎn)發(fā)位置和發(fā)送時(shí)延。首先判斷發(fā)送節(jié)點(diǎn)為是否為源節(jié)點(diǎn)，如果是則轉(zhuǎn)到(4a)；否則轉(zhuǎn)到(4b)。

圖3 理想情況下的最優(yōu)空間覆蓋廣播方法

圖4 實(shí)際網(wǎng)絡(luò)中轉(zhuǎn) 發(fā)節(jié)點(diǎn)的分布

(4a)按3.2節(jié)中式(1)計(jì)算3個(gè)理想位置，然后分別計(jì)算到3個(gè)理想位置的最短距離，設(shè)為d，計(jì)算發(fā)送時(shí)延為delay=(d/R)?SCB_delay，其中SCB_ delay為算法預(yù)設(shè)的時(shí)延值，d/R稱為時(shí)延因數(shù)，用df表示。

(4b)按式(3)計(jì)算3個(gè)理想位置，其中l(wèi)oc1為上一跳發(fā)送節(jié)點(diǎn)靠近的理想位置，因此只需分別計(jì)算到loc2和loc3的距離并找出最小值d。如果d≥R則節(jié)點(diǎn)距離loc1較近，因此不轉(zhuǎn)發(fā)；如果d＜R，則發(fā)送時(shí)延為delay=(d/R)?SCB_delay 。

(5)接收節(jié)點(diǎn)設(shè)置轉(zhuǎn)發(fā)計(jì)時(shí)器的值為delay，將該包加入轉(zhuǎn)發(fā)隊(duì)列。計(jì)時(shí)器超時(shí)則以廣播方式轉(zhuǎn)發(fā)該包；如果在超時(shí)之前接收到其他節(jié)點(diǎn)轉(zhuǎn)發(fā)的該數(shù)據(jù)包則取消發(fā)送。

所有節(jié)點(diǎn)重復(fù)(2)到(5)的過(guò)程，直到數(shù)據(jù)包到達(dá)網(wǎng)絡(luò)邊緣，由于節(jié)點(diǎn)收到兩次以上同一序號(hào)的包不進(jìn)行轉(zhuǎn)發(fā)，算法自然收斂。

3.2 理想位置的計(jì)算方法

發(fā)送節(jié)點(diǎn)為源節(jié)點(diǎn)時(shí)，設(shè)源節(jié)點(diǎn)位置坐標(biāo)為(X, Y)，由于節(jié)點(diǎn)隨機(jī)分布，在任何方向上其分布概率都是相同的，因此按圖3中的位置計(jì)算3個(gè)一跳理想位置，分別為

發(fā)送節(jié)點(diǎn)不是源節(jié)點(diǎn)時(shí)，設(shè)節(jié)點(diǎn)N1為發(fā)送節(jié)點(diǎn)，N1從上一跳發(fā)送節(jié)點(diǎn)N0收到數(shù)據(jù)包，N0和N1的位置坐標(biāo)分別為(X0, Y0)和(X1, Y1)。理想位置按如下方法確定：首先以N1為坐標(biāo)原點(diǎn)進(jìn)行坐標(biāo)轉(zhuǎn)換，如圖5所示，N0轉(zhuǎn)換后的坐標(biāo)為(X0?X1, Y0?Y1)，令x0=X0?X1，y0=Y0?Y1，N1到N0的距離為d0=，N1N0與x軸夾角∠x(chóng)N1N0為α，則cosα=x0/d0，角度α為

3個(gè)理想位置分別為

3.3 轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇方法的改進(jìn)

節(jié)點(diǎn)延時(shí)轉(zhuǎn)發(fā)機(jī)制使得接收節(jié)點(diǎn)可以選擇出最優(yōu)的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)而排除其他節(jié)點(diǎn)的發(fā)送。然而，如果多個(gè)節(jié)點(diǎn)到某個(gè)理想位置的距離相近，而使發(fā)送時(shí)延間隔小于轉(zhuǎn)發(fā)包的接收時(shí)延，可能出現(xiàn)多個(gè)節(jié)點(diǎn)幾乎同時(shí)轉(zhuǎn)發(fā)的情況。這種情況會(huì)造成沖突，影響協(xié)議性能。為了改善此問(wèn)題，本文提出兩種改進(jìn)的方法：(1)用代替d/R計(jì)算時(shí)延因數(shù)，稱為平方根距離方法(相應(yīng)地，3.1節(jié)中的方法稱為線形距離方法)。這種方法在d較小時(shí)能夠增大不同節(jié)點(diǎn)轉(zhuǎn)發(fā)時(shí)延的間隔，因而增強(qiáng)了區(qū)分能力。(2)增加角度判斷，其目的是在距離相近的節(jié)點(diǎn)中優(yōu)先選擇靠近理想方向的節(jié)點(diǎn)，從而減小傳輸范圍的重疊面積。如圖6所示，S為發(fā)送節(jié)點(diǎn)，設(shè)節(jié)點(diǎn)n到理想位置N的距離為d，夾角∠nSN等于α，其時(shí)延因數(shù)為

其中A為預(yù)設(shè)參數(shù)且0＜A≤1，稱這種方法為線形距離加角度方法，當(dāng)A=1時(shí)，與線形距離方法相同。此外，將方法(1)，(2)相結(jié)合得到平方根距離加角度方法，其時(shí)延因數(shù)為

圖5 理想轉(zhuǎn)發(fā)位置的確定

圖6 距離加角度的轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇方法

4 仿真及數(shù)值結(jié)果分析

基于ns-2平臺(tái)(版本2.29)對(duì)SCB的性能進(jìn)行了仿真分析。仿真參數(shù)設(shè)置如下：無(wú)線傳播信道采用two-ray ground reflection 模型；MAC層采用IEEE 802.11協(xié)議；無(wú)線信道的帶寬為缺省值2 Mbps；節(jié)點(diǎn)傳輸范圍為250 m；數(shù)據(jù)包長(zhǎng)度采用固定值256 byte；網(wǎng)絡(luò)負(fù)載設(shè)置為10 pkt/s。每次仿真運(yùn)行時(shí)間為150 s，結(jié)果為100次運(yùn)行的平均值。性能評(píng)價(jià)參數(shù)為送達(dá)率(delivery ratio)，轉(zhuǎn)發(fā)率(forwarding ratio)和傳輸時(shí)延(transmission delay)。送達(dá)率用來(lái)評(píng)價(jià)協(xié)議的傳輸可靠性，定義為成功接收到數(shù)據(jù)包的節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的比值，每次運(yùn)行的結(jié)果為所有數(shù)據(jù)包的平均值。使用轉(zhuǎn)發(fā)率來(lái)評(píng)價(jià)協(xié)議的轉(zhuǎn)發(fā)效率，其定義為轉(zhuǎn)發(fā)節(jié)點(diǎn)的平均個(gè)數(shù)對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的比值。傳輸時(shí)延定義為所有接收節(jié)點(diǎn)的端到端時(shí)延的平均值，用來(lái)描述協(xié)議完成數(shù)據(jù)包廣播的時(shí)延特性。

首先對(duì)轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇方法進(jìn)行仿真，分析各種轉(zhuǎn)發(fā)時(shí)延計(jì)算方法在不同網(wǎng)絡(luò)環(huán)境下對(duì)算法性能的影響，找出獲得較好性能的選擇方法和協(xié)議參數(shù)。然后，將SCB算法與3類廣播方法的典型協(xié)議(分別為無(wú)狀態(tài)的洪泛協(xié)議[16]，基于1跳鄰節(jié)點(diǎn)信息的邊緣轉(zhuǎn)發(fā)協(xié)議[14]和基于2跳鄰節(jié)點(diǎn)信息的CDS-based廣播協(xié)議[9])進(jìn)行仿真比較，對(duì)SCB算法的性能進(jìn)行驗(yàn)證。

4.1 轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇方法的性能比較

轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇方法分別為線性距離方法(1.0 Linear)、平方根距離方法(1.0Sqrt)、線性距離加角度方法(0.5 Linear)和平方根距離加角度方法(0.5 Sqrt)。通過(guò)仿真分析各種方法在不同節(jié)點(diǎn)密度下的性能。網(wǎng)絡(luò)環(huán)境為200到1000個(gè)節(jié)點(diǎn)隨機(jī)分布在面積為1000 m×1000 m 的正方形區(qū)域內(nèi)，節(jié)點(diǎn)最大速度為20 m/s，參數(shù)A設(shè)為0.5，SCB_delay取值為0.2 s。仿真結(jié)果分別示于圖7，圖8和圖9。

由圖7可見(jiàn)，幾種選擇方法都能獲得較高的送達(dá)率；隨著節(jié)點(diǎn)個(gè)數(shù)增加，由于轉(zhuǎn)發(fā)節(jié)點(diǎn)分布趨于理想分布，具有更好的覆蓋效果，送達(dá)率也隨之提高；線性距離加角度方法性能較好，在節(jié)點(diǎn)個(gè)數(shù)大于400時(shí)送達(dá)率超過(guò)99%，節(jié)點(diǎn)個(gè)數(shù)為1000時(shí)接近100%。圖8中，幾種選擇方法的轉(zhuǎn)發(fā)率都隨著節(jié)點(diǎn)密度的增大而減小，這是由于轉(zhuǎn)發(fā)節(jié)點(diǎn)數(shù)目主要與網(wǎng)絡(luò)面積有關(guān)，并且隨節(jié)點(diǎn)密度增大而減少并趨于最小值；不同方法相比，線性距離加角度方法仍然是最優(yōu)的。圖9顯示了幾種選擇方法下廣播包的傳輸時(shí)延。對(duì)每種方法而言，節(jié)點(diǎn)密度對(duì)時(shí)延影響不大，說(shuō)明協(xié)議的時(shí)延特性具有穩(wěn)定性；而對(duì)于不同的選擇方法，傳輸時(shí)延存在明顯的差別，0.5 Linear方法具有較好的性能。綜合以上分析，增加角度判斷能夠獲得較好的轉(zhuǎn)發(fā)節(jié)點(diǎn)分布，提高算法性能；而平方根距離方法在節(jié)點(diǎn)密度較小時(shí)未能提高性能，其原因是節(jié)點(diǎn)密度較小時(shí)節(jié)點(diǎn)到理想位置的距離偏大，而平方根距離方法在d較小時(shí)才能增加區(qū)分能力，而在d較大時(shí)與線性距離方法相比得到的時(shí)延因數(shù)df會(huì)增大。SCB_delay是協(xié)議預(yù)設(shè)的時(shí)延參數(shù)，SCB_delay取值較小時(shí)，轉(zhuǎn)發(fā)時(shí)延較小，節(jié)點(diǎn)之間的時(shí)延間隔也較小，區(qū)分能力降低；SCB_delay取值較大時(shí)，不同節(jié)點(diǎn)之間的轉(zhuǎn)發(fā)時(shí)延間隔也較大，具有較好的區(qū)分能力，但取值過(guò)大會(huì)增加轉(zhuǎn)發(fā)時(shí)延且增加不同序號(hào)轉(zhuǎn)發(fā)包沖突的機(jī)會(huì)。通過(guò)仿真，SCB_delay取值為0.1 s到0.2 s時(shí)算法的送達(dá)率，轉(zhuǎn)發(fā)率和傳輸時(shí)延都能獲得較好的值。

圖7 不同節(jié)點(diǎn)選擇方法下的送達(dá)率

圖8 不同節(jié)點(diǎn)選擇方法下的轉(zhuǎn)發(fā)率

圖9 不同節(jié)點(diǎn)選擇方法下的傳輸時(shí)延

4.2 SCB與幾種廣播協(xié)議的性能比較

首先對(duì)SCB，洪泛協(xié)議，邊緣轉(zhuǎn)發(fā)協(xié)議和基于CDS的廣播協(xié)議在不同節(jié)點(diǎn)密度的條件下進(jìn)行仿真比較。200到1000個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布在面積為1000 m×1000 m 的正方形區(qū)域內(nèi)，節(jié)點(diǎn)最大速度仍為20 m/s。仿真結(jié)果示于圖10和圖11。由于洪泛協(xié)議的轉(zhuǎn)發(fā)率為100%，因此在圖11和圖13中省略。

圖10顯示，SCB的送達(dá)率明顯優(yōu)于其他對(duì)比協(xié)議，節(jié)點(diǎn)個(gè)數(shù)為200時(shí)即可獲得99%的送達(dá)率，并且隨節(jié)點(diǎn)數(shù)個(gè)增加而增大并趨于100%；而其他協(xié)議在節(jié)點(diǎn)個(gè)數(shù)為200時(shí)送達(dá)率最高且只有大約90%。這是由于當(dāng)節(jié)點(diǎn)密度增大時(shí)，3種對(duì)比協(xié)議的轉(zhuǎn)發(fā)次數(shù)增加，使得網(wǎng)絡(luò)中出現(xiàn)較多的沖突，因此3種協(xié)議的送達(dá)率都隨節(jié)點(diǎn)數(shù)目增加而降低；相反地，SCB算法基于空間覆蓋的思想，隨著節(jié)點(diǎn)密度增加，轉(zhuǎn)發(fā)節(jié)點(diǎn)的分布趨于最優(yōu)分布使得覆蓋效果更好，因此其送達(dá)率也增大。圖11中，SCB算法的轉(zhuǎn)發(fā)率明顯低于其他對(duì)比協(xié)議。節(jié)點(diǎn)數(shù)為200時(shí)，基于CDS的廣播協(xié)議和邊緣轉(zhuǎn)發(fā)協(xié)議的轉(zhuǎn)發(fā)率分別為大于70%和接近90%；而SCB的轉(zhuǎn)發(fā)率只有11.7%，并且隨著節(jié)點(diǎn)數(shù)增加而迅速降低。這是由于SCB優(yōu)化了轉(zhuǎn)發(fā)節(jié)點(diǎn)分布，明顯減少了轉(zhuǎn)發(fā)次數(shù)，因此具有更高的轉(zhuǎn)發(fā)效率；并且隨著節(jié)點(diǎn)密度增大，轉(zhuǎn)發(fā)節(jié)點(diǎn)個(gè)數(shù)減少并趨于最小值。

在不同的網(wǎng)絡(luò)規(guī)模和網(wǎng)絡(luò)負(fù)載條件下對(duì)幾種協(xié)議的性能進(jìn)行了比較。圖12顯示了不同的網(wǎng)絡(luò)規(guī)模下3種協(xié)議的轉(zhuǎn)發(fā)率，其中節(jié)點(diǎn)密度設(shè)定為1000m2/節(jié)點(diǎn)，網(wǎng)絡(luò)面積分別設(shè)置為200,000m2到1000,000m2，相應(yīng)的節(jié)點(diǎn)個(gè)數(shù)分別為200到1000；節(jié)點(diǎn)最大速度為20 m/s。在各種網(wǎng)絡(luò)規(guī)模下SCB的轉(zhuǎn)發(fā)率明顯低于另外兩種對(duì)比協(xié)議。此外，由圖12可以看出，SCB與邊緣轉(zhuǎn)發(fā)協(xié)議具有較好的可擴(kuò)展性，當(dāng)網(wǎng)絡(luò)規(guī)模增大時(shí)，轉(zhuǎn)發(fā)率呈現(xiàn)緩慢下降的趨勢(shì)；而基于CDS的廣播協(xié)議在網(wǎng)絡(luò)規(guī)模增大時(shí)，轉(zhuǎn)發(fā)率明顯增加，因此其可擴(kuò)展性較差。圖13顯示了網(wǎng)絡(luò)負(fù)載不同時(shí)協(xié)議的送達(dá)率，其中網(wǎng)絡(luò)負(fù)載分別為1 pkt/s到20 pkt/s，網(wǎng)絡(luò)環(huán)境為1000個(gè)節(jié)點(diǎn)隨機(jī)分布在1000 m×1000 m 的網(wǎng)絡(luò)區(qū)域內(nèi)。由圖13可以看到，所有協(xié)議在負(fù)載較低時(shí)都能獲得較高的送達(dá)率，隨著網(wǎng)絡(luò)負(fù)載增加，所有協(xié)議的送達(dá)率均降低，這是由于隨著負(fù)載增大網(wǎng)絡(luò)中出現(xiàn)了更多的沖突；網(wǎng)絡(luò)負(fù)載較大時(shí)，SCB的送達(dá)率明顯高于洪泛協(xié)議，邊緣轉(zhuǎn)發(fā)協(xié)議和基于CDS的廣播協(xié)議。

圖10 節(jié)點(diǎn)密度與協(xié)議送達(dá)率

圖11 節(jié)點(diǎn)密度與協(xié)議轉(zhuǎn)發(fā)率

圖12 網(wǎng)絡(luò)規(guī)模與協(xié)議轉(zhuǎn)發(fā)率

圖13 網(wǎng)絡(luò)負(fù)載與協(xié)議送達(dá)率

5 結(jié)束語(yǔ)

無(wú)狀態(tài)的廣播協(xié)議由于不需要維護(hù)鄰節(jié)點(diǎn)信息因而容易實(shí)現(xiàn)，但可能會(huì)造成轉(zhuǎn)發(fā)節(jié)點(diǎn)分布不合理，導(dǎo)致節(jié)點(diǎn)丟包；基于鄰節(jié)點(diǎn)信息的廣播協(xié)議在節(jié)點(diǎn)密度較大時(shí)會(huì)增加沖突機(jī)會(huì)，使協(xié)議性能下降；鄰節(jié)點(diǎn)指派方法在信道狀況出現(xiàn)變化時(shí)可能導(dǎo)致轉(zhuǎn)發(fā)節(jié)點(diǎn)出現(xiàn)傳輸錯(cuò)誤而使轉(zhuǎn)發(fā)失敗。本文提出了一種不需鄰節(jié)點(diǎn)信息的空間覆蓋廣播(SCB)算法，SCB通過(guò)優(yōu)化轉(zhuǎn)發(fā)節(jié)點(diǎn)的空間分布使轉(zhuǎn)發(fā)節(jié)點(diǎn)的個(gè)數(shù)最小化，在保證較高送達(dá)率的前提下明顯降低了轉(zhuǎn)發(fā)次數(shù)；同時(shí)，SCB算法由于無(wú)需鄰節(jié)點(diǎn)信息，減少了網(wǎng)絡(luò)帶寬和存儲(chǔ)計(jì)算等開(kāi)銷；此外，轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇過(guò)程在接收節(jié)點(diǎn)處分布式完成，能夠自動(dòng)適應(yīng)信道狀況，避免信道變化造成的傳輸錯(cuò)誤，增強(qiáng)了算法的實(shí)用性。

[1] Heissenbüel M, Braun T, W?lchli M, and Bernoulli T.Optimized stateless broadcasting in wireless multi-hop networks [C]. Proc. IEEE INFOCOM2006, Barcelona,Spanish, April 23-29 2006: 1-12.

[2] Khan I A, Javaid A, and Qian H L. Distance-based dynamically adjusted probabilistic forwarding for wireless mobile Ad Hoc networks [C]. IEEE and IFIP WOCN’08,Surabaya, Indonesia, May 5-7, 2008: 1-6.

[3] Liarokapis D, Shahrabi A, and Komninos A. DibA: An adaptive broadcasting scheme in mobile Ad hoc networks [C].Communication Networks and Services Research Conference 2009, Moncton, Canada, May 11-13, 2009: 224-231.

[4] Durresi A, Paruchuri V K, Iyengar S S, and Kannan R.Optimized broadcast protocol for sensor networks [J]. IEEE Transactions on Computers, 2005, 54(8): 1013-1024.

[5] Liu H, Jia X H, Wan P J, Liu X X, and Yao F. A distributed and efficient flooding scheme using 1-hop information in mobile Ad Hoc networks [J]. IEEE Transactions on Parallel and Distributed Systems, 2007, 18(5): 658-671.

[6] Khabbazian M and Bhargava V K. Efficient broadcasting in mobile Ad hoc networks [J]. IEEE Transactions on Mobile Computing, 2009, 8(2): 231-245.

[7] al-Humoud S O, Mackenzie L M, and Abdulai J.Neighbourhood-aware counter-based broadcast scheme for wireless Ad hoc networks [C]. IEEE GLOBECOM 2008 Workshops, New Orleans, USA, Nov. 30-Dec. 4 2008: 1-6.

[8] Lee Y, Shim Y, Choi Y, and Kwon T. A reliability aware flooding algorithm (RAFA) in wireless multi-hop networks[C]. IEEE Symposium on Computers and Communications 2008, Marrakech, Morocco, July 6-9, 2008: 1070-1075.

[9] Stojmenovic I, Seddigh M, and Zunic J. Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks [J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(1): 14-25.

[10] Thai M T, Wang F, Liu D, Zhu S, and Du D Z. Connected dominating sets in wireless networks with different transmission ranges [J]. IEEE Transactions on Mobile Computing, 2007, 6(7): 721-730.

[11] Yang H Y, Lin C H, and Tsai M J. Distributed algorithm for efficient construction and maintenance of connected k-hop dominating sets in mobile Ad hoc networks [J]. IEEE Transactions on Mobile Computing, 2008, 7(4): 444-457.

[12] Dai F and Wu J. Performance analysis of broadcast protocols in Ad hoc networks based on self-pruning [J]. IEEE Transactions on Parallel and Distributed Systems, 2004,15(11): 1-14.

[13] Kadi N and Al agha K. Optimized MPR-based flooding in wireless ad hoc network using network coding [C]. Wireless Days 2008 1st IFIP, Dubai, UAE, Nov 24-27, 2008: 1-5.

[14] Cai Y, Hua K A, and Phillips A. Leveraging 1-hop neighborhood knowledge for efficient flooding in wireless Ad hoc networks [C]. Proc. IPCCC 2005, Phoenix, Arizona,April 7-9, 2005: 347-354.

[15] Kershner R. The number of circles covering a set [J].American Journal of Mathematics, 1939, 61(1): 665-671.

[16] Ho C, Obraczka K, Tsudik G, and Viswanath K. Flooding for reliable multicast in multi-hop Ad hoc networks [C]. Proc.DiaLM99, Seattle, USA, 1999: 64-71.