【導(dǎo)讀】究所取得的研究成果。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文。不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果作品。究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。全意識(shí)到本聲明的法律后果由本人承擔(dān)。正迅速滲透到相關(guān)的民用通信領(lǐng)域。通過共享的無線信道進(jìn)行通信，無需任何固定的信息基站。各個(gè)節(jié)點(diǎn)互為中繼節(jié)。點(diǎn)，這樣可以與一些不在自身信號(hào)覆蓋范圍的節(jié)點(diǎn)進(jìn)行通信。在這樣的移動(dòng)自組。網(wǎng)絡(luò)中，廣播被頻繁的用于路由發(fā)現(xiàn)、地址解析和許多其他網(wǎng)絡(luò)服務(wù)中。Hoc的性能有著十分重要的意義。因此擁有高效率的廣播算法是無線路由協(xié)議研究的關(guān)鍵和前提。改進(jìn)以概率為基礎(chǔ)的算法，參考轉(zhuǎn)發(fā)節(jié)點(diǎn)間的距離，針對(duì)各種網(wǎng)絡(luò)結(jié)構(gòu)設(shè)置。動(dòng)態(tài)調(diào)整節(jié)點(diǎn)轉(zhuǎn)發(fā)概率的實(shí)現(xiàn)為減少廣播風(fēng)暴對(duì)網(wǎng)絡(luò)影響的目標(biāo)。提供了一種可靠有效的方案。

　　

【正文】 。 Ad Hoc 網(wǎng)絡(luò)中廣播風(fēng)暴 當(dāng)前尚無一種專門為 Ad hoc 網(wǎng)絡(luò)設(shè)計(jì)的廣播協(xié)議。由于泛洪式廣播 (Flooding)不需要任何特殊的設(shè)備或算法，因此是廣為采用的一種方法，而在 Ad hoc 網(wǎng)絡(luò)上的廣播，也大多以泛洪式廣播法來進(jìn)行。泛洪式廣播法是一種簡單的執(zhí)行策略，在這個(gè)策略下，所有的節(jié)點(diǎn)不論何時(shí)收到第一個(gè)廣播包都有義務(wù)將這個(gè)廣播包繼續(xù)傳給它鄰近的節(jié)點(diǎn)。這種方法雖然簡單易于實(shí)現(xiàn)，但也會(huì)造成許多信息重復(fù)的被傳送而產(chǎn)生冗余 (Redundancy)、競爭 (Contention)、以及碰撞 (Collision)，繼而形成廣播 風(fēng)暴 (Broad Cast Storm Problem)。 廣播信息冗余分析 移動(dòng) Ad Hoc 網(wǎng)絡(luò)中的節(jié)點(diǎn)一般使用全向天線，其覆蓋范圍內(nèi)的節(jié)點(diǎn)都可以收到信號(hào)。如果當(dāng)節(jié)點(diǎn)準(zhǔn)備轉(zhuǎn)發(fā)收到的廣播時(shí)，其所有的鄰居節(jié)點(diǎn)已經(jīng)收到該廣播包，該廣播稱之為冗余廣播。產(chǎn)生冗余的主要原因是來自不同發(fā)射天線的無線信號(hào)很容易相互重疊。如圖 所示，節(jié)點(diǎn) S 將報(bào)文廣播出去，周圍節(jié)點(diǎn)都收到了信息報(bào)文并進(jìn)行轉(zhuǎn)發(fā)，而此時(shí)節(jié)點(diǎn) 2 的廣播就是冗余廣播 (虛線圓內(nèi)為節(jié)點(diǎn) 2的覆蓋地區(qū) )，這是因?yàn)楣?jié)點(diǎn) 2 廣播所覆蓋的范圍已經(jīng)被其他廣播覆蓋過， 圖中的絕大部分區(qū)域都被重覆蓋過，其中有的區(qū)域被 4 個(gè)節(jié)點(diǎn)同時(shí)覆蓋，由此產(chǎn)生很大的冗余。 圖 廣播冗余示意圖 湖南人文科技學(xué)院畢業(yè)設(shè)計(jì) 我們來對(duì)廣播冗余來簡單分析，由于轉(zhuǎn)發(fā)廣播信息帶來了信號(hào)覆蓋面積的增益。如圖 中，節(jié)點(diǎn) A 發(fā)送一個(gè)廣播包，而節(jié)點(diǎn) B 轉(zhuǎn)發(fā)這個(gè)廣播包。用 S a 和S b 分別 表示 A 和 B 的傳輸覆蓋面積，陰影部分 S ba 表示 B 轉(zhuǎn)發(fā)的額外覆蓋面積。假設(shè) A 和 B 的半徑為 r， A 和 B 的圓心距為 d，于是 |S ba|= ∏ r2 INTC(d)，其中 INTC(d)是圓心距離為 d 的兩個(gè)圓之間的重疊面積： 圖 節(jié)點(diǎn)轉(zhuǎn)發(fā)廣播 信息帶來的覆蓋增益 ? ? dxxrdI N T C rd? ?? 2 224)( () 當(dāng) d=r 是，覆蓋面積 |S ba|最大，此時(shí) |S ba| = ∏ r2 INTC(d) = r2( ∏ /3 + 23 ) ≈ ∏ r2 () 以上分析表明，一次廣播轉(zhuǎn)發(fā)能在以前傳輸?shù)幕A(chǔ)上提供 0~60%的額外覆蓋面積。同樣，還可以得到額外覆蓋面積的平均 值。假設(shè) B 能隨機(jī)位于 A 覆蓋范圍中的任意一點(diǎn)，其平均值可以通過圓半徑 x 在 [0, r]上的積分得到： ? ?? ??? ????r rdxr dI N T Crx0 222 )(2 () 由此可見，在前一次廣播后，轉(zhuǎn)發(fā)廣播信息只能提供平均 41%的額外覆蓋面積?，F(xiàn)在考慮如果主機(jī) C 收到 A 和 B 的廣播后決定繼續(xù)廣播， C 轉(zhuǎn)發(fā)可以獲得的額外面積為 |Sc A∩ B| ≈ [12] ，這表明在此情況下通過廣播轉(zhuǎn)發(fā)來找新主機(jī)的可能性事非常小的。 對(duì)于一般情況，一個(gè)主機(jī)在收到一條 消息 k 次以后轉(zhuǎn)發(fā)該消息所帶來的覆蓋增用 ECA(k)表示。當(dāng) k ≥4 時(shí)，額外覆蓋面積小于 5%[16]。 湖南人文科技學(xué)院畢業(yè)設(shè)計(jì) 信道競爭分析 廣播風(fēng)暴的另一個(gè)問題就是節(jié)點(diǎn)之間對(duì)信道的競爭。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)密度大時(shí)，產(chǎn)生競爭的幾率就會(huì)變大。 還是圖 ，假設(shè)主機(jī) A 發(fā)送廣播消息以后有 N 個(gè)主機(jī)接收到這條消息，因?yàn)?A 周圍可能有兩個(gè)以上的主機(jī)很接近，如果這些主機(jī)都想轉(zhuǎn)發(fā)這條廣播消息，就可能產(chǎn)生無線信道的爭搶。 分析當(dāng) N=2 的簡單情況。假定 B 和 C 是兩個(gè)接收主機(jī)， B 在 A 傳輸范圍內(nèi)的位置隨機(jī)。當(dāng) C 位于 SA∩ B 的時(shí)候，就會(huì)產(chǎn)生競爭，所以競爭的概率是 |SA∩B| / ∏ r2。 設(shè) A 和 B 的距離為 x，則 C 和 B 產(chǎn)生競爭的概率為： ? ?? ????r dxr rxI N T Cx0 0022 59)(2 () 顯然，當(dāng)轉(zhuǎn)發(fā)節(jié)點(diǎn)個(gè)數(shù) N 增加時(shí)，競爭的 機(jī)會(huì) 也變大。如果 在 A 的傳輸范圍內(nèi)隨機(jī) 存在 的 N 臺(tái)主機(jī)中 K 臺(tái)主機(jī)轉(zhuǎn)發(fā)廣播信息不發(fā)生競爭的概率為 CF(n, k)，所有 N 臺(tái)主機(jī)發(fā)生競爭的概率在 N≥ 6 時(shí)迅速增加到 [3]以上。另一方面，有一臺(tái)主機(jī)發(fā)送時(shí)不發(fā)生信道爭搶的概率 CF(n, k)隨著 N 增加迅速下降。再者，幾乎不存在多臺(tái)主機(jī) (k≥ 2)發(fā)送時(shí)不發(fā)生信道爭搶的情況。 信號(hào)碰撞分析 在 MANET 中，沒有基站和接入點(diǎn)。因此，對(duì)于使用 IEEE 802． 11Mac 分類的中心協(xié)調(diào)方式 (PCF)工作模式不予考慮，而主要研究在分布式協(xié)調(diào) 方式 (DCF)工作模式下的行為。 CSMA/CA 機(jī)制需要一臺(tái)主機(jī)在發(fā)送一條消息后，或是當(dāng) 主機(jī)有消息發(fā)送并且前面的退避程序已經(jīng)結(jié)束，但是發(fā)現(xiàn)信道媒介正在被占用的時(shí)候，立即啟動(dòng)一個(gè)備份程序。執(zhí)行退避程序時(shí)，首先要從現(xiàn)有的退避窗口隨 機(jī)選取了 一 個(gè)整數(shù)作為計(jì)數(shù)，如果主機(jī)的信道清除評(píng)估 (CCA)機(jī)制探測 到在過去的時(shí)間間隙內(nèi) ( 一個(gè)固定的時(shí)期 )信道空閑，計(jì)數(shù)器就減 1。當(dāng) 計(jì)數(shù)器值到 0 時(shí)，退避程序完成。 考慮幾個(gè)相鄰主機(jī)都接收到主機(jī) x 廣播信息的情形下，產(chǎn)生碰撞的原因有以下幾個(gè)。首先，如果 x 周圍的信道長時(shí)間空閑， x 的鄰居也許都已經(jīng)完成了它湖南人文科技學(xué)院畢業(yè)設(shè)計(jì) 們的退避程序。那么，當(dāng)收到廣播消息后，它們就可能 同時(shí)開始轉(zhuǎn) 發(fā)此廣播信息。特別是由于存儲(chǔ)轉(zhuǎn)發(fā) (RF)延時(shí)和傳輸延時(shí)造 成載波檢測不及時(shí)的時(shí)候，這種現(xiàn)象特別明顯。第二，由于在廣播傳輸 中沒有使用 RTS／ CTS 預(yù)警對(duì)話機(jī)制，碰撞將會(huì)更加嚴(yán)重。第三，一旦發(fā) 生了碰撞，由于沒有沖突檢測 (CD)機(jī)制，即使已經(jīng)發(fā)送的比特已不可 用，主機(jī)仍將一直傳輸完該分組，而且分組越長，浪費(fèi)越大。 現(xiàn)有應(yīng)對(duì) Ad Hoc 網(wǎng)絡(luò)廣播風(fēng)暴的機(jī)制 由于廣播風(fēng)暴產(chǎn)生的主要原因是廣播報(bào)文的重復(fù)傳送，進(jìn)而導(dǎo)致競爭和碰撞的情況 。由此出發(fā)，目前對(duì)降低廣播風(fēng)暴發(fā)生的研究，大多是從減少報(bào)文傳送數(shù)量來著手。當(dāng) 下比較常用的廣播方法有這幾類：基于概率的方法、基于計(jì)數(shù)器的方法、基于距離的方法、基于位置的方法、基于角度的方法、基于角度的方法。這里簡單的洪泛法就不做介紹了，下面我們介紹一下這些應(yīng)對(duì)廣播風(fēng)暴的方法。 概率型算法 概率算法 (Probabilistic Scheme)，它與洪泛相似，只是當(dāng)節(jié)點(diǎn)收到一個(gè)廣播信息時(shí)僅以概率 p 轉(zhuǎn)發(fā)該信息。在這種情況下，概率 p 的選擇尤為關(guān)鍵。概率的減小會(huì)降低廣播風(fēng)暴的作用，覆蓋范圍也隨之減小。顯然， p=1 時(shí)，本方案相當(dāng)于洪泛。 考慮到信道爭搶和碰撞的問題，應(yīng)該在轉(zhuǎn)發(fā)消息 前加上一個(gè)小的隨機(jī)時(shí)延，這樣就可以使得轉(zhuǎn)發(fā)在世間上更加分散。本算法的優(yōu)點(diǎn)就是簡單易行，降低了延時(shí)和帶寬損耗。但是，在這種算法中，要實(shí)時(shí)地對(duì)節(jié)點(diǎn)進(jìn)行評(píng)估，所以該算法可能不能找到源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最佳路徑，而且，對(duì)某以網(wǎng)絡(luò)結(jié)果的最佳概率 p并不一定是另一個(gè)網(wǎng)絡(luò)結(jié)構(gòu)的最佳概率。 基于計(jì)數(shù)器算法 計(jì)數(shù)器 算法 (CounterBased Scheme)，計(jì)數(shù)器的基本思想是節(jié)點(diǎn)收到相同報(bào)文的次數(shù)反比于轉(zhuǎn)發(fā)報(bào)文所獲得的額外覆蓋面積。當(dāng)節(jié)點(diǎn)首次收到一個(gè)報(bào)文時(shí)啟動(dòng)一個(gè)計(jì)數(shù)器 (其初始值為 1) 和一個(gè)定時(shí)器 RAD(其 超時(shí)時(shí)間在 0s 到 T max之間隨湖南人文科技學(xué)院畢業(yè)設(shè)計(jì) 機(jī)選擇 )。在此期間，節(jié)點(diǎn)沒收到這個(gè)報(bào)文一次，計(jì)數(shù)器就加 1。當(dāng)計(jì)時(shí)器超時(shí)且計(jì)時(shí)器小于一個(gè)門限值 C，則節(jié)點(diǎn)對(duì)該報(bào)文進(jìn)行轉(zhuǎn)發(fā)，否則丟棄該報(bào)文。如圖，假設(shè)節(jié)點(diǎn)使用計(jì)數(shù)器廣播算法且 C=2，節(jié)點(diǎn) 3 相互之間為一跳鄰居?，F(xiàn)節(jié)點(diǎn) 1 發(fā)送一個(gè)廣播報(bào)文，節(jié)點(diǎn) 2 和節(jié)點(diǎn) 3 收到該報(bào)文后啟動(dòng)定時(shí)器并分別是c=1。如果節(jié)點(diǎn) 3 的定時(shí)器先超時(shí)并收到報(bào)文，則節(jié)點(diǎn) 2 收到來自節(jié)點(diǎn) 3 的報(bào)文后 c 加 1。由于節(jié)點(diǎn) 2 的 c 值已經(jīng)達(dá)到 C(C=2)，所以不對(duì)報(bào)文進(jìn)行轉(zhuǎn)發(fā)。這樣節(jié)點(diǎn) 4 將不會(huì)收到來自節(jié)點(diǎn) 1 的報(bào)文。另外，隨機(jī)時(shí) 延的引入會(huì)導(dǎo)致報(bào)文傳輸時(shí)間延長。如果在按需路由協(xié)議的路由發(fā)現(xiàn)過程中會(huì)導(dǎo)致路由查找時(shí)間增大。 圖 計(jì)數(shù)器算法示意圖 根據(jù)本文 節(jié)所介紹的，接收到同一條消息 k 次后再轉(zhuǎn)發(fā)所能獲得的額外覆蓋范圍 EAC(k)，它隨著 k 的增加而迅速減小。當(dāng)這個(gè)值太低的時(shí)候，我們應(yīng)該禁止該主機(jī)轉(zhuǎn)發(fā)，基于計(jì)數(shù)器的方案就是基于這一點(diǎn)設(shè)計(jì)的。具體的說，用一個(gè)計(jì)數(shù)器 c 來跟蹤記錄廣播消息收到的次數(shù)。選擇一個(gè)計(jì)數(shù)器門限值 C，當(dāng) c≥C 時(shí)，節(jié)點(diǎn)轉(zhuǎn)發(fā)禁止。 這種算法于洪泛相比，在主機(jī)分布密集的時(shí)候，計(jì)數(shù)器算法可以減少許多冗余廣播包，但它在 一定程度上增加了每個(gè)節(jié)點(diǎn)的時(shí)延。另外，此算法運(yùn)用在稠密的網(wǎng)絡(luò)環(huán)境中時(shí)一些節(jié)點(diǎn)將不會(huì)進(jìn)行轉(zhuǎn)發(fā)，在節(jié)點(diǎn)稀疏的環(huán)境中，有可能所有的節(jié)點(diǎn)都參與轉(zhuǎn)發(fā)。 基于距離算法 基于距離的算法 (DistanceBased Scheme)，算法根據(jù)主機(jī)之間的距離判斷節(jié)點(diǎn)是否需要對(duì)廣播報(bào)文進(jìn)行轉(zhuǎn)發(fā)。例如，節(jié)點(diǎn) H 收到來自其鄰居節(jié)點(diǎn) S 發(fā)送的廣播報(bào)文時(shí)， H 得到它與 S 的距離 d。如果 d 很小，則 H 對(duì)來自 S 的報(bào)文的轉(zhuǎn)發(fā)所獲得的額外覆蓋面積也就小，否則額外覆蓋面積就大。極端情況，如果 d=0，湖南人文科技學(xué)院畢業(yè)設(shè)計(jì) 則 H 對(duì)報(bào)文的轉(zhuǎn)發(fā)對(duì)于探索新區(qū)域沒有任何貢 獻(xiàn)。反之，如果 S 與 H 之間的距離等于節(jié)點(diǎn)的傳輸半徑，則 H 對(duì)報(bào)文的轉(zhuǎn)發(fā)可獲得最大的額外面積。因此，基于距離的算法以節(jié)點(diǎn)間的距離作為判斷節(jié)點(diǎn)是否轉(zhuǎn)發(fā)廣播的準(zhǔn)則。若節(jié)點(diǎn)與廣播上一跳節(jié)點(diǎn)的距離小于一個(gè)預(yù)先給定的值 D，則丟棄該報(bào)文?；诰嚯x的算法同樣存在覆蓋率 低的問題。我們?nèi)砸詧D 為例，假定網(wǎng)絡(luò)中的節(jié)點(diǎn)執(zhí)行基于距離的廣播算法，如果節(jié)點(diǎn) 1 與節(jié)點(diǎn) 2 的距離以及節(jié)點(diǎn) 1 與節(jié)點(diǎn) 3 的距離都未超過極限值 D，則節(jié)點(diǎn) 4 不會(huì)收到來自節(jié)點(diǎn) 1 的信息。 基于位置算法 基于位置的算法 (LocationBased Scheme)，在基于位置的廣播算法中，每當(dāng)節(jié)點(diǎn)發(fā)起或轉(zhuǎn)發(fā)一個(gè)廣播報(bào)文時(shí)，節(jié)點(diǎn)將自己的位置信息添加到報(bào)文中，這樣接收節(jié)點(diǎn)即可獲得發(fā)送節(jié)點(diǎn)的位置并計(jì)算出轉(zhuǎn)發(fā)所獲得的額外覆蓋面積。如果計(jì)算出的額外面積小于一個(gè)門限值，節(jié)點(diǎn)將不對(duì)接收到的報(bào)文轉(zhuǎn)發(fā)。否則節(jié)點(diǎn)緩存數(shù)據(jù)并等待一個(gè)隨機(jī)時(shí)間。如果在等待期間內(nèi)接收到相同的消息，節(jié)點(diǎn)重新計(jì)算額外覆蓋面積并與門限值比較。如果等待時(shí)間到了，并且計(jì)算出轉(zhuǎn)發(fā)所獲得的額外覆蓋面積仍大于門限值則轉(zhuǎn)發(fā)這個(gè)報(bào)文。 該算法需要節(jié)點(diǎn)的具體位置來計(jì)算出額外覆蓋面積 EAC(A)，這就可以利用位置裝置如全球定位系 統(tǒng) GPS 提供服務(wù)。假設(shè)一個(gè)節(jié)點(diǎn)的位置在 (0, 0)處，它從位置為 (x1, y1)， (x2, y2)， … ..， (xn, yn)的 k 的節(jié)點(diǎn)接收相同的消息，我們用 AC((x1, y1)， (x2, y2)， … ..， (xn, yn))來表示該額外覆蓋面積與 πr2 的比值。那么我們可以用該值與預(yù)定的覆蓋門限 A 相比較來決定是否將接收到的消息重新廣播。這種方法的困難之處在于計(jì)算 AC，因?yàn)槲覀冃枰?jì)算一些圓中重疊的面積。在只有四個(gè)圓的時(shí)候，計(jì)算 AC 就已經(jīng)比較難了。一個(gè)可行的辦法就是用用網(wǎng)格填充來估計(jì) AC 的值。下面我們通過圖形來 分析。 假定主機(jī) X 收到從 A、 B、 C 發(fā)送的廣播消息各一次，比較圖 和圖 ，容易得到如果 X 不在該多邊形內(nèi)，它將能提供更多的額外覆蓋范圍 (陰影部分所示 )。通過上述觀察，我們可以規(guī)定只有當(dāng)主機(jī)不在凸多變形內(nèi)時(shí)才能進(jìn)行轉(zhuǎn)發(fā)。 湖南人文科技學(xué)院畢業(yè)設(shè)計(jì) 圖 主機(jī)位于有三個(gè)發(fā)送主機(jī)組成的三角形內(nèi) 圖 主機(jī)位于有三個(gè)發(fā)送主機(jī)組成的三角形之外 圖 使用多邊形測試可獲得的最大額外覆蓋面積分析 我們通過幾何計(jì)算來證明采用以上策略的原因。如果 X 在多邊形內(nèi)，通過 邊形測試禁止主機(jī) X 轉(zhuǎn)發(fā)，那么最多有 22%[4]的額外覆蓋面積丟失。我們可以注意到，當(dāng) X 落在多邊形的邊界上時(shí)。所能獲得的額外覆蓋面積最大。假定 A 和B 是這個(gè)邊界的兩個(gè)端點(diǎn)，當(dāng) A 和 B 被傳輸半徑為 r 的主機(jī) X 分開如圖 時(shí)，X 提供的額外覆蓋最大，該面積為 [15]： 222022222 rrdxxrdxxrr rr ???????? ????????? ???? ? 這種算法雖然具備很高的可達(dá)性，但還需要如 GPS 這種設(shè)備的配合，以便為每個(gè)節(jié)點(diǎn) 提供定位信息，這和 Ad Hoc 網(wǎng)絡(luò)不需要預(yù)先設(shè)置的基礎(chǔ)設(shè)施定義不符。此外要得到額外覆蓋面積需要計(jì)算很多圓的交集，開銷很大，這樣會(huì)消耗節(jié)湖南人文科技學(xué)院畢業(yè)設(shè)計(jì) 點(diǎn)寶貴的能量資源。 基于角度算法 角度算法 (Angle Scheme )，角度算法是利用主機(jī)之間的相對(duì)角度來判斷是否轉(zhuǎn)發(fā)廣播信息的策略。 假設(shè)我們已知主機(jī)節(jié)點(diǎn) S 和它們的鄰居節(jié)點(diǎn) N 以及它們的覆蓋半徑 RS， RN如圖 所示。 A 和 B 是以 S 和 N 為圓心，以各自的覆蓋半徑 RS， RN為半徑的兩個(gè)交點(diǎn)。取 S 的正東方以 RS為