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

　　

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