一種移動(dòng)自組網(wǎng)的分簇算法
相關(guān)鏈接： 廣東安全網(wǎng) 廣東質(zhì)量網(wǎng) 廣東論文網(wǎng) 廣東資訊網(wǎng)
摘要本文分析了移動(dòng)自組網(wǎng)的現(xiàn)有分簇算法，并針對(duì)現(xiàn)有分簇算法的不足對(duì)NTDR進(jìn)行了改進(jìn)，提出了基于按需加權(quán)的NTDR（DWNTDR）。
論文關(guān)鍵詞：移動(dòng)自組網(wǎng),分簇,分簇算法
在移動(dòng)自組網(wǎng)環(huán)境中，分簇的入侵檢測(cè)系統(tǒng)能有效控制移動(dòng)節(jié)點(diǎn)間的入侵檢測(cè)通信開銷，節(jié)約網(wǎng)絡(luò)資源和節(jié)點(diǎn)能量，實(shí)現(xiàn)高效協(xié)作式檢測(cè)機(jī)制。因此，移動(dòng)自組網(wǎng)IDS采用分簇結(jié)構(gòu)能否高效，IDS分簇算法起著非常重要的作用。
2 幾種典型移動(dòng)自組網(wǎng)分簇算法
移動(dòng)自組網(wǎng)的分簇算法目標(biāo)就是以較少的計(jì)算和通信開銷來構(gòu)造與維護(hù)一個(gè)簇集合，使其能在覆蓋整個(gè)網(wǎng)絡(luò)的同時(shí)較好地支持資源管理和路由協(xié)議的相互連接，并在網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化時(shí)生成新的簇結(jié)構(gòu)，確保網(wǎng)絡(luò)正常通信。在此將對(duì)幾種典型分簇算法進(jìn)行闡述。
1. 最小ID分簇算法
最小ID分簇算法，它由Grela和Tsai在鏈路分簇算法（LCA）基礎(chǔ)上改進(jìn)而得。該
算法特點(diǎn)是計(jì)算簡(jiǎn)單, 實(shí)現(xiàn)方便，算法收斂較快。但是該算法節(jié)點(diǎn)消耗的能量多,而且加快了網(wǎng)絡(luò)出現(xiàn)分割的時(shí)間, 同時(shí)沒有考慮負(fù)載平衡等因素。
2. 最高節(jié)點(diǎn)度分簇算法
該算法特點(diǎn)是簇?cái)?shù)目較少，減少了分組投遞時(shí)延, 但同時(shí)也減少了信道空間重用率。由于簇內(nèi)節(jié)點(diǎn)數(shù)不受限制, 并且信道由節(jié)點(diǎn)共享, 當(dāng)簇內(nèi)節(jié)點(diǎn)數(shù)量過多時(shí), 每個(gè)節(jié)點(diǎn)的吞吐量急劇下降。此外, 當(dāng)節(jié)點(diǎn)移動(dòng)性較強(qiáng)時(shí), 簇頭更新頻率較高，簇維護(hù)開銷較大。因此，該算法適合于移動(dòng)性較弱且節(jié)點(diǎn)密度較低的場(chǎng)合。
3. 最小移動(dòng)性分簇算法
最小移動(dòng)性分簇算法是節(jié)點(diǎn)權(quán)值分簇算法的一種，在移動(dòng)性較強(qiáng)時(shí), 該算法可以明顯減
----------
作者簡(jiǎn)介：周忠華（1978 -），廣東商學(xué)院實(shí)驗(yàn)師，碩士研究生，主要研究方向：計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)
少簇頭更新頻率。它的缺點(diǎn)是節(jié)點(diǎn)權(quán)重的更新較頻繁, 簇頭計(jì)算開銷較大, 并且未考慮負(fù)載平衡和節(jié)點(diǎn)能量損耗問題。
4．NTDR
該算法優(yōu)點(diǎn)是分簇時(shí)間短，而且為了彌補(bǔ)當(dāng)原簇頭失效的情況，當(dāng)某一個(gè)簇頭失效時(shí)，會(huì)有一個(gè)新簇頭被迅速選舉出來。缺點(diǎn)是產(chǎn)生的簇頭數(shù)相對(duì)過多，系統(tǒng)穩(wěn)定性不強(qiáng)，原因是節(jié)點(diǎn)聲明為簇頭時(shí)沒有考慮節(jié)點(diǎn)的各方面的綜合能力，導(dǎo)致加入該簇的成員相對(duì)較少，增加了簇頭的個(gè)數(shù)，同時(shí)也增加通信開銷。
3 基于按需加權(quán)的NTDR（DWNTDR）
前三種分簇算法都只是單純的分簇算法，沒有考慮移動(dòng)自組網(wǎng)入侵檢測(cè)和軍事方面的需要。而NTDR專門應(yīng)用于軍事方面，對(duì)于移動(dòng)自組網(wǎng)入侵檢測(cè)來說具有更大的實(shí)用性。但NTDR產(chǎn)生的簇頭數(shù)相對(duì)過多，系統(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)值來選擇簇頭，權(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ì)算公式為:
W（n）=a·|D（n）-M|+b·T（n）+c·M（n）+d·P（n）-x
其中: 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è)增量；a，b，c,d表示加權(quán)系數(shù)，且滿足a+b+c+d=1。
其算法描述為：
（1）網(wǎng)絡(luò)各節(jié)點(diǎn)分配唯一ID標(biāo)識(shí)，并分配相同的能量。
�。�2）一個(gè)DWNTDR節(jié)點(diǎn)如果發(fā)現(xiàn)它的附近沒有一個(gè)簇頭節(jié)點(diǎn)，或者是它探測(cè)到自己可以修復(fù)一個(gè)網(wǎng)絡(luò)分割，并且在鄰居節(jié)點(diǎn)中具有最小W，則認(rèn)為自己要成為簇頭。如果W相同，則選擇ID最小的為簇頭。
�。�3）每個(gè)新的簇頭在認(rèn)定自己為簇頭后，則立即聲明自己的簇頭地位。
�。�4）其一跳鄰居節(jié)點(diǎn)中沒有加入某個(gè)簇的節(jié)點(diǎn)成為該簇成員節(jié)點(diǎn)，并不再參與分簇。
�。�5）已經(jīng)是某個(gè)簇的成員節(jié)點(diǎn)一般保持簇從屬關(guān)系不變，但在下列情況發(fā)生時(shí)，也可以加入此簇頭，并不再參與分簇，包括：簇頭放棄自己的簇頭地位、簇頭已經(jīng)不再列出這個(gè)節(jié)點(diǎn)、到簇頭的鏈路狀況已經(jīng)惡化到無法接受的程度以及從簇頭接收的信號(hào)強(qiáng)度過低。
�。�6）如果簇頭同意該節(jié)點(diǎn)加入，則向所有其它的簇頭發(fā)布立即更新后的簇內(nèi)成員列表，通告其它所有簇頭該節(jié)點(diǎn)已經(jīng)屬于自己這個(gè)簇，明確這個(gè)節(jié)點(diǎn)的當(dāng)前位置。如果新加入的節(jié)點(diǎn)在加入該簇之前屬于另外一個(gè)簇，則簇頭還要通告該節(jié)點(diǎn)以前的簇頭，指示該節(jié)點(diǎn)已經(jīng)有了新的簇從屬關(guān)系。
�。�7）簇頭在自己的剩余能量小于某個(gè)規(guī)定的閾值時(shí)則放棄自己的簇頭地 位，不再為簇頭。
（8）剩余重復(fù)執(zhí)行（2）～（7）步驟，直到所有節(jié)點(diǎn)都屬于某個(gè)簇。
為了減小簇維護(hù)所引入的系統(tǒng)開銷，采取按需策略，規(guī)定只有當(dāng)網(wǎng)絡(luò)中的某個(gè)節(jié)點(diǎn)與現(xiàn)有的任何簇頭都不是相鄰節(jié)點(diǎn)時(shí)，才重新選舉簇頭。
4 算法模擬與分析
為了便于實(shí)現(xiàn)，本文用Java語言編制的簡(jiǎn)單模擬環(huán)境來對(duì)上述五種分簇算法進(jì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í)間。主要通過不同移動(dòng)環(huán)境下的算法模擬結(jié)果來對(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ì)于基于按需加權(quán)的NTDR，理想的簇成員M=8，a=0.2，b=0.3，c=0.3，d=0.2，x=1，并且節(jié)點(diǎn)剛開始的能量是1000能量單位，每單位時(shí)間簇頭消耗能量0.2%，簇成員為0.05%，能量閾值為100能量單位。
圖1平均簇頭數(shù)隨傳輸范圍的變化
圖1給出了不同分簇算法平均簇頭數(shù)隨節(jié)點(diǎn)傳輸范圍的變化情況。從圖1可以看出，簇頭數(shù)隨節(jié)點(diǎn)傳輸范圍的增加而減少, 當(dāng)傳輸范圍大于30后, 速度逐漸變慢。DWNTDR，NTDR的平均簇頭數(shù)略多于最小移動(dòng)性和最小ID分簇算法的平均簇頭數(shù)。并且DWNTDR的簇頭數(shù)較NTDR要少, 主要是因?yàn)镈WNTDR比NTDR多考慮了節(jié)點(diǎn)度，速度等因素，減少了冗余簇頭的產(chǎn)生。
圖2給出不同分簇算法單位時(shí)間內(nèi)簇間轉(zhuǎn)移次數(shù)隨節(jié)點(diǎn)傳輸范圍的變化情況。從圖2可以看出，最高節(jié)點(diǎn)度分簇算法的單位時(shí)間內(nèi)的簇間轉(zhuǎn)移次數(shù)略高于其它分簇算法。而
DWNTDR單位時(shí)間內(nèi)的簇間轉(zhuǎn)移次數(shù)較其它算法要低，由此可以說明DWNTDR的簇結(jié)構(gòu)穩(wěn)定性遠(yuǎn)大于另外幾種分簇算法。
圖2 單位時(shí)間內(nèi)簇間轉(zhuǎn)移次數(shù)
綜上所述，通過對(duì)不同算法的模擬與分析，可以看出DWNTDR分簇算法在穩(wěn)定性，對(duì)網(wǎng)絡(luò)拓?fù)渥兓倪m應(yīng)力等方面要明顯優(yōu)于其它幾種算法，而且DWNTDR還保留了NTDR算法在原簇頭失效時(shí)迅速選出新簇頭的優(yōu)點(diǎn)，從而改善了系統(tǒng)的靈活性和通用性，提高了簇結(jié)構(gòu)的穩(wěn)定性，更加適應(yīng)移動(dòng)自組網(wǎng)入侵檢測(cè)。
5 結(jié)束語
本文針對(duì)現(xiàn)有移動(dòng)自組網(wǎng)分簇算法的不足之處在此基礎(chǔ)上對(duì)NTDR進(jìn)行了改進(jìn)，提出基于按需加權(quán)的NTDR（DWNTDR），該算法綜合考慮了影響移動(dòng)自組網(wǎng)性能的節(jié)點(diǎn)度，速度等多種因素，改善了系統(tǒng)的靈活性和通用性，提高了簇結(jié)構(gòu)的穩(wěn)定性，更適合移動(dòng)自組網(wǎng)入侵檢測(cè)系統(tǒng)。
參考文獻(xiàn)
[1] 王寒凝，王亞弟，費(fèi)曉飛、韓繼紅. 移動(dòng)自組網(wǎng)中一種基于分簇的信任評(píng)估方案. 計(jì)算機(jī)科學(xué)，2006，33（8）：98~105
