基于層次分析法的多度量MPR選取

雷 琪 琦

(哈爾濱工程大學(xué) 信息與通信工程學(xué)院，哈爾濱 150001)

無(wú)人機(jī)自組網(wǎng)(FANET)是移動(dòng)自組織網(wǎng)絡(luò)(MANET)在無(wú)人機(jī)領(lǐng)域的應(yīng)用[1].它們共享一些特性比如無(wú)中心、自組織和節(jié)點(diǎn)可以在沒(méi)有任何基礎(chǔ)設(shè)施的情況下進(jìn)行通信等，同時(shí)無(wú)人機(jī)自組網(wǎng)也具有自身特有的屬性[2].無(wú)人機(jī)節(jié)點(diǎn)移動(dòng)性較高，因此節(jié)點(diǎn)間通信鏈路波動(dòng)劇烈.相比于在二維空間中的移動(dòng)節(jié)點(diǎn)，三維空間中無(wú)人機(jī)節(jié)點(diǎn)位置的改變更容易造成節(jié)點(diǎn)間鏈路的建立與斷開(kāi)，頻繁的拓?fù)渥兓璧K了數(shù)據(jù)的正常傳輸并使網(wǎng)絡(luò)的傳輸時(shí)延增大[3].因此，F(xiàn)ANET中路由協(xié)議的研究顯得尤為重要.優(yōu)化鏈路狀態(tài)(OLSR)協(xié)議是MANET中典型的表驅(qū)動(dòng)路由協(xié)議，它不僅能夠快速建立路由而且可以利用MPR機(jī)制有效地限制控制消息的洪泛范圍以減小網(wǎng)絡(luò)的路由開(kāi)銷(xiāo)[4].但是，由于FANET中節(jié)點(diǎn)移動(dòng)性高、節(jié)點(diǎn)間鏈路連接不穩(wěn)定且節(jié)點(diǎn)能量有限等特性，移動(dòng)自組網(wǎng)中傳統(tǒng)的路由協(xié)議已經(jīng)無(wú)法適用于無(wú)人機(jī)自組網(wǎng)[5].因此，如何對(duì)傳統(tǒng)OLSR協(xié)議進(jìn)行改進(jìn)并使其適用于FANET中成為了一個(gè)重要的問(wèn)題[6].

為了對(duì)OLSR協(xié)議進(jìn)行優(yōu)化，作為其核心思想的MPR選取算法為了研究的熱點(diǎn)之一[7].文獻(xiàn)[8]提出了一種考慮節(jié)點(diǎn)移動(dòng)性的MPR選取算法，該算法盡可能地選取移動(dòng)性較小的節(jié)點(diǎn)作為MPR以此來(lái)提高網(wǎng)絡(luò)的分組投遞率.文獻(xiàn)[9]提出在MPR選取時(shí)綜合考慮節(jié)點(diǎn)連接度、鏈路層擁塞度以及節(jié)點(diǎn)剩余能量.實(shí)驗(yàn)表明，改進(jìn)后的協(xié)議具有更高的分組投遞率.文獻(xiàn)[10]提出了一種基于位置和鄰居感知的OLSR協(xié)議，該協(xié)議將節(jié)點(diǎn)位置記錄于HELLO消息中并在MPR節(jié)點(diǎn)選取時(shí)將鏈路穩(wěn)定性作為選取標(biāo)準(zhǔn).仿真結(jié)果表明，該協(xié)議降低了傳輸時(shí)延并使網(wǎng)絡(luò)更加穩(wěn)定.文獻(xiàn)[11]提出了一種新的MPR選取算法，該算法在源節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)的可達(dá)性和剩余能量之間引入動(dòng)態(tài)權(quán)重比，避免了長(zhǎng)期被選為MPR的節(jié)點(diǎn)能量的快速減少，提高了網(wǎng)絡(luò)的生存時(shí)間.文獻(xiàn)[12]在MPR選取算法中引入節(jié)點(diǎn)密度和剩余能量，將能量低于閾值的節(jié)點(diǎn)排除然后再進(jìn)行MPR的選取，該算法降低了網(wǎng)絡(luò)的路由開(kāi)銷(xiāo).

為了使傳統(tǒng)OLSR協(xié)議在FANET中表現(xiàn)出更好的網(wǎng)絡(luò)性能，本文考慮到節(jié)點(diǎn)間鏈路生存時(shí)間、節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)深度均可以影響MPR的選取，便提出了基于層次分析法的多度量MPR選取算法.該算法綜合考慮3種影響因素并利用層次分析法精確地計(jì)算各影響因素的權(quán)重因子，接著將它們的加權(quán)和作為綜合度量來(lái)選取合適的MPR節(jié)點(diǎn).改進(jìn)后LEC-OLSR協(xié)議不僅能夠選取出更合理的MPR節(jié)點(diǎn)，而且使網(wǎng)絡(luò)的分組投遞率和平均端到端時(shí)延得到提升.

1 相關(guān)理論

1.1 傳統(tǒng)MPR選取算法

對(duì)于一個(gè)要選取MPR節(jié)點(diǎn)的中心節(jié)點(diǎn)，它的MPR集定義為M，它的一跳鄰居節(jié)點(diǎn)集定義為N1，它的兩跳鄰居節(jié)點(diǎn)集定義為N2.D(y)表示N1中某個(gè)節(jié)點(diǎn)的深度，指與該節(jié)點(diǎn)間鏈路狀態(tài)為對(duì)稱(chēng)的鄰居節(jié)點(diǎn)的個(gè)數(shù)；Reachability表示N1中某個(gè)節(jié)點(diǎn)的可達(dá)性，表示N1中某節(jié)點(diǎn)可到達(dá)的對(duì)稱(chēng)鄰居節(jié)點(diǎn)的個(gè)數(shù).與深度D(y)不同的是，它在不包括中心節(jié)點(diǎn)和N1中的任何一個(gè)節(jié)點(diǎn)的基礎(chǔ)上還排除了被MPR節(jié)點(diǎn)集覆蓋的兩跳鄰居節(jié)點(diǎn).RFC362中MPR選取算法具體步驟如下[13]：

Step 1 初始化一個(gè)MPR節(jié)點(diǎn)集M，然后將中心節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)集中N1節(jié)點(diǎn)意愿度為WILL_ALWAYS的節(jié)點(diǎn)放入集合M中；

Step 2 計(jì)算N1中所有節(jié)點(diǎn)的深度D(y);

Step 3 判斷N1中是否存在可達(dá)到N2的唯一的一跳鄰居節(jié)點(diǎn).若存在，將此一跳鄰居節(jié)點(diǎn)放入集合M中并執(zhí)行Step 4；若不存在，則執(zhí)行Step 5；

Step 4 判斷N2中是否還存在未被集合M覆蓋的節(jié)點(diǎn).若存在，則執(zhí)行Step 5；若不存在，集合M即為最終的MPR節(jié)點(diǎn)集；

Step 5 計(jì)算一跳鄰居節(jié)點(diǎn)集N1中各節(jié)點(diǎn)的Reachability,在非零可達(dá)性的節(jié)點(diǎn)中選取N_willingness最高的節(jié)點(diǎn)作為MPR節(jié)點(diǎn).假如有多個(gè)備選節(jié)點(diǎn)，則選取可達(dá)性最高的節(jié)點(diǎn)作為MPR節(jié)點(diǎn)；若可達(dá)性也相同，則選擇D(y)最高的節(jié)點(diǎn)作為MPR節(jié)點(diǎn)并將其放入集合M中.接著，再次判斷N2中是否還存在未被集合M覆蓋的節(jié)點(diǎn).若存在，則繼續(xù)執(zhí)行Step 3；若不存在，集合M即為最終的MPR節(jié)點(diǎn)集.

1.2 層次分析法

層次分析法是一種多標(biāo)準(zhǔn)決策算法，它將復(fù)雜的決策過(guò)程簡(jiǎn)化為許多成對(duì)的比較，最后通過(guò)矩陣計(jì)算便可得到權(quán)重結(jié)果[14].AHP算法的具體步驟如下：

1)建立層次結(jié)構(gòu)

首先將需要解決的問(wèn)題放在目標(biāo)層，接著將進(jìn)行決策時(shí)考慮的方案或者約束放在準(zhǔn)則層，最后將實(shí)現(xiàn)目標(biāo)可選擇的候選方案放在方案層.圖1顯示了具體的層次結(jié)構(gòu)示意圖.

圖1 層次結(jié)構(gòu)示意圖Figure 1 Hierarchy Diagram

2)構(gòu)建判斷矩陣

根據(jù)各準(zhǔn)則對(duì)目標(biāo)層所造成的影響程度的大小將它們相互比較，并根據(jù)比較結(jié)果構(gòu)造判斷矩陣.假設(shè)有n個(gè)影響因素需要計(jì)算權(quán)重值，則構(gòu)造一個(gè)如式(1)所示的大小為B=(bij)n×n的n階矩陣.其中：bij表示準(zhǔn)則wi與準(zhǔn)則wj相比的重要程度，可根據(jù)表1對(duì)bij的值進(jìn)行選取.

(1)

3)權(quán)重計(jì)算

表1 1～9比例標(biāo)度含義Table 1 1～9 scale meaning

4)矩陣一致性檢驗(yàn)

對(duì)上述求得的權(quán)重值進(jìn)行一致性檢驗(yàn)，只有當(dāng)檢驗(yàn)結(jié)果符合給定的標(biāo)準(zhǔn)時(shí)才說(shuō)明求出來(lái)的權(quán)重值正確.首先跟據(jù)式(2)計(jì)算一致性指標(biāo)CI的值:

(2)

其中：n表示判斷矩陣的階數(shù).

通過(guò)表2確定N階矩陣B所對(duì)應(yīng)的平均隨機(jī)一致性指標(biāo)RI的值.最后，根據(jù)式(3)計(jì)算判斷矩陣B的一致性比率CR.

表2 n階矩陣與RI的取值Table 2 n-order matrix and the value of RI

(3)

如果CR<0.1，則說(shuō)明構(gòu)造的判斷矩陣滿(mǎn)足一致性標(biāo)準(zhǔn)，并且求出的權(quán)重值正確.否則，需要重新對(duì)各影響因素的相對(duì)重要程度進(jìn)行判斷，直到CR的值小于0.1為止.

2 本文算法

2.1 鏈路生存時(shí)間

本文的無(wú)人機(jī)節(jié)點(diǎn)采用高斯-馬爾可夫(GM)移動(dòng)模型，它是一種基于時(shí)間的移動(dòng)模型，通過(guò)一個(gè)調(diào)整參數(shù)來(lái)適應(yīng)不同程度的隨機(jī)性，從而避免節(jié)點(diǎn)速度和方向的突然改變[15].假設(shè)每個(gè)無(wú)人機(jī)節(jié)點(diǎn)都配備GPS和速度計(jì)，因此每個(gè)節(jié)點(diǎn)可以隨時(shí)獲取自己的坐標(biāo)和速度信息.本文以圖2為例計(jì)算無(wú)人機(jī)節(jié)點(diǎn)間的鏈路生存時(shí)間.

圖2 節(jié)點(diǎn)鏈路生存時(shí)間計(jì)算Figure 2 Node link lifetime calculation

(4)

(5)

將節(jié)點(diǎn)在三維空間中的運(yùn)動(dòng)映射到二維平面上，節(jié)點(diǎn)np到兩節(jié)點(diǎn)移動(dòng)路徑的垂直距離d(nq,l)為：

(6)

最后便可以計(jì)算出節(jié)點(diǎn)np和節(jié)點(diǎn)nq間的鏈路的持續(xù)時(shí)間tpq為：

(7)

對(duì)于正在執(zhí)行MPR集選取算法的中心節(jié)點(diǎn)來(lái)說(shuō)，要盡可能在一跳鄰居節(jié)點(diǎn)中選取鏈路生存時(shí)間長(zhǎng)的節(jié)點(diǎn)作為MPR，這樣才會(huì)使MPR節(jié)點(diǎn)與中心節(jié)點(diǎn)間的鏈路更加穩(wěn)定，網(wǎng)絡(luò)拓?fù)涞聂敯粜愿?2.2節(jié)點(diǎn)剩余能量

無(wú)人機(jī)節(jié)點(diǎn)的能量消耗包括兩個(gè)部分：一部分用于維持無(wú)人機(jī)節(jié)點(diǎn)自身的運(yùn)動(dòng)；另一部分用于保證節(jié)點(diǎn)間的正常通信.因此，節(jié)點(diǎn)總的能耗為：

(8)

由于無(wú)人機(jī)節(jié)點(diǎn)采用GM移動(dòng)模型，節(jié)點(diǎn)移動(dòng)過(guò)程中速度會(huì)發(fā)生改變.節(jié)點(diǎn)維持運(yùn)動(dòng)的能耗為：

(9)

(10)

(11)

節(jié)點(diǎn)通信能耗也包括兩個(gè)部分，分別是節(jié)點(diǎn)發(fā)送消息的能耗和節(jié)點(diǎn)接收消息能耗：

(12)

無(wú)人機(jī)節(jié)點(diǎn)發(fā)送消息消耗的能量包括節(jié)點(diǎn)發(fā)出消息消耗的能量和消息被傳輸相應(yīng)距離所消耗的能量:

(13)

其中：Eb表示節(jié)點(diǎn)發(fā)送單位比特?cái)?shù)據(jù)的能耗，Bs表示節(jié)點(diǎn)i發(fā)送的總比特?cái)?shù)，Et表示節(jié)點(diǎn)傳輸單位比特?cái)?shù)據(jù)的能耗，d表示兩節(jié)點(diǎn)間的距離.

無(wú)人機(jī)節(jié)點(diǎn)接收數(shù)據(jù)的能耗為：

(14)

其中：Br表示節(jié)點(diǎn)i收到的數(shù)據(jù)的總比特?cái)?shù)，Rb表示節(jié)點(diǎn)接收單位比特?cái)?shù)據(jù)的能耗.本文假設(shè)節(jié)點(diǎn)接收和發(fā)出單位比特的數(shù)據(jù)消耗的能量相同.

最后，可以計(jì)算出節(jié)點(diǎn)的剩余能量為：

(15)

2.3 改進(jìn)后的MPR選取算法

結(jié)合FANET的應(yīng)用場(chǎng)景，根據(jù)3種影響因素對(duì)MPR節(jié)點(diǎn)選取影響程度的不同進(jìn)行準(zhǔn)確的權(quán)重分配，并將其加權(quán)和m(i)作為MPR選取的綜合度量：

(16)

根據(jù)AHP算法的步驟對(duì)式(16)中的各權(quán)重因子進(jìn)行計(jì)算.首先通過(guò)分析建立節(jié)點(diǎn)選取層次結(jié)構(gòu)圖.然后，考慮到本文的應(yīng)用場(chǎng)景中節(jié)點(diǎn)運(yùn)動(dòng)速度較大、拓?fù)渥兓l繁，因此，將鏈路生存時(shí)間納為最重要的影響因素，其次考慮無(wú)人機(jī)節(jié)點(diǎn)的剩余能量對(duì)MPR節(jié)點(diǎn)選取的影響，最后考慮節(jié)點(diǎn)深度的影響.根據(jù)表1構(gòu)建判斷矩陣B為：

圖3 改進(jìn)后的MPR選取算法Figure 3 Improved MPR selection algorithm

3 仿真實(shí)驗(yàn)與結(jié)果分析

將改進(jìn)后的MPR選取算法應(yīng)用于OLSR協(xié)議中，以此來(lái)驗(yàn)證優(yōu)化后的LEC-OLSR路由協(xié)議的性能.本文從節(jié)點(diǎn)存活率、分組投遞率、平均端到端時(shí)延和路由開(kāi)銷(xiāo)這四種性能指標(biāo)上對(duì)改進(jìn)前后的路由協(xié)議進(jìn)行對(duì)比.

考慮在2 000 m×2 000 m×1 000 m的范圍內(nèi)進(jìn)行仿真且仿真時(shí)間為600 s，節(jié)點(diǎn)個(gè)數(shù)分別取 20、40、60、80、100，節(jié)點(diǎn)的通信范圍設(shè)為400 m.節(jié)點(diǎn)移動(dòng)速度在15～20 m/s之間且方向隨機(jī).數(shù)據(jù)包大小設(shè)置為512 Bytes,數(shù)據(jù)包發(fā)送間隔為0.1 s，具體的仿真參數(shù)如表3所示.

表3 仿真參數(shù)設(shè)置Table 3 Simulation parameter settings

由圖4中可知LEC-OLSR協(xié)議比OLSR協(xié)議具有更高的節(jié)點(diǎn)存活率.這是因?yàn)長(zhǎng)EC-OLSR協(xié)議在選取MPR節(jié)點(diǎn)時(shí)考慮了節(jié)點(diǎn)的剩余能量，避免了低能量節(jié)點(diǎn)被賦予高負(fù)載后的快速死亡，使節(jié)點(diǎn)的生命周期延長(zhǎng).當(dāng)節(jié)點(diǎn)個(gè)數(shù)大于40之后，LEC-OLSR協(xié)議在節(jié)點(diǎn)存活率上提升幅度增大，這是因?yàn)楣?jié)點(diǎn)個(gè)數(shù)增加后MPR節(jié)點(diǎn)的選取更加合理，故優(yōu)化更明顯.

圖4 節(jié)點(diǎn)存活率對(duì)比Figure 4 Comparison of node survival rate

由圖5可知相比于OLSR協(xié)議，當(dāng)節(jié)點(diǎn)個(gè)數(shù)較少時(shí)由于MPR候選節(jié)點(diǎn)較少兩種協(xié)議選取的MPR集差別不大，故LEC-OLSR協(xié)議在分組投遞率上的提升不夠明顯；當(dāng)節(jié)點(diǎn)數(shù)大于60后，LEC-OLSR協(xié)議在分組投遞率上有約3%的提升.這是因?yàn)镸PR候選節(jié)點(diǎn)增加，LEC-OLSR協(xié)議避免選取將要移出源節(jié)點(diǎn)通信范圍的節(jié)點(diǎn)作為MPR，增加了鏈路持續(xù)時(shí)間.同時(shí)，LEC-OLSR協(xié)議優(yōu)先選擇剩余能量較高的節(jié)點(diǎn)作為MPR，避免了由于節(jié)點(diǎn)能量不足而導(dǎo)致的鏈路斷開(kāi)，使分組投遞率得到提升.

圖5 分組投遞率對(duì)比Figure 5 Comparison of packet delivery rate

圖6顯示LEC-OLSR協(xié)議的時(shí)延比OLSR協(xié)議低，并且當(dāng)節(jié)點(diǎn)個(gè)數(shù)大于40時(shí)，LEC-OLSR協(xié)議的優(yōu)化更加明顯.這是因?yàn)楣?jié)點(diǎn)個(gè)數(shù)增多后備選MPR節(jié)點(diǎn)也隨之增多，LEC-OLSR協(xié)議會(huì)優(yōu)先選擇與源節(jié)點(diǎn)間鏈路更加穩(wěn)定的節(jié)點(diǎn)作為MPR，減少了重新尋找路由或者頻繁更換MPR所造成的數(shù)據(jù)包排隊(duì)時(shí)延，加快了數(shù)據(jù)包的傳輸使平均端到端時(shí)延降低.

圖6 平均端到端時(shí)延對(duì)比Figure 6 Comparison of average end-to-end delay

由圖7可知，相比于OLSR協(xié)議，LEC-OLSR協(xié)議帶來(lái)了更大的路由開(kāi)銷(xiāo).這是因?yàn)閷⒏倪M(jìn)后的MPR選取算法應(yīng)用于OLSR時(shí)對(duì)HELLO消息的格式進(jìn)行了修改并且添加了額外字段，從而使控制消息比特?cái)?shù)增加，網(wǎng)絡(luò)開(kāi)銷(xiāo)增大.當(dāng)網(wǎng)絡(luò)規(guī)模增大時(shí)，網(wǎng)絡(luò)中總的控制消息的比特?cái)?shù)迅速上升從而導(dǎo)致LEC-OLSR協(xié)議在路由開(kāi)銷(xiāo)這一性能指標(biāo)上有所劣化.

圖7 路由開(kāi)銷(xiāo)對(duì)比Figure 7 Comparison of routing overhead

4 結(jié) 語(yǔ)

對(duì)傳統(tǒng)OLSR協(xié)議可能會(huì)選取與源節(jié)點(diǎn)間鏈路易斷開(kāi)以及剩余能量不足的無(wú)人機(jī)節(jié)點(diǎn)成為MPR這一問(wèn)題，本文提出的基于層次分析法的多度量MPR選取算法綜合考慮了節(jié)點(diǎn)間鏈路生存時(shí)間、節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)覆蓋度這3種影響因素，利用層次分析法構(gòu)建判斷矩陣精確地計(jì)算各影響因素的權(quán)重因子，并將它們的加權(quán)和作為MPR節(jié)點(diǎn)的選取標(biāo)準(zhǔn).利用OMNeT++軟件在節(jié)點(diǎn)個(gè)數(shù)遞增種場(chǎng)景下對(duì)OLSR協(xié)議和改進(jìn)后的LEC-OLSR協(xié)議進(jìn)行仿真.仿真結(jié)果表明，LEC-OLSR協(xié)議雖然帶來(lái)了更大的路由開(kāi)銷(xiāo)，但在節(jié)點(diǎn)存活率、分組投遞率和平均端到端時(shí)延上都有一定程度的提升.