Ａｄ Ｈｏｃ網絡基于權重的ＡＯＷ分簇算法研究與仿真

摘要：該文首先介紹了Ad Hoc網絡中常見的幾種分簇算法以及各自的優缺點，這些分簇算法考慮的因素較為單一。而自適應按需加權（AOW）分簇算法利用加權的思想綜合考慮多種因素，在實際應用中可以對影響因素進行取舍，也可以調整各因素的重要性，具有較強的通用性和靈活性。最后通過NS2仿真實驗對幾種分簇算法進行了比較分析，得出AOW分簇算法根據網絡環境的變化動態的調整權值更能適應復雜的網絡環境。

關鍵詞：Ad Hoc網絡；AOW；分簇

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)36-2602-03

Ad Hoc Network Based on the Weight of the AOW Clustering Algorithm and Simulation

LU Xin-rong1， HUANG Xiao-ling2

(1.Wuhan University，Wuhan 430000，China;2.Jiangxi University of Science and Technology，Ganzhou 341000，China)

Abstract: This article first introduced the Ad Hoc network of several common clustering algorithms， as well as their respective advantages and disadvantages，these algorithm consider to more single，Adaptive On-demand Weighting clustering algorithm (AOW) using weighting thought overall evaluation many kinds of factors， may carry on the choices in the practical application to the influence factor， also may adjust various factors the importance， has the strong versatility and the flexibility. Finally， through NS2 simulation of several sub-cluster algorithm for a comparative analysis，AOW clustering algorithm based on the network environment changes the dynamic of the right to adjust the value in a better position to complex network environment.

Key words: Ad Hoc network;AOW;cluster

1 引言

移動Ad hoc網絡是一組帶有無線收發裝置的移動終端(節點)組成的一個多跳臨時性自治系統。Ad hoc網絡中所有節點的地位平等，無需設置任何中心控制節點，具有很強的抗毀性。

Ad hoc網絡的體系結構可分為平面結構和分級結構[1]，如圖1所示。平面結構中，網絡中的所有節點的地位平等，理論上不存在瓶頸節點，網絡比較健壯。但在網絡規模較大，特別是在網絡拓撲變化較頻繁的情況下，平面結構具有控制開銷大，路由經常中斷等缺點，并且很難實施集中式的網絡管理和控制。在分級結構中，通常將整個Ad hoc網絡進行分簇，一個簇（Cluster）通常包括一個簇頭和若干個簇成員。簇頭負責協調和管理簇內節點，并用于相鄰簇之間的通信，而簇成員的功能則較為單一。

分級結構的網絡可擴充性好，網絡的規模受限制較小。在移動環境中，需要交換的路由和控制信息相對較少，信道的空間重用率高，從而提高了系統容量。當網絡拓撲結構發生改變時，可以將這種變化的影響限制在一定的區域內而不會擴散到整個網絡中。但是建立和維護簇結構會引入一定的開銷，可以通過設計合理的分簇算法來減少這種開銷。總之，在Ad Hoc網絡中分級結構可以對移動節點進行有效的組織并合理分配網絡資源。

2 典型的分簇算法

1) 鏈路分簇算法（LCA）

鏈路分簇算法(LCA)[2]是較早提出的一種分簇算法。LCA算法中，鄰居節點中具有最高ID的節點成為簇頭，并且如果一個節點是其某個鄰居節點的ID最高的鄰居節點，此節點也成為簇頭。該分簇算法的一種實現方法是首先選擇ID最高的節點作為簇頭。如果次高ID的節點覆蓋的范圍內存在沒有被ID最高的簇頭覆蓋的節點，那么次高ID節點也成為簇頭，否則繼續檢查下一個ID較高的節點，直到所有節點都屬于某個簇。

LCA算法最大的優點就是實現簡單，分簇過程中節點的計算量較小。但是，使用LCA算法會產生過多的簇頭，特別是當節點按ID遞增的順序線性排列時，此時除第一個節點外，其他節點都是簇頭。為了解決上述問題，可以引入簇頭消減機制來消除多余的簇頭，例如規定如果一個簇的節點都在其他簇頭的覆蓋范圍之內，則取消此簇頭的資格。LCA算法的另一個缺點是，沒有考慮公平性因素和負載平衡因素。

2) 最小ID分簇算法(LID)

最小ID分簇算法[3]也是基于節點ID的分簇算法之一。最小ID算法對LCA算法作了改進，進一步減少了簇頭的個數。算法規定，相鄰節點中具有最小ID的節點作為簇頭，其一跳鄰居節點成為該簇頭所在簇的成員節點，并不再參與簇頭選舉過程。此外，在某些特殊情況下，簇頭可以將其職責交付給簇內具有最小ID的成員節點。

最小ID分簇算法計算簡單，實現方便，算法收斂較快。在移動環境下，最小ID算法中簇頭更新的頻率較慢，維護簇花費的開銷較小。最小ID算法同樣沒有考慮公平性因素，也沒有考慮負載平衡等因素。因為，該算法傾向于選擇ID較小的節點作為簇頭，這部分節點由于充當簇頭而耗費過多的資源（如能量，處理能力等），不利于延長網絡的整體壽命。

3) 最高節點度分簇算法(HID)

最高節點度分簇算法[4]（也稱最高連接度算法）借鑒了Internet中選擇路由節點的方法，原則是盡量減少路由節點的數目，其目標是提高網絡的控制能力和減少簇的數目。每個節點通過交互控制消息來獲得鄰居節點的數目，然后它將自己的節點度向鄰居節點廣播。該節點和其相鄰節點中具有最大節點度的節點被選為簇頭；當節點度相同時，則選擇ID較小的節點作為簇頭。簇頭的一跳鄰居節點則成為該簇的成員節點，并不再參與簇生成過程，重復以上過程直到所有節點都加入到某個簇。

最高節點度算法的優點在于網絡中簇的數目較少，源目的節點對之間的平均跳數較少，從而減少了分組投遞時延。最高節點度算法的缺點是沒有對簇中簇成員的個數進行限制。當一個簇中的簇成員過多時，簇頭的負擔過重，可能會成為網絡的瓶頸。而且，當網絡中節點的移動性較低時，網絡拓撲較穩定，某些節點可能一直充當簇頭，直至其能量耗盡，同樣不利于延長整個網絡的壽命。

4) 最低移動性分簇算法(WM)

節點的移動會造成網絡拓撲的變化，為適應節點的移動特性，提高簇結構的穩定性，可以根據節點的移動性為節點分配權重，并依據節點的權重來選舉簇頭。最低節點移動性分簇算法[5]規定：節點的移動性越高，其權重越低，選擇鄰居節點中具有最高權重的節點作為簇頭，即選擇移動性最低的節點作為簇頭。在算法的實現中，可采用一種相對移動性指標來表示節點的移動性，節點通過比較收到的來自某一鄰居節點的連續兩次的信號強度來估計它們之間的相對移動性。下面介紹這種相對移動性指標的計算方法。

定義節點y相對于節點x的相對移動性指標：

(1)

其中，RxPr 表示當前節點y收到來自節點x的接收功率，RxPr 表示上一測量時刻節點y收到來自節點x的接收功率。如果My(x)<0，表示兩節點逐漸遠離；否則兩節點互相靠近。通過計算節點y和其所有m個鄰居節點xi（i

(2)

My越小，說明節點相對于鄰居節點的移動性越低，反之越高。

在移動性較強時，最低移動性分簇算法可以明顯減少簇頭更新的頻率。其缺點在于節點權重的更新比較頻繁，簇頭的計算開銷較大，并且沒有考慮系統的負載平衡和節點的能量損耗。

3 自適應按需加權AOW分簇算法

在分簇結構中，簇頭負責協調和管理簇內節點，可用于相鄰簇之間的通信，因此扮演著重要的角色。簇頭的合理選擇對采用分簇結構的Ad hoc網絡至關重要，簇頭性能的好壞直接影響到整個網絡的性能。AOW算法[6]是一種考慮多種因素的分簇算法，具有較好的適應性、靈活性和通用性。在實際應用中，為了改善分簇結構網絡的總體性能，最大限度地發揮分簇結構的優勢，簇頭的選舉應考慮多種因素，并根據實際需要和應用環境做出合理的折中。為此可以采用一種組合加權算法來選舉簇頭，在這種算法中，每個節點分配一個權值（Weight）來表示它適合充當簇頭的程度，節點的權值越小越適合充當簇頭。權值可以通過一個考慮多種因素的通用公式來計算：

Weight =a × mobility+b×degree+c×power+d×energy+x(3)

其中，mobility表示節點的移動性，degree表示節點度，power表示節點的傳輸功率，energy表示節點的剩余能量，x表示其他可能的因素對組合權值的影響，如處理能力和存儲空間等。參數a、b、c和d為權重因子，它們的值由具體的應用和網絡環境決定，并歸一化。

AOW算法中，簇頭的選擇考慮多種因素，如節點度數、節點的傳輸功率、節點的移動性和節點的剩余能量，也可根據實際情況進行取舍，并且各個因素的權重因子可以根據具體應用進行調整。AOW算法的執行只依賴于鄰居節點的消息交換，即簇頭的選擇是本地化（局部化）決定。簇結構的確定比較靈活，可以根據不同的分簇策略來形成交疊簇或非交疊簇結構，從而使算法具有較小的開銷和較強的通用性。此外，還可根據具體的應用環境對AOW算法進行相應的改進，以提高節點的公平性、優化分簇結構和進一步降低簇維護開銷。

4 不同分簇算法性能比較

為了將AOW算法與其他幾種典型的分簇算法進行比較，可以通過修改AOW算法中的權值計算部分實現最小ID分簇算法、最大節點度算分簇法和最低節點移動性分簇算法。最小ID分簇算法可以將節點ID作為權值，權值小的充當簇頭。最大節點度分簇算法中，可以用節點度的倒數作為權值。而最低節點移動性分簇算法中節點的移動性可直接作為權值。幾種分簇算法中，都是選擇權值較小的節點作為簇頭。下面通過實驗來比較這幾種分簇算法的相關性能指標。

實驗中，采用的場景是由NS中的setdest生成的隨機場景。實驗中采用的場景大小為1000m*1000m，節點數為30，節點的最大速度為 15m/s。圖中LID表示最小節點度算法，HID表示最高節點度算法，WM表示最低節點移動性算法，AOW中參數為a=0.6，b=0.2，c=0.2，Dideal=5，AOW1中參數為a=0.2，b=0.6，c=0.2，Dideal=10，其中a、b、c分別為移動性、節點度、剩余能量的權重因子。

1) 簇頭數比較

簇頭數是分簇Ad hoc網絡中的一項重要指標，網絡中的簇頭數不宜過多，

也不宜過少。下面通過實驗來比較幾種分簇算法中的簇頭數指標。比較結果如圖2所示。

由圖2可以看出隨著節點傳輸范圍的增加，簇頭數是單調遞減的。在節點傳輸范圍從20m變化到200m期間，簇頭數急劇下降。這是因為，當節點傳輸范圍較小時，相鄰節點對很少，大多數的簇僅由簇頭構成。

總體來看，HID中簇頭數是幾種分簇算法中最小的，WM中的簇頭數在大部分情況下是最大的，而LID、AOW、AOW1介于HID與WM之間。值得注意的是，由于AOW和AOW1中權重因子與理想節點度不同，起到了調節簇頭數的作用，AOW1中節點度的權重因子較大，而且理想節點度較高，因此，AOW1中的簇頭數較AOW中要小。

2) 節點重新加入簇次數比較

由于實驗中幾種分簇算法中簇頭的更新是按需的，因此網絡中簇頭的移動性對簇結構的穩定性有很大的影響，為了突出移動性的影響，下面僅比較AOW與WM中節點重新加入簇次數隨傳輸范圍的變化，比較結果如圖3所示。

由圖3可以看出，節點重新加入簇的次數隨著傳輸范圍的變化，先是急劇增加，傳輸范圍為100m時達到最大值，然后逐漸減小，趨向于某一固定值，圖中約為38。當節點傳輸范圍很小時，簇的大小幾乎都為1（只有簇頭），簇成員較少。隨著傳輸范圍的增加，網絡中簇（頭）逐漸減小，簇成員增多，因此簇成員移出簇的機會也隨之增加。這和節點的傳輸范圍也有關系，當傳輸范圍很大時，節點移出簇頭傳輸范圍的機會也很小。

實驗結果表明，選取移動性較低的節點作為簇頭可以有效地降低節點重新加入簇的次數。在AOW中可以通過調節移動性的權重因子來做到這一點。

3) 統治集更新次數的比較

下面對幾種分簇算法中統治集更新次數作出比較，比較的結果如圖4所示。

由圖4可以看出，統治集更新的次數隨節點傳輸范圍變化，先是急劇增加，直到傳輸范圍為100m時達到最大值，然后急劇下降，直到300m左右開始緩慢減少，最后趨向于一定值。

實驗結果表明，WM中統治集更新次數最小，HID中最大，而AOW與LID介于兩者之間。實驗中，HID中統治集更新次數較大，是因為HID中簇頭的選舉只考慮節點度，所選擇的簇頭具有較高的節點度，而由于節點的移動，簇頭的節點度處在變化中，兩個簇頭也會成為相鄰節點，從而導致簇結構的變化。WM中統治集更新次數較小，是因為WM中簇頭相對簇成員的移動性較小，簇結構變化較緩慢。AOW算法的該項指標介于兩者之間，可以說明AOW能在節點的移動性和節點度之間作很好的折中。

5 結束語

按需加權分簇算法綜合考慮了影響Ad hoc網絡性能的多種岡素，采用按需簇維護策略，改善了系統的靈活性和通用性；單位時間內的簇：頭更新次數和簇間轉移次數都明顯少于其它分簇算法，從而提高了系統的穩定性，節省了開銷。通過動態地調整各加權系數的值，該算法還能夠適應其它類似的系統環境。

參考文獻：

[1] 鄭少仁，王海濤，趙志峰，等.Ad Hoc網絡技術[M].北京:人民郵電出版社，2005.

[2] Baker D， Ephremides A. The Architectural Organization of a Mobile Radio Network via a Distributed Algorithm. Communications， IEEE Transactions on [legacy， pre-1988] Volume 29，Issue 11，Nov 1981 Page(s):1694-1701.

[3] Lin C R， Gerla M. A distributed architecture for multimedia in dynamic wireless networks．Global Telecommunications Conference， 1995. GLOBECOM '95， IEEEVolume 2， 13-17 Nov， 1995 Page(s):1468-1472 vol.2 Digital Object Identifier 10.1109.1995，502646 1468-1472.

[4] Gerla M， Tsai J T C．Multicluster， Mobile， Multimedia Radio Network [J]. Wireless Networks，1995，1(3):255-265.

[5] S Basagni. Distributed Clustering for Ad Hoc Networks. International Symposiun on Parallel Architectures， Algorithms and Networks， June 1999. 310-315.

[6] Amis A D， Prakash R. Load-balancing clusters in wireless ad hoc networks. Application-Specific Systems and Software Engineering Technology， 2000 Proceedings 3rd IEEE Symposium on 24-25 March 2000 Page(s):25-32.

[7] Daniel Lihui Gu， Guangyu Pei， Henry Ly， et al. Hierarchical Routing for Multi-Layer Ad-Hoc Wireless Networks with UAVs [A]. in Proceedings of IEEE Milcom 2000[C]. Los Angeles， USA， 2000(10).

[8] 王海濤.Ad Hoc網絡的體系結構和分簇算法研究[D].解放軍理工大學通信工程學院博士論文，2003(6).

[9] 英春，史美林.自組網體系結構研究[J].通信學報，1999， 20(9).

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”