移動(dòng)自組網(wǎng)中基于按需加權(quán)的NTDR分簇算法

胡波

1 福建省財(cái)稅信息中心 福建 350003

2 中南大學(xué)信息科學(xué)與工程學(xué)院 湖南 410083

0 引言

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

1 分簇定義及分簇算法目標(biāo)

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

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

2.1 最小ID分簇算法

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

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

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

2.3 最小移動(dòng)性分簇算法

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

2.4 NTDR

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

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

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

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

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

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

4 算法模擬與分析

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

4.1.1 模擬假設(shè)前提

（1）網(wǎng)絡(luò)中所有節(jié)點(diǎn)是對(duì)等節(jié)點(diǎn)，各節(jié)點(diǎn)隨機(jī)部署在網(wǎng)絡(luò)中，且每個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中具有惟一ID號(hào)。

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

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

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

4.1.2 模擬環(huán)境

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

4.2 算法性能評(píng)價(jià)指標(biāo)

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

[2] 王寒凝,王亞弟,費(fèi)曉飛,韓繼紅.移動(dòng)自組網(wǎng)中一種基于分簇的信任評(píng)估方案.計(jì)算機(jī)科學(xué).2006.