王　超　李長庚

(中南大學(xué)物理與電子學(xué)院　湖南 長沙 410083)

?

一種基于相對移動(dòng)性的Ad-hoc網(wǎng)絡(luò)分簇算法

王超李長庚

(中南大學(xué)物理與電子學(xué)院湖南 長沙 410083)

針對Ad-hoc網(wǎng)絡(luò)中節(jié)點(diǎn)移動(dòng)而導(dǎo)致網(wǎng)絡(luò)分層結(jié)構(gòu)不穩(wěn)定的問題，提出一種基于節(jié)點(diǎn)間的相對移動(dòng)性的加權(quán)分簇算法RMCA(RelativeMobilityClusteringAlgorithm)。將局部節(jié)點(diǎn)的相關(guān)性運(yùn)用到簇頭的選舉當(dāng)中，并考慮距離因素的影響。運(yùn)用層次分析法計(jì)算出各因素的權(quán)重，通過NS2仿真工具對該算法進(jìn)行仿真，并與經(jīng)典算法進(jìn)行比較。結(jié)果顯示該算法在簇頭數(shù)目方面得到優(yōu)化，在簇依附關(guān)系變化和簇頭更新次數(shù)方面性能提升10%～15%左右，有效地提高了簇結(jié)構(gòu)的穩(wěn)定性。

Ad-hoc網(wǎng)絡(luò)分簇權(quán)值相對移動(dòng)性平均距離層次分析法

0　引　言

無線Ad-hoc網(wǎng)絡(luò)，又稱無線自組織網(wǎng)絡(luò)或者無線多跳網(wǎng)絡(luò)。該網(wǎng)絡(luò)由具有無線通信功能的節(jié)點(diǎn)組成，且不依賴于任何固定基礎(chǔ)設(shè)施。對網(wǎng)絡(luò)進(jìn)行分簇可以提高Ad-hoc網(wǎng)絡(luò)的可擴(kuò)展性。分簇算法對邏輯結(jié)構(gòu)要求較高，且要盡可能地降低維護(hù)開銷[1]。在分層結(jié)構(gòu)的網(wǎng)絡(luò)中，簇首承擔(dān)本簇內(nèi)成員之間的通信以及本簇成員節(jié)點(diǎn)和其他簇成員間通信的任務(wù)。因此，選擇合理節(jié)點(diǎn)擔(dān)任簇頭成為分簇算法的關(guān)鍵問題。目前已有幾種受到普遍認(rèn)可的分簇算法，如最小ID算法[2]、最高節(jié)點(diǎn)度算法[3]、加權(quán)分簇算法WCA(WeightedClusteringAlgorithm)[4]。最小ID算法較易實(shí)現(xiàn)，簇頭更換頻率慢，維護(hù)簇花費(fèi)的開銷較小。但I(xiàn)D較小的節(jié)點(diǎn)會因長期擔(dān)任簇頭而消耗更多的能量，進(jìn)而導(dǎo)致網(wǎng)絡(luò)出現(xiàn)分區(qū)的速度加快。最高節(jié)點(diǎn)度分簇算法中，簇的數(shù)目較少，降低了分組投遞時(shí)延，但較少的簇?cái)?shù)目也會導(dǎo)致信道的空間重用率降低。

WCA算法考慮多方面因素的影響，且為每個(gè)節(jié)點(diǎn)分配一個(gè)權(quán)值，以此評價(jià)節(jié)點(diǎn)充當(dāng)簇頭的能力[5]。該算法引入了電池能量、節(jié)點(diǎn)度、距離、節(jié)點(diǎn)速度四個(gè)因素作為計(jì)算權(quán)值的系統(tǒng)參數(shù)?？梢愿鶕?jù)不同的環(huán)境，對系統(tǒng)參數(shù)變量賦以不同權(quán)重，以適應(yīng)不同需求，算法的自適應(yīng)性較強(qiáng)[6,7]。但每個(gè)節(jié)點(diǎn)需要保存整個(gè)網(wǎng)絡(luò)系統(tǒng)的信息，每個(gè)循環(huán)周期僅能選舉出一個(gè)簇頭，延長了網(wǎng)絡(luò)初始化周期，增大了網(wǎng)絡(luò)通信開銷。在權(quán)值公式中，選取節(jié)點(diǎn)的平均速率和距離來評價(jià)節(jié)點(diǎn)的移動(dòng)性和位置，有其不足之處：(1) 節(jié)點(diǎn)速率小只能代表個(gè)體節(jié)點(diǎn)穩(wěn)定；(2) 與鄰居節(jié)點(diǎn)距離之和小，有可能是因?yàn)槠浯爻蓡T的數(shù)目較少，并不能真正確定簇頭與簇成員距離的遠(yuǎn)近。

本文提出一種基于相對移動(dòng)性的分簇算法RMCA，在克服已有算法不足的同時(shí)，集合了其他算法的優(yōu)點(diǎn)。最后在NS2下對RMCA算法進(jìn)行仿真分析，預(yù)計(jì)RMCA算法形成的簇結(jié)構(gòu)更穩(wěn)定，網(wǎng)絡(luò)開銷更少。

1　算法描述

算法選取節(jié)點(diǎn)度、節(jié)點(diǎn)平均距離、節(jié)點(diǎn)的相對移動(dòng)性以及節(jié)點(diǎn)剩余電量四個(gè)因素作為計(jì)算權(quán)值的系統(tǒng)參數(shù)，采用的權(quán)值公式為：

(1)

ω1+ω2+ω3+ω4=1

(2)

1.1權(quán)重的確定

本文算法利用權(quán)值公式通過計(jì)算選舉簇頭，優(yōu)勢在于可以根據(jù)不同的網(wǎng)絡(luò)要求，賦予相應(yīng)的權(quán)重以滿足不同的需求。因此，權(quán)重的確定尤為重要。層次分析法是美國運(yùn)籌學(xué)家Saaty教授提出的一種簡便、靈活而又方便使用的多準(zhǔn)則決策方法[8]。使用層次分析法解決問題時(shí)，分為四個(gè)步驟：

1) 建立目標(biāo)問題的遞進(jìn)關(guān)系結(jié)構(gòu)；

2) 構(gòu)造元素間的比較判斷矩陣；

3) 計(jì)算被比較元素的權(quán)重；

4) 計(jì)算各層次的組合權(quán)重。

在兩兩比較過程中，采用層次分析法中的1—9的比例標(biāo)度，見表1所示。

表1　標(biāo)度的意義

在Ad-hoc網(wǎng)絡(luò)中，由于節(jié)點(diǎn)的移動(dòng)性而導(dǎo)致網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不斷變化，進(jìn)而影響系統(tǒng)的性能，降低了網(wǎng)絡(luò)的可擴(kuò)展性，甚至?xí)鹁W(wǎng)絡(luò)癱瘓。此外由于本算法針對的是Ad-hoc網(wǎng)絡(luò)中由于節(jié)點(diǎn)移動(dòng)而導(dǎo)致網(wǎng)絡(luò)分層結(jié)構(gòu)不穩(wěn)定的問題，研究的重點(diǎn)是基于節(jié)點(diǎn)的移動(dòng)性。故而認(rèn)為移動(dòng)性因素相比較其他因素更為重要。

除移動(dòng)性外，電池能量、節(jié)點(diǎn)距離、節(jié)點(diǎn)度三個(gè)因素仍需考慮。在一些特定的場景中，節(jié)點(diǎn)能量有一定的保障，節(jié)點(diǎn)的距離與節(jié)點(diǎn)度的大小可通過動(dòng)態(tài)調(diào)節(jié)節(jié)點(diǎn)傳輸功率來降低對系統(tǒng)性能的影響。如現(xiàn)代軍事演習(xí)或?yàn)?zāi)難救援等，而節(jié)點(diǎn)移動(dòng)速度是根據(jù)現(xiàn)實(shí)情況的需求，任意改變的，故而節(jié)點(diǎn)的移動(dòng)性顯得尤為重要。同時(shí)，為了便于計(jì)算，因此假設(shè)三個(gè)因素同等重要。根據(jù)表1可得，移動(dòng)性因素重要于其他三個(gè)因素，標(biāo)度為a(a∈[2,9])；其他因素相對于移動(dòng)性因素標(biāo)度為1/a；相同元素之間比較或重要性相同的元素之間比較，因其重要性相同，標(biāo)度為1,結(jié)果如表2所示。

表2　兩兩判斷的對比情況

將所得矩陣進(jìn)行歸一化處理，得到矩陣的特征向量Wi：

(3)

(4)

再對矩陣進(jìn)行一致性檢驗(yàn)，公式為：

(5)

(6)

(7)

其中，CI為一致性指標(biāo)，λmax為矩陣的最大特征值,RI為隨機(jī)一致性指標(biāo),CR為一致性比率[9]。n為因素的個(gè)數(shù)，n=4。

隨機(jī)一致性指標(biāo)RI 數(shù)值表如表3 所列。如果一致性比率指標(biāo)：CR=CI/RI<0.1時(shí)，認(rèn)為其不一致程度在容許范圍之內(nèi)，一致性檢驗(yàn)通過[10]。

表3　隨機(jī)一致性指標(biāo)RI數(shù)據(jù)表

本文對不同的a值分別進(jìn)行實(shí)驗(yàn)仿真，現(xiàn)以中間值5為例進(jìn)行介紹。當(dāng)a=5時(shí),計(jì)算此時(shí)的一致性比率：

認(rèn)為一致性檢驗(yàn)通過。故而可得當(dāng)a=5時(shí)的判斷矩陣最終為：

通過計(jì)算得到權(quán)重為ω1=0.135，ω2=0.135，ω3=0.595，ω4=0.135。

1.2最佳節(jié)點(diǎn)度的計(jì)算

在Ad-hoc分層網(wǎng)絡(luò)中，簇的大小影響網(wǎng)絡(luò)運(yùn)行效率。簇頭節(jié)點(diǎn)覆蓋范圍應(yīng)該適中，覆蓋范圍過大，就會發(fā)生擁塞，過小則帶寬利用率降低；為了使吞吐率達(dá)到最佳，采用了Gerla等給出的一個(gè)結(jié)論[11]：網(wǎng)絡(luò)中的最佳節(jié)點(diǎn)度的大小為:

(8)

1.3平均相對移動(dòng)性的計(jì)算

在WCA算法中節(jié)點(diǎn)平均速率的確定依賴于節(jié)點(diǎn)的定位，現(xiàn)有的大多數(shù)文獻(xiàn)所采取的策略是對節(jié)點(diǎn)安裝GPS定位裝置，這加大了網(wǎng)絡(luò)成本，增大了通信消耗。使用節(jié)點(diǎn)相對其鄰居節(jié)點(diǎn)的相對移動(dòng)速率，提高了簇結(jié)構(gòu)的穩(wěn)定性，并且不需要明確節(jié)點(diǎn)每一時(shí)刻的具體位置，這大大減少了網(wǎng)絡(luò)能量消耗。

本方案利用節(jié)點(diǎn)連續(xù)兩次與其相鄰節(jié)點(diǎn)的交互信息，計(jì)算每一個(gè)節(jié)點(diǎn)的平均相對移動(dòng)性：

(9)

其中,Pr1、Pr2為鄰居節(jié)點(diǎn)連續(xù)兩次接收功率的大小，Pis1、Pis2為節(jié)點(diǎn)連續(xù)兩次發(fā)送功率大小。該移動(dòng)性的評價(jià)是節(jié)點(diǎn)與其他鄰居節(jié)點(diǎn)連續(xù)兩次交互信息之間移動(dòng)性的狀態(tài)，避免了節(jié)點(diǎn)因能耗等因素導(dǎo)致發(fā)送功率改變所帶來的影響，確定了評價(jià)移動(dòng)性的唯一標(biāo)準(zhǔn)，即Vi越小越好。此方案不依賴于GPS等定位儀對節(jié)點(diǎn)進(jìn)行定位，降低了網(wǎng)絡(luò)能耗，同時(shí)，局部范圍內(nèi)節(jié)點(diǎn)間的相關(guān)性較大。因此，網(wǎng)絡(luò)局部的穩(wěn)定性較強(qiáng)，所選的簇結(jié)構(gòu)較為穩(wěn)定。

1.4平均距離的計(jì)算

實(shí)驗(yàn)傳播模型采用雙反射模型，運(yùn)用文獻(xiàn)[12,13]中的跨層設(shè)計(jì)方案，利用發(fā)送信號強(qiáng)度與MAC層接收信號強(qiáng)度的關(guān)系[14]：

(10)

式中，Pt為節(jié)點(diǎn)的發(fā)送信號強(qiáng)度，si為發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的距離，G代表發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)的增益，ht和hr分別為發(fā)射天線和接收天線的高度，Pr為節(jié)點(diǎn)的MAC層接收信號的強(qiáng)度。由式(10)可得發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的距離為:

(11)

由此可計(jì)算出節(jié)點(diǎn)i到其所有鄰居節(jié)點(diǎn)的平均距離:

(12)

本方法考慮了鄰居節(jié)點(diǎn)的個(gè)數(shù)，避免了因節(jié)點(diǎn)度較小而得出距離較近的誤判。

1.5簇頭的選舉

當(dāng)網(wǎng)絡(luò)中有新節(jié)點(diǎn)加入或網(wǎng)絡(luò)開始成簇時(shí)，網(wǎng)絡(luò)通過初始化選舉簇頭。所有網(wǎng)絡(luò)中的節(jié)點(diǎn)通過發(fā)送“hello”消息以此來建立相互之間的鏈路，進(jìn)而計(jì)算權(quán)值。步驟如下：

第一步節(jié)點(diǎn)間通過周期性的發(fā)送交互“hello”信息報(bào)文獲知鄰居節(jié)點(diǎn)的信息，得到每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)，作為它的度數(shù)di,其中“hello”信息報(bào)文攜帶節(jié)點(diǎn)ID、節(jié)點(diǎn)度、權(quán)值、所屬簇、鄰居信息表等；

第二步計(jì)算得到節(jié)點(diǎn)度與最佳節(jié)點(diǎn)度差值Di；

第三步用Ei表示節(jié)點(diǎn)i剩余的電量；

第四步計(jì)算得到節(jié)點(diǎn)相對于其鄰居節(jié)點(diǎn)的相對移動(dòng)性Vi；

第六步每個(gè)節(jié)點(diǎn)i按照式(1)計(jì)算組合權(quán)重Wi，并將權(quán)值置于“hello”信息中廣播；

第七步所有相鄰的節(jié)點(diǎn)通過比較權(quán)值，擁有最小權(quán)值的節(jié)點(diǎn)作為簇頭，并廣播消息宣布自己的簇頭地位，在權(quán)值相等的情況下，ID較小的節(jié)點(diǎn)具有優(yōu)先成為簇頭的權(quán)利，未知節(jié)點(diǎn)接收到某簇頭的廣播消息即成為該簇頭的成員節(jié)點(diǎn)，修改自己的所屬簇列表，并廣播至網(wǎng)絡(luò)，且自身不再參與簇頭選舉；

第八步不斷重復(fù)前七步，直到所有節(jié)點(diǎn)都處于統(tǒng)治集范圍內(nèi)，初始化過程結(jié)束。

1.6簇的更新維護(hù)

在簇的初始化完成后，由于節(jié)點(diǎn)自身的移動(dòng)、耗能等內(nèi)在因素和外在環(huán)境的變化，可能導(dǎo)致節(jié)點(diǎn)間的鏈路發(fā)生改變，進(jìn)而使網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生改變，這需要對網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行實(shí)時(shí)更新維護(hù)：

1) 鏈路失效。如果該鏈路兩端為同一層次的節(jié)點(diǎn)，或一個(gè)節(jié)點(diǎn)是簇頭，另一個(gè)節(jié)點(diǎn)是其他簇的成員節(jié)點(diǎn)，則只需更新自己的成員信息表和鄰居信息表；如果鏈路兩端有簇依附關(guān)系，則簇頭更新自己的信息表，成員節(jié)點(diǎn)則找尋其他的簇，并成為新簇的成員節(jié)點(diǎn)；如果沒有發(fā)現(xiàn)其他簇頭，則自成一簇。

2) 新建鏈路。假設(shè)發(fā)生在節(jié)點(diǎn)i、j之間。

(1) 如果鏈路兩端都是成員節(jié)點(diǎn)，則只需更新自己的鄰居信息表。

(2) 如果i是簇頭，j是以節(jié)點(diǎn)k為簇頭的成員節(jié)點(diǎn)，則比較節(jié)點(diǎn)i和k的權(quán)值。如果weight(i)小于weight(k)，則節(jié)點(diǎn)j加入以i為簇頭的簇，節(jié)點(diǎn)i和節(jié)點(diǎn)k更新自己的鄰居信息表和成員信息表。如果weight(i)大于weight(k)，則節(jié)點(diǎn)i只是更新自己的鄰居信息表，其余狀態(tài)保持不變。

(3) 如果鏈路兩端都是簇頭，則只更新自己的鄰居信息表，其余狀態(tài)保持不變。

2　算法仿真與性能分析

NS2是面向?qū)ο蟮木W(wǎng)絡(luò)仿真工具，具有豐富的構(gòu)件庫，但NS2中沒有集成分族算法。因此需要用OTcl腳本語言擴(kuò)展NS2中的代理來實(shí)現(xiàn)仿真，對RMCA算法進(jìn)行模擬分析，并與其他經(jīng)典分簇算法進(jìn)行比較。

2.1仿真性能指標(biāo)

1) 平均簇頭數(shù)目。當(dāng)簇頭數(shù)目過大時(shí)，會增大端到端的延遲、增加通信開銷；當(dāng)簇頭數(shù)目過少時(shí)，會加大簇頭節(jié)點(diǎn)的工作強(qiáng)度，加快網(wǎng)絡(luò)出現(xiàn)分割的時(shí)間。

2) 單位時(shí)間內(nèi)，簇依附關(guān)系變化次數(shù)。簇結(jié)構(gòu)越穩(wěn)定，節(jié)點(diǎn)重新加入其他簇的次數(shù)就越少。

3) 單位時(shí)間內(nèi)，簇頭統(tǒng)治集更新次數(shù)。分簇算法在分簇過程中會有大量的計(jì)算與通信開銷，因此要盡可能降低簇頭更新的頻率[17]。本算法規(guī)定，當(dāng)有節(jié)點(diǎn)移出原簇，卻無法加入其他簇，則自成簇頭，并觸發(fā)統(tǒng)治集更新。此外，當(dāng)大量節(jié)點(diǎn)的簇依附關(guān)系發(fā)生變化，說明當(dāng)前網(wǎng)絡(luò)的簇結(jié)構(gòu)極不穩(wěn)定。因此，本算法規(guī)定單位時(shí)間內(nèi)簇依附關(guān)系變化次數(shù)超過10時(shí)，觸發(fā)統(tǒng)治集更新。

2.2仿真結(jié)果分析

仿真環(huán)境采用NS2軟件中的內(nèi)置工具setdest生成[18]，場景為100×100單位距離的區(qū)域；節(jié)點(diǎn)數(shù)N=100個(gè)；節(jié)點(diǎn)的移動(dòng)方式采用RandomWayp-oint模型，Waypoint方式的節(jié)點(diǎn)移動(dòng)速度為5～50m/s；節(jié)點(diǎn)傳輸范圍為5～50m；節(jié)點(diǎn)初始狀態(tài)能量設(shè)為50J；模擬時(shí)間為300s；監(jiān)測周期為5s。

實(shí)驗(yàn)考查節(jié)點(diǎn)傳輸范圍和節(jié)點(diǎn)移動(dòng)速度兩種因素對算法的影響，故模擬時(shí)采用兩種仿真場景，圖1-圖3采用場景一：節(jié)點(diǎn)移動(dòng)速率為10m/s，節(jié)點(diǎn)傳輸范圍由5m均勻變化到50m。圖4-圖5采用場景二：節(jié)點(diǎn)傳輸范圍為20m，節(jié)點(diǎn)的移動(dòng)速率由5m/s均勻變化到50m/s。實(shí)驗(yàn)中每組數(shù)據(jù)通過50次仿真結(jié)果平均得到。

在實(shí)驗(yàn)中，隨著節(jié)點(diǎn)傳輸距離的增加，簇頭數(shù)目逐漸減少，當(dāng)傳輸距離達(dá)到20m后，簇頭數(shù)目減少的趨勢逐漸變緩，最終減少到1個(gè)。如圖1所示。由于WCA算法和RMCA算法對節(jié)點(diǎn)度的限制，簇頭數(shù)目適中，且接近符合最佳節(jié)點(diǎn)度數(shù)的要求。

圖1　簇頭數(shù)目隨節(jié)點(diǎn)傳輸距離的變化

節(jié)點(diǎn)重入簇次數(shù)隨著節(jié)點(diǎn)的傳輸距離增大而變化的情況如圖2所示。四種分簇算法都呈拋物線狀，因?yàn)楫?dāng)傳輸距離較小時(shí)，網(wǎng)絡(luò)形成的簇結(jié)構(gòu)較多，成員節(jié)點(diǎn)很少，節(jié)點(diǎn)脫離原簇的概率小。節(jié)點(diǎn)脫離原簇的概率隨著距離的增大也逐漸增加，峰值出現(xiàn)在傳輸距離為25m左右。隨后，由于簇的統(tǒng)治范圍增大，節(jié)點(diǎn)脫離原簇的概率再次減小。RMCA算法較其他三種算法而言，重入簇次數(shù)明顯減小， 簇的穩(wěn)定性增強(qiáng)。

圖2　節(jié)點(diǎn)重入簇次數(shù)隨節(jié)點(diǎn)傳輸距離的變化

節(jié)點(diǎn)傳輸距離對統(tǒng)治集更新的影響如圖3所示。四種算法的結(jié)果呈拋物線狀，峰值出現(xiàn)在10m左右。本方案中，節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的距離考慮節(jié)點(diǎn)度的影響，計(jì)算平均距離，使簇頭到簇成員的距離更為準(zhǔn)確，因此在同等條件下，本算法的統(tǒng)治集更新次數(shù)較少。

圖3　統(tǒng)治集更新次數(shù)隨節(jié)點(diǎn)傳輸距離的變化

重入簇次數(shù)隨節(jié)點(diǎn)速度的變化情況如圖4所示，RMCA算法明顯較優(yōu)。這是由于當(dāng)節(jié)點(diǎn)速度較快時(shí)，節(jié)點(diǎn)更容易發(fā)生簇間移動(dòng)，本方案采用節(jié)點(diǎn)間的相對移動(dòng)性，減弱了節(jié)點(diǎn)移動(dòng)速度對簇結(jié)構(gòu)的影響，能更好地維護(hù)簇的拓?fù)浣Y(jié)構(gòu)。

圖4　重入簇次數(shù)隨節(jié)點(diǎn)移動(dòng)速度的變化

圖5反映了統(tǒng)治集更新次數(shù)隨節(jié)點(diǎn)移動(dòng)速度的變化情況，隨著移動(dòng)速度的增大，四種算法的統(tǒng)治集更新次數(shù)都有增大的趨勢。相比較而言，RMCA與WCA算法考慮到了節(jié)點(diǎn)的移動(dòng)性的影響，因此要優(yōu)于其他算法。RMCA算法利用節(jié)點(diǎn)間的相對移動(dòng)性，節(jié)點(diǎn)之間的相關(guān)性較大，考慮到了節(jié)點(diǎn)周圍拓?fù)浣Y(jié)構(gòu)的變化，因此本算法所形成的簇結(jié)構(gòu)和網(wǎng)絡(luò)的統(tǒng)治域更為穩(wěn)定。

圖5　統(tǒng)治集更新次數(shù)隨節(jié)點(diǎn)移動(dòng)速度的變化

2.3不同的權(quán)重對于網(wǎng)絡(luò)性能的影響

本文的仿真是在以移動(dòng)性的標(biāo)度為5為例的基礎(chǔ)上進(jìn)行的，不同的標(biāo)度值得出的權(quán)重各有不同。現(xiàn)對其他標(biāo)度值進(jìn)行仿真對比。仿真環(huán)境中的參數(shù)設(shè)定為：節(jié)點(diǎn)移動(dòng)速率為10m/s,節(jié)點(diǎn)的傳輸范圍為20m。其他保持不變。仿真結(jié)果如表4所示。

表4　不同標(biāo)度值對網(wǎng)絡(luò)系統(tǒng)性能的影響

由表4和前文中的仿真圖可知，在本算法中，a取不同的值時(shí)，系統(tǒng)性能較其他算法總體有所提升，且當(dāng)a=5時(shí)，網(wǎng)絡(luò)性能最優(yōu)。

從表4中可以看出，平均簇頭數(shù)隨a值的增大呈遞減的趨勢。因?yàn)楫?dāng)a較小時(shí)，節(jié)點(diǎn)度的影響相對較大，對簇頭數(shù)目有一定的約束，隨著a值的增大，節(jié)點(diǎn)度的影響相對減弱，簇頭數(shù)目隨之減少，偏離最佳節(jié)點(diǎn)度的幅度隨之增大。

平均簇依附關(guān)系和平均統(tǒng)治集更新次數(shù)隨a值的增大，呈拋物線狀。當(dāng)a較小時(shí)，節(jié)點(diǎn)移動(dòng)性的重要程度較低，節(jié)點(diǎn)移動(dòng)性對簇頭的選擇貢獻(xiàn)值較小，導(dǎo)致所確定的簇結(jié)構(gòu)穩(wěn)定性較差，故而簇依附關(guān)系變化次數(shù)和統(tǒng)治集更新次數(shù)相應(yīng)較大；當(dāng)a較大時(shí)，移動(dòng)性對于簇頭選擇的貢獻(xiàn)較大，得到的簇結(jié)構(gòu)只是物理上的相對穩(wěn)定，但因?yàn)楣?jié)點(diǎn)能量、節(jié)點(diǎn)度以及距離因素對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的形成貢獻(xiàn)較少，導(dǎo)致部分節(jié)點(diǎn)因能量損耗，節(jié)點(diǎn)分布不均勻、節(jié)點(diǎn)死亡等因素的影響而引起網(wǎng)絡(luò)結(jié)構(gòu)的不穩(wěn)定。最終導(dǎo)致節(jié)點(diǎn)平均簇依附關(guān)系變化次數(shù)和平均統(tǒng)治集更新次數(shù)逐漸升高。

3　結(jié)　語

RMCA算法考慮四個(gè)因素，具有更好的適應(yīng)性，與僅考慮單因素的算法相比，雖然復(fù)雜度稍高，但可通過極少的計(jì)算開銷而獲得較好的系統(tǒng)性能。并且運(yùn)用層次分析法得到的權(quán)重更加符合主觀和客觀的要求。與WCA算法比較，RMCA算法采用相對移動(dòng)性，更好地考慮了節(jié)點(diǎn)局部拓?fù)浣Y(jié)構(gòu)的變化。另外，采用平均距離，考慮節(jié)點(diǎn)的節(jié)點(diǎn)度對距離因素的影響，故而在簇結(jié)構(gòu)穩(wěn)定性、能量利用率等方面實(shí)現(xiàn)了合理優(yōu)化。通過仿真工具NS2，將RMCA算法和WCA等三種算法進(jìn)行了分析比較，驗(yàn)證了RMCA算法形成的簇結(jié)構(gòu)具有更強(qiáng)的穩(wěn)定性，節(jié)點(diǎn)重新入簇次數(shù)和統(tǒng)治集更新次數(shù)等方面性能提高了10%～15%左右。

[1]AkbariTorkestaniJ,MeybodiMR.Amobilitybasedclusterformationalgorithmforwirelessmobilead-hocnetworks[J].Clustercomputing,2011,14(4):311-324.

[2]LinCR,GerlaM.Adaptiveclusteringformobilewirelessnet-works[J].IEEEJournalonSelectedAreasinCommunication,1997,15(7):1268-1275.

[3]GerlaM,TsaiTC.Multicluster,Mobile,Multime-Dia,RadioNetwork[C]//JournalofWirelessNetworks.1995:255-265.

[4]ChatterjeeM,DasS,TurgutD.WCA:AWeightedClusteringAlgorithm(WCA)formobileadhocnetworks[J].ClusterComputing,2002,5(7):193-204.

[5]DhurandherSK，SinghGV.WeightBasedAdaptiveClusteringinWirelessAdHocNetworks[C]//Proceedingsofthe2005IEEEInternationalConferenceonPersonalWirelessCommunications,NewDelhi,India,2005:95-100.

[6] 李瑾,潘宏,劉中兵，等.MANET中基于連通支配集的組合權(quán)值簇生成算法[J].計(jì)算機(jī)應(yīng)用,2012,32(7):1840-1843,1855.

[7] 杜國勇,束永安.基于鏈接率的AdHoc自適應(yīng)按需加權(quán)分簇算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014,24(1):93-97.

[8] 孫璐.層次分析法中用于確定權(quán)重的最小-最大優(yōu)化方法[J].東南大學(xué)學(xué)報(bào):英文版,2012,28(2):245-250.

[9]SainiVK，KumarV.AHP,fuzzysetsandTOPSISbasedreliablerouteselectionforMANET[C]//ComputingforSustainableGlobalDevelopment(INDIACom),2014InternationalConferenceon.NewDelhi,India,2014:24-29.

[10] 許樹柏．層次分析法原理[M]．天津：天津大學(xué)出版社，1988.

[11]XuKaixin,HongXiaoyan,MarioGerla，etal.Anadhocnetworkwithmobilebackbones[J].IEEE,ICC,2002,16(4):11-21.

[12] 鄭騰飛,朱琦.認(rèn)知AdHoc網(wǎng)絡(luò)中的跨層路由協(xié)議[J].計(jì)算機(jī)應(yīng)用,2011,31(S2):9-13.

[13] 張永敏,徐偉強(qiáng),黃炯，等.AdHoc網(wǎng)絡(luò)節(jié)能型功率控制與擁塞控制的跨層優(yōu)化[J].軟件學(xué)報(bào),2013,24(4):900-914.

[14] 王慶文,史浩山,戚茜，等.一種新的AdHoc網(wǎng)絡(luò)跨層能量均衡廣播協(xié)議[J].西北工業(yè)大學(xué)學(xué)報(bào),2011,29(5):671-675.

[15] 柯志亨,程榮祥,鄧德雋.NS2 仿真實(shí)驗(yàn)-多媒體和無線網(wǎng)絡(luò)通信[M]. 北京:電子工業(yè)出版社,2009.

[16]QiBing,ShenFangyang.Propagationmodelsformulti-hopwirelessnetworksinNs-2Simulator[C]// 8thInternationalConference2011,Infor-mation,Technology:NewGenerations.lasVegas,Nevadam,USA,2011:701-706.

[17]YuJiguo,WangGuanghui.Constructingminimumextendedweakly-connecteddominatingsetsforclusteringinadhocnetworks[J].JournalofParallelandDistributedComputing,2012,72(1):35-47.

[18] 黃化吉，馮穗力,秦麗姣，等.NS網(wǎng)絡(luò)模擬和協(xié)議仿真[M].北京：人民郵電出版社，2010.

ANAD-HOCNETWORKCLUSTERINGALGORITHMBASEDONRELATIVEMOBILITY

WangChaoLiChanggeng

(School of Physics and Electronics,Central South University,Changsha 410083， Hunan, China)

Aimingattheinstabilityproblemofnetworkhierarchystructurecausedbythemovementofnodesinad-hocnetwork,thispaperproposesaweightedclusteringalgorithmwhichisbasedonrelativemobilitybetweennodes.Thealgorithmappliesthecorrelationmobilitybetweenlocalnodestoclusterselection,andconsiderstheeffectofdistancefactoraswell.Throughtheanalytichierarchyprocess(AHP)itcalculatestheweightofeachfactor.ThealgorithmissimulatedusingNS2simulationtoolandcomparedwiththeclassicalalgorithms.Resultsshowthatthisalgorithmisoptimisedinnumbersoftheclusterhead,theperformanceincreasesofabout10%～15%innumberoftheclusterattachmentchangesandthenumberofclusterheadupdate.Itimprovesthestabilityoftheclusterstructureeffectively.

Ad-hocnetworkClusteringWeightsRelativemobilityAveragedistanceAHP

2014-08-23。王超，碩士生，主研領(lǐng)域：無線自組織網(wǎng)絡(luò)，無線傳感器網(wǎng)絡(luò)拓?fù)淇刂?，路由協(xié)議。李長庚， 教授。

TP393.0

ADOI:10.3969/j.issn.1000-386x.2016.03.034