移動無線Ad Hoc網絡分簇算法及性能研究

摘要：自組網以其組網的靈活特性正越來越受到人們的關注。在移動自組網絡中，許多應用都依賴層次結構的支持。簇結構是移動自組網絡中應用最為廣泛的層次結構。文章闡述了Ad Hoc網絡的體系結構和存在的問題，討論了Ad Hoc網絡中幾種典型的分簇算法。

關鍵詞：移動無線Ad Hoc；自組網；分簇算法；密鑰管理

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-2374（2013）16-0032-02

1 Ad Hoc網絡介紹

Ad Hoc網絡是一種無線移動通信網絡，其前身是分組無線網絡（Packet Radio Network）。Ad Hoc網是一種無線網絡，英文可譯為Multi-hop Network、Infrastructureless、NetworkSelf-or-ganizing Network等，是一種較為新的通訊技術手段。

這里提出的“Ad Hoc”指的是一種無線特定的網絡結構，強調的是多跳、自組織、無中心的概念。該網絡具有信息收集和傳遞功能，各個節點相互獨立，且可以任意組合成一個面向特定工作任務的網絡拓撲結構。

2 移動無線Ad Hoc網絡分簇算法及性能研究

2.1 分簇算法的評價

在Ad Hoc網絡架構中，常采用分簇算法，而分簇算法最關鍵的是利用簇頭作為判定是否在同一網絡鏈路中的條件。換言之，Ad Hoc網絡依靠鄰節點之間交換信息，從而互聯成網絡，其分簇算法要以分布的方式來設計和運行。

我們對分簇算法的評價的假設：

網絡中采用兩種頻率進行通信。簇頭之間采用一種頻率進行通信，節點之間采用另一種頻率進行通信。簇頭之間在通信時采用的密鑰與簇內采用的密鑰是不同的。即簇頭之間在通信時采用一種加密機制，本網絡中打算采用非對稱加密RSA；簇內成員之間采用另一種加密機制，本網絡打算采用DES對稱加密算法。

對密鑰進行管理時，主要考慮密鑰管理的前向性和后向性問題。當某一個簇中有節點離開，對本簇而言：若離開的節點是簇頭時，則要重新進行簇頭的選舉，重新建立通信密鑰的管理與分配；若某個普通節點離開，則本簇的簇頭要負責進行簇內通信的密鑰更新。一個簇中有節點加入，在節點加入之前要先實現本簇的密鑰更新，使得新加入的節點無法獲取之前的信息。

觸發密鑰更新機制：有節點出入要更新一個簇，若其在一段較長時間內保持拓撲結構不變，則也要進行密鑰

更新。

2.2 最小ID啟發式算法分簇算法

在實際采用分簇算法時，一般使用最小ID啟發式算法，之所以采用該方法，主要是考慮到該分簇算法計算量小、實現方便、算法收斂較快，類似路由中的最短路徑算法。

網絡拓撲結構變化的時候，引發密鑰更新。新密鑰更新的過程中，節點要付出計算新密鑰的計算代價。在計算出密鑰后，需要在所有簇頭的共同管理下，對整個網絡進行密鑰更新，密鑰傳輸過程中需要消耗通信代價。總的來說，網絡拓撲結構變化后，所導致的代價為計算代價和通信代價。

由仿真程序可以看出，用最小ID分簇算法來進行分簇，網絡中產生的簇頭數目比最大連通度分簇算法所產生的多，且效果較好。

2.3 最高節點度啟發式算法的評價

3 基于團和補圖理論的分簇仿真

基于團與補圖的著色的思想，根據以下的算法步驟：（1）任意選取若干發起者；（2）以此點為中心求其一跳補圖；（3）得到最小度數點u，設顏色為1；（4）中心點的一跳鄰居啟動計時器T，T先消亡者為中心并賦上顏色2，并將其為中心的消息發給其鄰居節點。求新中心節點的一跳補圖。

參考文獻

[1] 章靜，許力，林志偉.自組網中基于簇的混合密鑰管理策略[J].計算機應用，2006，（6）.

[2] David A. Beyer. Accomplishments of the DARPA Survivable Adaptive Networks SURAN Program. In Proceedings of the IEEE MILCOM Conference， 1990.

[3] Barry M. Leiner， Robert Ruth， and Ambatipudi R. Sastry. Goals and Challenges of the DARPA GloMo Program. IEEE Personal Communications，Vol.3， No.6，1996.

[4] http：//www.ieee802.org/11/.

[5] Mobile Ad hoc Networks. http：//www.ietf.org/html.charters/Ad hoc network-charter.html.May，2000.