胡波

1 福建省財稅信息中心 福建 350003

2 中南大學信息科學與工程學院 湖南 410083

0 引言

在移動自組網(wǎng)環(huán)境中，分簇的入侵檢測系統(tǒng)能有效控制移動節(jié)點間通信開銷，節(jié)約網(wǎng)絡(luò)資源和節(jié)點能量，實現(xiàn)高效協(xié)作式檢測機制。因此，移動自組網(wǎng)IDS采用分簇結(jié)構(gòu)能否高效，分簇算法成為實現(xiàn)的關(guān)鍵技術(shù)之一。

1 分簇定義及分簇算法目標

移動自組網(wǎng)分簇是一種將節(jié)點分成邏輯上獨立的組的一種機制。分簇算法目標是以較少的計算和通信開銷來構(gòu)造與維護一個簇集合，使其能在覆蓋整個網(wǎng)絡(luò)的同時較好地支持資源管理和路由協(xié)議的相互連接，并在網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化時生成新的簇結(jié)構(gòu)，確保網(wǎng)絡(luò)正常通信。為減少分簇開銷，分簇算法應(yīng)簡單高效，理想情況下希望以最少的簇頭覆蓋整個網(wǎng)絡(luò)。分簇算法在拓撲偵聽的基礎(chǔ)上完成分簇形成和分簇連接。

2 幾種典型移動自組網(wǎng)分簇算法

2.1 最小ID分簇算法

最小 ID分簇算法工作過程為：①網(wǎng)絡(luò)各節(jié)點分配惟一ID標識。②選擇具有最小ID的節(jié)點作簇頭。③其一跳鄰居節(jié)點成為該簇成員節(jié)點，并不再參與分簇。④剩余重復執(zhí)行②，③步驟，直到所有節(jié)點都屬于某個簇。該算法特點是計算簡單，算法收斂較快；在移動環(huán)境下，簇頭更新頻率較慢，簇維護開銷較小。但該算法傾向選擇ID較小的節(jié)點為簇頭，導致這些節(jié)點耗能較多，且沒有考慮負載平衡等因素。

2.2 最高節(jié)點度分簇算法

最高節(jié)點度分簇算法的目標是提高網(wǎng)絡(luò)控制能力和減少簇的數(shù)目。算法工作過程為最小 ID分簇算法步驟②改為選擇具有連接度最大的節(jié)點作為簇頭，節(jié)點度相同時選擇ID較小的節(jié)點為簇頭，其他步驟一樣。該算法特點是簇數(shù)目較少，減少了分組投遞時延與信道空間重用率。由于簇內(nèi)節(jié)點數(shù)不受限制，且信道由節(jié)點共享，當簇內(nèi)節(jié)點數(shù)量過多時，每個節(jié)點吞吐量急劇下降。此外，當節(jié)點移動性較強時，簇頭更新頻率較高，簇維護開銷較大。

2.3 最小移動性分簇算法

最小移動性分簇算法是節(jié)點權(quán)值分簇算法的一種，即按照一定規(guī)則給網(wǎng)絡(luò)中每個節(jié)點賦予權(quán)值，依據(jù)權(quán)值選取簇頭。算法工作過程為最小 ID分簇算法步驟②選擇相鄰節(jié)點中具有最大權(quán)值的節(jié)點被選作簇頭，權(quán)值相同時選擇 ID 較小的節(jié)點為簇頭。在移動性較強時，該算法可明顯減少簇頭更新頻率，缺點是節(jié)點權(quán)重更新較頻繁，簇頭計算開銷較大，且未考慮負載平衡和節(jié)點能量損耗問題。

2.4 NTDR

NTDR不僅是一種分簇算法，而且還是一種簇運行控制算法。算法工作過程如下：①一個節(jié)點如果發(fā)現(xiàn)它附近無簇頭節(jié)點，或探測到自己可修復一個網(wǎng)絡(luò)分割，則認為自己要成為簇頭。②為防止同時有多個節(jié)點做出反應(yīng)導致簇頭“競爭”，該節(jié)點等待一段隨機時間間隔后重測，當條件仍然為真時認定自己是簇頭。③每個新簇頭在認定自己為簇頭后，立即聲明簇頭地位。④沒有加入某個簇的節(jié)點根據(jù)一定原則選擇是否加入某個簇。⑤已經(jīng)是某個簇的成員節(jié)點一般保持簇從屬關(guān)系不變，但在下列情況發(fā)生時，也根據(jù)④尋找新的從屬關(guān)系，包括簇頭放棄簇頭地位、簇頭已經(jīng)不再列出這個節(jié)點、到簇頭的鏈路狀況已經(jīng)惡化到無法接受的程度以及從簇頭接收信號強度過低。⑥如果簇頭同意該節(jié)點加入，則向所有其它的簇頭發(fā)布更新后的簇內(nèi)成員列表，通告該節(jié)點已經(jīng)屬于自己這個簇。如果新加入的節(jié)點在加入該簇之前屬于另外一個簇，則簇頭還要通告該節(jié)點以前的簇頭。該算法優(yōu)點是分簇時間短，且為彌補原簇頭失效情況，當某一個簇頭失效時，會有一個新簇頭被迅速選舉出來。缺點是產(chǎn)生的簇頭數(shù)相對過多，系統(tǒng)穩(wěn)定性不強，原因是節(jié)點聲明為簇頭時沒有考慮節(jié)點各方面的綜合能力，導致加入該簇的成員相對較少，增加了簇頭的個數(shù)與通信開銷。

3 基于按需加權(quán)的NTDR(DWNTDR)

對于移動自組網(wǎng)入侵檢測來說，NTDR相對其他分簇算法具有更大的實用性。但NTDR產(chǎn)生的簇頭數(shù)相對過多，系統(tǒng)穩(wěn)定性不強。因此在此對其進行改進，提出一種基于按需加權(quán)的NTDR(DWNTDR, On-demand Weighting NTDR)。

此算法根據(jù)每個節(jié)點的權(quán)值來選擇簇頭，權(quán)值較小的節(jié)點優(yōu)先成為簇頭。在計算節(jié)點權(quán)值時，綜合考慮它的節(jié)點度、剩余能量和移動性。為增加簇結(jié)構(gòu)的穩(wěn)定性，減少簇頭的更新次數(shù)，還為原有簇頭引入了一定的增量以減小其權(quán)值，使其再次被選舉為簇頭的可能性增加。節(jié)點權(quán)值的計算公式為:

其中：①D(n)，節(jié)點n的節(jié)點度，M表示每個簇內(nèi)理想的簇成員數(shù)。②T(n)，節(jié)點n擔當簇頭的時間。③M(n)，節(jié)點n的平均移動速度。④P(n)，到所有鄰居節(jié)點距離之和。⑤x表示一個增量。如果在上一次選舉時，節(jié)點n被選為簇頭，則在本次選舉時，為其權(quán)值附加這個增量。若在上次選舉中節(jié)點n為簇成員，則權(quán)值的計算公式中不包含這個增量。⑥a，b，c，d表示加權(quán)系數(shù)，且滿足a+b+c+d=1。

其算法描述為：①網(wǎng)絡(luò)各節(jié)點分配惟一 ID標識，并分配相同的能量。②一個節(jié)點如果發(fā)現(xiàn)附近無簇頭節(jié)點，或探測到自己可以修復一個網(wǎng)絡(luò)分割，并且在鄰居節(jié)點中具有最小W，則認為自己要成為簇頭。如果W相同，則選擇ID最小的為簇頭。③每個新的簇頭在認定自己為簇頭后，立即聲明自己的簇頭地位。④其一跳鄰居節(jié)點中沒有加入某個簇的節(jié)點成為該簇成員節(jié)點，并不再參與分簇。⑤⑥與NTDR算法相同。⑦簇頭在自己剩余能量小于某個規(guī)定閾值時則放棄自己的簇頭地位。⑧剩余重復執(zhí)行②～⑦步驟，直到所有節(jié)點都屬于某個簇。當分簇完成后，如果簇頭失效，則立即在此簇中剩余能量大于某個規(guī)定閾值的節(jié)點中選舉具有最小W的節(jié)點為新簇頭，如果W相同，則選擇ID最小的為新簇頭。

4 算法模擬與分析

4.1 模擬假設(shè)前提和模擬環(huán)境

4.1.1 模擬假設(shè)前提

（1）網(wǎng)絡(luò)中所有節(jié)點是對等節(jié)點，各節(jié)點隨機部署在網(wǎng)絡(luò)中，且每個節(jié)點在網(wǎng)絡(luò)中具有惟一ID號。

（2）各節(jié)點通信能力相同，并能和通信范圍內(nèi)其它節(jié)點正常通信，不考慮背景噪聲和分組傳輸差錯等因素的影響。

（3）節(jié)點無線通信能力有限，即節(jié)點傳輸距離有限制。

（4）節(jié)點之間連接對稱。即連接的兩個節(jié)點 V1和 V2可以互相通信。為了更好地比較，各節(jié)點初始位置相同，并且五種算法均采用按需更新簇頭的簇維護策略。

4.1.2 模擬環(huán)境

模擬環(huán)境為在一個 100×100 單位距離的區(qū)域內(nèi)隨機放置N 個節(jié)點，節(jié)點移動方向在[0, 2∏]內(nèi)隨機分布，移動速度在[0,maxV]內(nèi)變化。當節(jié)點到達區(qū)域邊界時，它向區(qū)域內(nèi)反射。節(jié)點的數(shù)量、傳輸范圍(以單位距離數(shù)表示)和移動速度均可根據(jù)要求動態(tài)調(diào)整，模擬時間為10000個單位時間。

4.2 算法性能評價指標

（1）平均簇數(shù)。簇數(shù)是指整個網(wǎng)絡(luò)所包含的簇數(shù)目，決定了網(wǎng)絡(luò)中路徑的平均長度，對入侵檢測性能有直接影響，在仿真中對其求平均值得到平均簇數(shù)。

（2）單位時間內(nèi)簇頭更新次數(shù)。一次簇頭更新指某個節(jié)點由簇頭變?yōu)榇爻蓡T或由簇成員變?yōu)榇仡^。此指標用來說明重新運行分簇算法的頻率，該指標在很大程度上決定分簇算法性能。

（3）單位時間內(nèi)簇間轉(zhuǎn)移次數(shù)。簇間轉(zhuǎn)移次數(shù)是指簇成員在不同簇之間移動的次數(shù)。該指標用于說明在重新計算統(tǒng)治集的時間間隔內(nèi)簇維護開銷。

4.3 模擬結(jié)果比較和分析

通過算法模擬結(jié)果來對比分析五種算法性能，這五種算法分別是最小 ID 算法(LowID)、最高連接度算法(HighD)、最小移動性算法(LowM)，NTDR、基于按需加權(quán)的 NTDR(DWNTDR)。在此取網(wǎng)絡(luò)節(jié)點數(shù)N=30，maxV=5，節(jié)點傳輸范圍從5～60單位距離變化。對于DWNTDR，理想的簇成員M=8，a=0.2，b=0.3，c=0.3，d=0.2，x=1，并且節(jié)點剛開始的能量是1000能量單位，每單位時間簇頭消耗能量0.2%，簇成員為0.05%，能量閾值為100能量單位。

圖1給出不同分簇算法平均簇頭數(shù)隨節(jié)點傳輸范圍的變化情況。從圖1看出，簇頭數(shù)隨節(jié)點傳輸范圍增加而減少，當傳輸范圍大于30后，速度逐漸變慢。并且HighD算法得到的平均簇數(shù)明顯偏低，因為這種算法選擇節(jié)點度較高的節(jié)點成為簇頭，這樣單個簇內(nèi)所包含的節(jié)點數(shù)就較多，產(chǎn)生較少的簇，從而降低分組投遞延遲，簡化簇結(jié)構(gòu)的管理。但較少簇數(shù)也會降低信道的空間重用率，同時單個簇內(nèi)的節(jié)點數(shù)過多會使簇頭負擔加重。同時 DWNTDR，NTDR的平均簇頭數(shù)略多于LowM和LowID算法的平均簇頭數(shù)。并且DWNTDR的簇頭數(shù)較NTDR要少，主要是因為DWNTDR比NTDR多考慮了節(jié)點度，速度等因素，減少了冗余簇頭的產(chǎn)生。

圖1 平均簇頭數(shù)隨傳輸范圍的變化

圖2給出了不同分簇算法單位時間內(nèi)簇頭更新次數(shù)隨節(jié)點傳輸范圍的變化情況。從圖2數(shù)據(jù)顯示，當節(jié)點的傳輸范圍非常小時，簇數(shù)較多，簇成員與簇頭的距離很近，節(jié)點離開原簇的概率較小，因此單位時間內(nèi)簇頭更新次數(shù)較低。隨著傳輸范圍增加，單位時間內(nèi)簇頭更新次數(shù)逐漸增加，并在10左右達到峰值。隨著節(jié)點傳輸范圍的進一步增大反而使單位時間內(nèi)簇頭更新次數(shù)降低，這是因為盡管節(jié)點仍然保持移動狀態(tài)，但由于簇頭傳輸范圍較大，節(jié)點移出統(tǒng)治域的概率減小。從圖2還可以看出，由于節(jié)點移動使各節(jié)點的節(jié)點度不斷變化，造成HighD分簇算法單位時間內(nèi)的簇頭更新次數(shù)明顯大于其它幾種分簇算法，而DWNTDR分簇算法單位時間內(nèi)簇頭更新次數(shù)較其它算法都要小，并且 DWNTDR的簇頭更新次數(shù)明顯小于NTDR，這就降低了簇頭更新引入的系統(tǒng)開銷，說明此算法穩(wěn)定性要優(yōu)于其它幾種算法。

圖2 單位時間內(nèi)簇頭更新次數(shù)

圖3給出不同分簇算法單位時間內(nèi)簇間轉(zhuǎn)移次數(shù)隨節(jié)點傳輸范圍的變化情況。與圖2相同的原因，單位時間內(nèi)簇間轉(zhuǎn)移次數(shù)先上升達到峰值再單調(diào)下降。并在傳輸范圍為 25左右達到最大值。從圖3可以看出，各算法的性能差別較小。其中HighD分簇算法單位時間內(nèi)簇間轉(zhuǎn)移次數(shù)略高于其它算法。而DWNTDR單位時間內(nèi)的簇間轉(zhuǎn)移次數(shù)較其它算法要低，由此可以說明DWNTDR的簇結(jié)構(gòu)穩(wěn)定性遠大于另外幾種分簇算法。

圖3 單位時間內(nèi)簇間轉(zhuǎn)移次數(shù)

5 結(jié)論

本文通過對移動自組網(wǎng)絡(luò)拓撲結(jié)構(gòu)的分析，決定將簇結(jié)構(gòu)用于移動自組網(wǎng)入侵檢測系統(tǒng)中，并分析幾種現(xiàn)有分簇算法。針對現(xiàn)有移動自組網(wǎng)分簇算法的不足之處再在此基礎(chǔ)上對 NTDR進行改進，提出基于按需加權(quán)的 NTDR(DWNTDR)，并模擬各分簇算法。通過對各分簇算法的性能評價指標的分析和比較，剖析了這些算法的優(yōu)缺點。由于DWNTDR綜合考慮了影響移動自組網(wǎng)網(wǎng)絡(luò)性能的多種因素，采用按需簇維護策略，單位時間內(nèi)的簇頭更新次數(shù)和簇間轉(zhuǎn)移次數(shù)都明顯少于另外幾種分簇算法，而且能夠在原簇頭失效時迅速選出新簇頭，從而改善了系統(tǒng)的靈活性和通用性，提高了簇結(jié)構(gòu)的穩(wěn)定性，更加適應(yīng)于移動自組網(wǎng)的入侵檢測。

[1] 吳迪,李晴,馮永新,王光興.一種基于地理定位信息的 Ad Hoc分簇算法.計算機工程與應(yīng)用.2005.

[2] 王寒凝,王亞弟,費曉飛,韓繼紅.移動自組網(wǎng)中一種基于分簇的信任評估方案.計算機科學.2006.