劉靖永 李樂民 景小榮

①(電子科技大學通信與信息工程學院 成都 610054)②(重慶郵電大學信號與信息處理重慶市重點實驗室 重慶 400065)

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

3 實際網(wǎng)絡中的SCB算法

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

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

3.1 SCB算法的工作過程

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

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

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

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

圖4 實際網(wǎng)絡中轉 發(fā)節(jié)點的分布

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

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

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

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

3.2 理想位置的計算方法

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

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

3個理想位置分別為

3.3 轉發(fā)節(jié)點選擇方法的改進

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

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

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

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

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

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

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

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

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

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

圖7 不同節(jié)點選擇方法下的送達率

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

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

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

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

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

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

圖10 節(jié)點密度與協(xié)議送達率

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

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

圖13 網(wǎng)絡負載與協(xié)議送達率

5 結束語

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

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