移動自組網的分簇算法研究

摘要本文分析了移動自組網的現有分簇算法，并針對現有分簇算法的不足對ntdr進行了改進，提出了基于按需加權的ntdr（dwntdr）。
關鍵詞：移動自組網,分簇,分簇算法

在移動自組網環境中，分簇的入侵檢測系統能有效控制移動節點間的入侵檢測通信開銷，節約網絡資源和節點能量，實現高效協作式檢測機制。因此，移動自組網ids采用分簇結構能否高效，ids分簇算法起著非常重要的作用。

2 幾種典型移動自組網分簇算法

移動自組網的分簇算法目標就是以較少的計算和通信開銷來構造與維護一個簇集合，使其能在覆蓋整個網絡的同時較好地支持資源管理和路由協議的相互連接，并在網絡結構發生變化時生成新的簇結構，確保網絡正常通信。在此將對幾種典型分簇算法進行闡述。

1. 最小id分簇算法

最小id分簇算法，它由grela和tsai在鏈路分簇算法（lca）基礎上改進而得。該

算法特點是計算簡單, 實現方便，算法收斂較快。但是該算法節點消耗的能量多,而且加快了網絡出現分割的時間, 同時沒有考慮負載平衡等因素。

2. 最高節點度分簇算法

該算法特點是簇數目較少，減少了分組投遞時延, 但同時也減少了信道空間重用率。由于簇內節點數不受限制, 并且信道由節點共享, 當簇內節點數量過多時, 每個節點的吞吐量急劇下降。此外, 當節點移動性較強時, 簇頭更新頻率較高，簇維護開銷較大。因此，該算法適合于移動性較弱且節點密度較低的場合。

3. 最小移動性分簇算法

最小移動性分簇算法是節點權值分簇算法的一種，在移動性較強時, 該算法可以明顯減少簇頭更新頻率。它的缺點是節點權重的更新較頻繁, 簇頭計算開銷較大, 并且未考慮負載平衡和節點能量損耗問題。

4．ntdr

該算法優點是分簇時間短，而且為了彌補當原簇頭失效的情況，當某一個簇頭失效時，會有一個新簇頭被迅速選舉出來。缺點是產生的簇頭數相對過多，系統穩定性不強，原因是節點聲明為簇頭時沒有考慮節點的各方面的綜合能力，導致加入該簇的成員相對較少，增加了簇頭的個數，同時也增加通信開銷。

3 基于按需加權的ntdr（dwntdr）

前三種分簇算法都只是單純的分簇算法，沒有考慮移動自組網入侵檢測和軍事方面的需要。而ntdr專門應用于軍事方面，對于移動自組網入侵檢測來說具有更大的實用性。但ntdr產生的簇頭數相對過多，系統穩定性不強。因此在此對其進行改進，提出一種基于按需加權的ntdr（dwntdr，on-demand weighting ntdr）。

此算法根據每個節點的權值來選擇簇頭，權值較小的節點優先成為簇頭。在計算節點權值時，綜合考慮它的節點度、剩余能量和移動性。為了增加簇結構的穩定性，減少簇頭的更新次數，還為原有簇頭引人了一定的增量以減小其權值，使其再次被選舉為簇頭的可能性增加。節點權值的計算公式為:

w（n）=a·|d（n）-m|+b·t（n）+c·m（n）+d·p（n）-x

其中: d（n）表示節點n的節點度，m表示每個簇內理想的簇成員數；t（n）表示節點n擔當簇頭的時間；m（n）表示節點n的平均移動速度；p（n）表示到所有鄰居節點的距離之和；x表示一個增量；a，b，c,d表示加權系數，且滿足a+b+c+d=1。

其算法描述為：

（1）網絡各節點分配唯一id標識，并分配相同的能量。

（2）一個dwntdr節點如果發現它的附近沒有一個簇頭節點，或者是它探測到自己可以修復一個網絡分割，并且在鄰居節點中具有最小w，則認為自己要成為簇頭。如果w相同，則選擇id最小的為簇頭。

（3）每個新的簇頭在認定自己為簇頭后，則立即聲明自己的簇頭地位。

（4）其一跳鄰居節點中沒有加入某個簇的節點成為該簇成員節點，并不再參與分簇。

（5）已經是某個簇的成員節點一般保持簇從屬關系不變，但在下列情況發生時，也可以加入此簇頭，并不再參與分簇，包括：簇頭放棄自己的簇頭地位、簇頭已經不再列出這個節點、到簇頭的鏈路狀況已經惡化到無法接受的程度以及從簇頭接收的信號強度過低。

（6）如果簇頭同意該節點加入，則向所有其它的簇頭發布立即更新后的簇內成員列表，通告其它所有簇頭該節點已經屬于自己這個簇，明確這個節點的當前位置。如果新加入的節點在加入該簇之前屬于另外一個簇，則簇頭還要通告該節點以前的簇頭，指示該節點已經有了新的簇從屬關系。

（7）簇頭在自己的剩余能量小于某個規定的閾值時則放棄自己的簇頭地 位，不再為簇頭。

（8）剩余重復執行（2）～（7）步驟，直到所有節點都屬于某個簇。

為了減小簇維護所引入的系統開銷，采取按需策略，規定只有當網絡中的某個節點與現有的任何簇頭都不是相鄰節點時，才重新選舉簇頭。

4 算法模擬與分析

為了便于實現，本文用java語言編制的簡單模擬環境來對上述五種分簇算法進行模擬與分析。模擬環境為在一個100×100 單位距離的區域內隨機放置n 個節點, 節點移動方向在[0, 2∏]內隨機分布, 移動速度在[0,maxv ]內變化。當節點到達區域邊界時, 它向區域內反射。節點的數量、傳輸范圍（以單位距離數表示）和移動速度均可根據要求動態調整，模擬時間為10000個單位時間。主要通過不同移動環境下的算法模擬結果來對比分析五種分簇算法的性能，這五種算法分別是最小id算法（lowid）、最大連接度算法（highd）、最小移動性算法（lowm），ntdr、基于按需加權的ntdr（dwntdr）。

在此取網絡節點數n=30，maxv=5，節點傳輸范圍從5～60單位距離變化。對于基于按需加權的ntdr，理想的簇成員m=8，a=0.2，b=0.3，c=0.3，d=0.2，x=1，并且節點剛開始的能量是1000能量單位，每單位時間簇頭消耗能量0.2%，簇成員為0.05%，能量閾值為100能量單位。

簇頭數隨節點傳輸范圍的增加而減少, 當傳輸范圍大于30后, 速度逐漸變慢。dwntdr，ntdr的平均簇頭數略多于最小移動性和最小id分簇算法的平均簇頭數。并且dwntdr的簇頭數較ntdr要少, 主要是因為dwntdr比ntdr多考慮了節點度，速度等因素，減少了冗余簇頭的產生。

最高節點度分簇算法的單位時間內的簇間轉移次數略高于其它分簇算法。而dwntdr單位時間內的簇間轉移次數較其它算法要低，由此可以說明dwntdr的簇結構穩定性遠大于另外幾種分簇算法。

綜上所述，通過對不同算法的模擬與分析，可以看出dwntdr分簇算法在穩定性，對網絡拓撲變化的適應力等方面要明顯優于其它幾種算法，而且dwntdr還保留了ntdr算法在原簇頭失效時迅速選出新簇頭的優點，從而改善了系統的靈活性和通用性，提高了簇結構的穩定性，更加適應移動自組網入侵檢測。

5 結束語

本文針對現有移動自組網分簇算法的不足之處在此基礎上對ntdr進行了改進，提出基于按需加權的ntdr（dwntdr），該算法綜合考慮了影響移動自組網性能的節點度，速度等多種因素，改善了系統的靈活性和通用性，提高了簇結構的穩定性，更適合移動自組網入侵檢測系統。

參考文獻（略）

本文收集整理于網絡，如有侵權請聯系客服刪除！