移動無線Ad Hoc網(wǎng)絡分簇算法及性能研究

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

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

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

1 Ad Hoc網(wǎng)絡介紹

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

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

2 移動無線Ad Hoc網(wǎng)絡分簇算法及性能研究

2.1 分簇算法的評價

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

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

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

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

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

更新。

2.2 最小ID啟發(fā)式算法分簇算法

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

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

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

2.3 最高節(jié)點度啟發(fā)式算法的評價

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

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

參考文獻

[1] 章靜，許力，林志偉.自組網(wǎng)中基于簇的混合密鑰管理策略[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.