基于節(jié)點速度和能量的MPR節(jié)點集選擇*

陳炳才,孫少瑋,寧 芊

(1.新疆師范大學(xué)計算機(jī)科學(xué)技術(shù)學(xué)院,烏魯木齊 830054;2.大連理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,遼寧 大連 116024; 3.新疆師范大學(xué)物理與電子工程學(xué)院,烏魯木齊 830054)

在公共領(lǐng)域和軍事領(lǐng)域,無人機(jī)自組網(wǎng)都有很高的研究價值。因為,相較于單無人機(jī)系統(tǒng)而言,多無人機(jī)系統(tǒng)協(xié)同去完成一項任務(wù)時效率更高、成本更低。在軍事任務(wù)中,無人機(jī)機(jī)群往往更加需要協(xié)同去完成一項任務(wù),這就需要無人機(jī)之間組成無人機(jī)自組網(wǎng),即由若干無人機(jī)動態(tài)形成的、無需借助任何中心站的多跳無線移動通信網(wǎng)絡(luò)[1]。在公共領(lǐng)域中,無人機(jī)自組網(wǎng)可以與地面的人建立連接,也可收集傳感器的信息實時傳回控制中心,一般常常運用于野外救援、森林探測以及受災(zāi)地區(qū)網(wǎng)絡(luò)的恢復(fù)。

不同于其他的無線網(wǎng)絡(luò),在無人機(jī)網(wǎng)絡(luò)中經(jīng)常會存在節(jié)點的高速移動,從而節(jié)點的相對位置發(fā)生高動態(tài)變化,所以移動自組織網(wǎng)絡(luò)相對適合無人機(jī)網(wǎng)絡(luò)[2]。這是因為自組織網(wǎng)絡(luò)不需要任何的基礎(chǔ)設(shè)施,每個節(jié)點的地位相同,在無人機(jī)節(jié)點快速移動的過程中,網(wǎng)絡(luò)可以快速的進(jìn)行部署和組織,網(wǎng)絡(luò)自愈能力和抗毀能力強,在無人機(jī)協(xié)同完成任務(wù)時具備很高的適用性。

由于無人機(jī)機(jī)群在執(zhí)行任務(wù)時,自組網(wǎng)中每個無人機(jī)節(jié)點都要進(jìn)行信息的高實時共享,這就對時延提出了高要求,所以選擇先驗式路由協(xié)議OLSR具有很高的適用性。但是又考慮到節(jié)點速度和能量對整個網(wǎng)絡(luò)的影響,例如一些無人機(jī)節(jié)點已經(jīng)被選為MPR節(jié)點,但是由于節(jié)點的高速移動而脫離通信范圍,或者能量耗盡而提前退出網(wǎng)絡(luò),都會致使其無法再選為MPR節(jié)點,而重新建立路由則會導(dǎo)致整個網(wǎng)絡(luò)中端到端時延增加以及網(wǎng)絡(luò)開銷增大。另一方面,如果速度快能量低的節(jié)點被選為MPR節(jié)點,則會加劇節(jié)點的負(fù)擔(dān),加速其能量耗盡,從而會縮減整個網(wǎng)絡(luò)的壽命。所以該算法從無人機(jī)節(jié)點的能量和速度著手,在MPR選舉之前,先將速度高能量低的節(jié)點進(jìn)行預(yù)處理,最后在意愿值相同的情況下再次對節(jié)點的速度和能量加權(quán)計算,從而求得最優(yōu)MPR節(jié)點集。

1 路由協(xié)議

1.1 路由協(xié)議分析

目前,無線自組織網(wǎng)絡(luò)常規(guī)的路由協(xié)議主要分為兩類,一類是反應(yīng)式路由,另一類是先驗式路由。在反應(yīng)式路由協(xié)議的研究中,王頂[3]等人針對無人機(jī)網(wǎng)絡(luò)中鏈路間斷性的問題對AODV(Ad hoc On-Demand Distance Vector Routing)協(xié)議進(jìn)行了改進(jìn),該協(xié)議充分利用網(wǎng)絡(luò)中節(jié)點的速度和鄰居數(shù)等相關(guān)信息,在選擇路由時根據(jù)預(yù)先設(shè)置的閾值判斷鏈路質(zhì)量。JDMM Biomo等人提出了在AODV協(xié)議的基礎(chǔ)上,為了實現(xiàn)路由發(fā)現(xiàn)的跳數(shù)最小化,利用路徑跳數(shù)、路徑新舊程度、路徑可靠性來進(jìn)行路徑的選擇[4]。而在先驗式路由協(xié)議中,Zheng Y等人[5]針對無人機(jī)自組網(wǎng)的特性提出了一種基于移動性和負(fù)載感知的ML-OLSR協(xié)議,得到了較高的分組交付率以及較低的時延。劉杰等人[6]針對OLSR中的MPR節(jié)點集提出一種基于貪婪算法改進(jìn)的OP_MPR算法,該算法可以對MPR集進(jìn)行優(yōu)化,從而得到更優(yōu)更小的MPR節(jié)點集。之后董思妤,張洪,王路等人提出一種多維感知的OLSR協(xié)議,針對無人機(jī)自組網(wǎng)的特性進(jìn)行綜合度量[7]。通過國內(nèi)外文獻(xiàn)可以看到,在無人機(jī)自組網(wǎng)中,先驗式路由協(xié)議中OLSR協(xié)議的研究具有很高可行性。

1.2 OLSR路由協(xié)議

OLSR[8-10]優(yōu)化鏈路狀態(tài)路由協(xié)議是經(jīng)典的鏈路狀態(tài)協(xié)議的一種優(yōu)化改進(jìn)后的算法。它是一種先驗式的路由協(xié)議,它通過控制信息的洪泛感知鄰居節(jié)點的信息,鏈路的狀態(tài)以及整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。運用HELLO分組的交互完成鏈路探測,鄰居發(fā)現(xiàn)以及MPR節(jié)點的選擇;利用TC分組的交互,在發(fā)布MPR節(jié)點信息后建立整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu);最后運用Dijkstra算法動態(tài)的計算到達(dá)成員節(jié)點間的最短路徑,生成路由表,并對其進(jìn)行周期性的維護(hù)。相對與傳統(tǒng)的鏈路狀態(tài)協(xié)議來說,OLSR路由協(xié)議主要進(jìn)行了以下幾點改進(jìn)與優(yōu)化:①擁有了辨別新舊路徑的序列號。在TC分組中有一個序列號的字段,根據(jù)序列號的大小來區(qū)別新舊消息,從而使新舊路徑不斷地進(jìn)行更新,并且控制分組也不用按照有序的方式進(jìn)行傳輸。②MPR多點中繼機(jī)制的增加。MPR機(jī)制大大減少了傳統(tǒng)鏈路狀態(tài)協(xié)議中消息洪泛的范圍。選取部分的節(jié)點作為MPR節(jié)點,并保證通過MPR節(jié)點在轉(zhuǎn)發(fā)廣播分組的時候可以遍布整個網(wǎng)絡(luò)。轉(zhuǎn)發(fā)時節(jié)點先判斷自己是否為MPR節(jié)點,如果是則轉(zhuǎn)發(fā)分組,這樣在保證低時延的情況下大大減少了網(wǎng)絡(luò)的開銷。③減少了路由表的條目。正是因為采用了MPR機(jī)制,在中心節(jié)點與其一跳鄰居和二跳鄰居之間的鏈路信息就會相應(yīng)的減少,每個成員節(jié)點以此節(jié)點建立并保持的路由信息也會相應(yīng)的減少。

2 基于速度和能量的MPR節(jié)點集選舉

無線自組網(wǎng)的特點是多變的網(wǎng)絡(luò)拓?fù)洹⒂邢薜膫鬏攷挕⒁苿咏K端的局限性、單向信道的存在和分布式控制等。而在無人機(jī)自組網(wǎng)中由于節(jié)點的高速移動性和節(jié)點能量的限制性[11]給上述困難帶來了更大的挑戰(zhàn),這種高速移動會導(dǎo)致拓?fù)涞母邉討B(tài)變化,網(wǎng)絡(luò)的連同性以及協(xié)議的性能都會因此而產(chǎn)生嚴(yán)重的影響。并且在無人機(jī)自組網(wǎng)中,由于無人機(jī)的隨機(jī)移動[12-14]、無線信道間的相互干擾以及地形等綜合因素的影響,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化的方式和速度都是不可預(yù)測的,這使得路由異常重要。這就要求充分的將速度和能量考慮到協(xié)議中去。為更好地適應(yīng)無人機(jī)快速移動和能量有限的特性,提出了基于節(jié)點速度和能量的MPR選舉算法,通過HELLO消息的交互感知鄰居節(jié)點的速度和能量,然后將節(jié)點的速度和能量散布到整個網(wǎng)絡(luò),從而為MPR選舉時的計算提供衡量標(biāo)準(zhǔn)。下面將對MPR機(jī)制和改進(jìn)后的MPR機(jī)制進(jìn)行介紹。

2.1 MPR機(jī)制

在OLSR路由協(xié)議中的核心就是MPR機(jī)制,由于在此機(jī)制下,網(wǎng)絡(luò)中的每個節(jié)點都要選擇一部分自己的對稱鄰居節(jié)點作為通信的中繼節(jié)點,即 MPR 節(jié)點,而該節(jié)點自身則成為MS(MPR Selector)節(jié)點。MPR節(jié)點一般是中心節(jié)點的一跳鄰居中可以和所有二跳鄰居成對稱鏈路的一跳鄰居。之后每個節(jié)點選擇MPR節(jié)點廣播分組。這樣,中心節(jié)點與其一跳鄰居之間的廣播分組數(shù)量會大量的減少,所以它的增加可以有效的減小網(wǎng)絡(luò)的開銷。尤其是在節(jié)點密度大,數(shù)量多的大規(guī)模網(wǎng)絡(luò)中,MPR機(jī)制的優(yōu)勢會愈發(fā)明顯。剩下的那些非 MPR 的節(jié)點也會接收和處理廣播消息,但它們不會轉(zhuǎn)發(fā)任何收到的控制消息。

從圖1可以看出,利用MPR機(jī)制可以在消息散布到整個網(wǎng)絡(luò)的情況下有效地減少中繼節(jié)點的數(shù)量,從而減少了廣播的范圍,也減少了節(jié)點所接收到重復(fù)分組的數(shù)量,從而可以大大減少網(wǎng)絡(luò)開銷。

圖1 非選擇洪泛和MPR機(jī)制節(jié)點中繼

2.2 基于速度和能量的MPR選舉算法

本節(jié)針對標(biāo)準(zhǔn)OLSR協(xié)議中MPR節(jié)點選舉的過程做以下改進(jìn):在MPR節(jié)點選舉之前基于速度和能量對節(jié)點進(jìn)行預(yù)處理,選出節(jié)點能量較小速度較快的幾個節(jié)點使其永不會成為MPR節(jié)點;在計算MPR節(jié)點時,如果存在兩跳鄰居沒有被完全覆蓋,而且節(jié)點的意愿值和深度都相同,則再次對節(jié)點的速度和能量進(jìn)行加權(quán)比較,將速度低能量高的節(jié)點加入MPR節(jié)點集,直至二跳鄰居完全被覆蓋。這樣可以有效的減少MPR節(jié)點集的數(shù)量,并且通過對節(jié)點的預(yù)處理會減少算法中需要計算的節(jié)點規(guī)模,從而加快MPR節(jié)點集的計算速度。

2.2.1 算法相關(guān)概念

willingness:意愿值表示一個節(jié)點為另一個節(jié)點傳輸網(wǎng)絡(luò)數(shù)據(jù)的意愿程度,其中包括5種,分別為WILL_NEVER 0、WILL_LOW 1、WILL_DEFAULT 3、WILL_HIGH 6和WILL_HIGH 7,從0-7傳輸消息的意愿程度逐漸遞增。

N:以圖2為例,節(jié)點1-6就是節(jié)點0的一跳鄰居節(jié)點集。

圖2 MPR算法相關(guān)概念示意圖

N2:以圖2為例,一個節(jié)點的兩跳鄰居節(jié)點集應(yīng)該為a-f,但不包括下面這幾類節(jié)點。

①如果一個節(jié)點只能通過集合N中某成員到達(dá),而N中成員的意愿值為WILL_NEVER,那么此節(jié)點不屬于N2。例如圖二中節(jié)點a只能通過N中成員節(jié)點1到達(dá),但如果節(jié)點1的willingness為WILL_NEVER,那么節(jié)點a不屬于N2。

②如果一個節(jié)點是正在進(jìn)行計算的節(jié)點,那么此節(jié)點不屬于N2。例如圖二中節(jié)點0不屬于N2。

③所有的對稱鄰居:它們與此節(jié)點的某些接口間存在對稱鏈路。例如圖二中節(jié)點2,它雖然可以通過節(jié)點1兩跳到達(dá),但與節(jié)點0具有對稱鏈路,所以不屬于N2。

D(y):一跳鄰節(jié)點y的深度(y為N的一個成員),被定義為節(jié)點y對稱鄰節(jié)點的數(shù)量,不包括N的所有成員以及進(jìn)行計算的這個節(jié)點。例如圖二中節(jié)點1的深度為2,其中包括了節(jié)點a和節(jié)點b。

Reachability:到達(dá)性在進(jìn)行計算MPR集時用到。表示在去除所有此時的MPR集節(jié)點及其覆蓋的兩跳節(jié)點后。某一跳鄰節(jié)點的對稱鄰節(jié)點數(shù)量,不包括N的所有成員以及進(jìn)行計算的這個節(jié)點。例如圖二中若此時只有節(jié)點1被選為MPR,則計算節(jié)點2的到達(dá)性為2,包括節(jié)點c和節(jié)點d,而不包括被節(jié)點1覆蓋的節(jié)點b。

2.2.2 剩余能量及節(jié)點權(quán)重建模

由于在HELLO分組的交互過程中要互相感知鄰居節(jié)點的速度和能量,并在MPR節(jié)點的計算時需要根據(jù)剩余能量和速度對節(jié)點進(jìn)行預(yù)處理,所以針對網(wǎng)絡(luò)中節(jié)點發(fā)送和接收數(shù)據(jù)建立一階能量消耗模型,如下所示:

Etx(k,r)=Eelk+kpr2

(1)

Erx(k,r)=Eelk

(2)

其中k為發(fā)送信息的比特數(shù),r表示傳輸距離,Eel表示為電路元件發(fā)送和接收單位比特數(shù)據(jù)所消耗的能量,p表示功率放大器發(fā)送單位比特數(shù)據(jù)的能耗系數(shù)。Etx(k,r)表示發(fā)送k比特數(shù)據(jù),傳輸距離為r的情況下的耗能情況。Erx(k,r)表示在傳輸距離為r,接收k比特數(shù)據(jù)所需要消耗的能量。

在對MPR節(jié)點集的選擇進(jìn)行預(yù)處理時,首先要將能量較低的節(jié)點除去,這就需要我們預(yù)先設(shè)置一個閾值,閾值設(shè)定如下所示:

El=Ei-Etx(k,r)-Erx(k,r)

(3)

(4)

其中Ei表示i節(jié)點的初始能量,并通過初始能量Ei減去節(jié)點發(fā)送和接收數(shù)據(jù)所消耗的能量,計算出節(jié)點的剩余能量El,limit表示節(jié)點剩余能量占所有節(jié)點初始能量均值的比值。文章中通過limit的值來衡量一個節(jié)點剩余能量的狀況,limit的值越小表示剩余能量越低,并將limit值低于臨界值的節(jié)點定義為低能量節(jié)點。經(jīng)過實驗分析,limit的臨界值設(shè)置為20%較為合理,當(dāng)limit<20%時,更新節(jié)點的willingness值為0,使其永遠(yuǎn)喪失成為MPR節(jié)點的資格。

如果二跳鄰居沒有被完全覆蓋且MPR節(jié)點的候選節(jié)點意愿值和深度都相同,則需要對節(jié)點的速度和能量進(jìn)行加權(quán)計算,本文設(shè)置的權(quán)重計算模型如下所示:

weight=αEi+βEl-γV

(5)

由于算法首先是依據(jù)節(jié)點能量高低進(jìn)行預(yù)處理的,所以算法的重點在于節(jié)點的能量比較及處理。式(5)中,Ei和El分別表示節(jié)點的初始能量和剩余能量,weight表示節(jié)點競爭MPR節(jié)點時的權(quán)值,V表示節(jié)點的移動速度,α,β,γ分別對應(yīng)節(jié)點這三個屬性的權(quán)重因子。算法考慮到節(jié)點能量的重要性,為了提高節(jié)點在競爭MPR節(jié)點時初始能量和剩余能量的權(quán)重,將α,β系數(shù)的值均設(shè)為0.4,將速度對應(yīng)的γ值設(shè)置為0.2。從式(5)還可以看出,能量越高,速度越低,weight值越大,也就是說高能量低速度的節(jié)點被選為MPR節(jié)點的機(jī)會就越大,從而權(quán)重模型滿足算法的整體需求。

2.2.3 基于速度和能量的MPR集的選舉

運用OLSR協(xié)議中HELLO分組的交互完成鏈路的探測和鄰居的發(fā)現(xiàn)。在鄰居信息交互的過程中,感知鄰居節(jié)點的速度和剩余能量,并將其保存在鄰居信息組中,以便于后面MPR節(jié)點集的計算。

考慮節(jié)點速度和能量MPR選舉算法的具體步驟如下:

Step 1 for it=N.begin( ):N.end( )

其中N為中心節(jié)點一跳鄰居節(jié)點集,在節(jié)點的一跳鄰居節(jié)點集中選擇出剩余能量較低的幾個節(jié)點加入low節(jié)點集中,如果節(jié)點的剩余能量相同,對節(jié)點的速度進(jìn)行比較,速度大的加入low節(jié)點集中。

end

Step 2 for it=low.begin( ):low.end( )

如果low節(jié)點集中的一跳鄰居的主地址和N節(jié)點集中一跳鄰居的主地址相同,那么將N中與其相對應(yīng)的節(jié)點的意愿值willingness設(shè)置為WILL_NEVER。

end

Step 3 先將N中所有意愿值willingness為WILL_ALWAYS的節(jié)點加入MPR節(jié)點集中。

Step 4 計算N中所有的節(jié)點y的深度D(y)。

Step 5 將N中滿足條件的節(jié)點加入到MPR集:它是到達(dá)N2中某一節(jié)點的唯一節(jié)點。移除N2中目前被MPR集覆蓋的節(jié)點。

Step 6 當(dāng)N2中存在不被MPR集中任何節(jié)點覆蓋的節(jié)點,執(zhí)行以下過程。若不存在,算法結(jié)束。?對N中的每個節(jié)點,計算其到達(dá)性。?在N中到達(dá)性非0且具有最高willingness的節(jié)點中選擇一個MPR,willingness相同時,選擇到達(dá)性最高的。到達(dá)性相同時,選擇D(y)高的。D(y)相同時,選擇速度和能量加權(quán)計算后最佳的節(jié)點。移除N2中目前被MPR集覆蓋的節(jié)點。回到Step 3。

3 仿真實驗結(jié)果分析

在無人機(jī)自組網(wǎng)環(huán)境下,為了對改進(jìn)后OLSR路由協(xié)議進(jìn)行評估,運用OMNeT++仿真平臺對其進(jìn)行了仿真實驗,并與原協(xié)議、反應(yīng)式路由協(xié)議DSR(Dynamic Source Routing)在端到端時延、吞吐量[15]及節(jié)點能量消耗三個指標(biāo)進(jìn)行了對比分析。

3.1 仿真參數(shù)設(shè)置

圖3 網(wǎng)絡(luò)仿真場景圖

網(wǎng)絡(luò)的仿真實驗場景圖如圖3所示,所有的無人機(jī)節(jié)點都采用隨機(jī)移動模型,目的節(jié)點也是隨機(jī)設(shè)置的。

本組實驗的仿真場景為1 400 m×800 m的矩形區(qū)域,仿真時間為100 s,仿真節(jié)點個數(shù)為 20個,每個節(jié)點的無線覆蓋范圍為250 m。節(jié)點的移動模型設(shè)置為隨機(jī)模型,移動速度為隨機(jī)80 m/s～110 m/s,節(jié)點的初始位置也隨機(jī)。節(jié)點的最大能量設(shè)置為1 J,每個節(jié)點能量的初始值隨機(jī)。具體的仿真參數(shù)設(shè)置如表1所示。

表1 節(jié)點隨機(jī)移動網(wǎng)絡(luò)場景參數(shù)

表2 信道物理參數(shù)

表3 路由協(xié)議相關(guān)參數(shù)

3.1 仿真結(jié)果分析

從仿真結(jié)果中可以看到在無人機(jī)自組網(wǎng)中,基于節(jié)點速度和能量MPR選舉的OLSR協(xié)議性能指標(biāo)均優(yōu)于DSR協(xié)議與原協(xié)議,并且得到了最優(yōu)MPR節(jié)點集,從而降低了時延,提高了網(wǎng)絡(luò)的整體性能。

圖4為基于速度和能量MPR選舉的OLSR協(xié)議與原協(xié)議、DSR協(xié)議的時延對比。

圖4 端到端時延對比圖

經(jīng)過兩次對曲線進(jìn)行移動平均處理,從圖4中可以清楚看出,在節(jié)點移動速度高的情況下,DSR協(xié)議的延時抖動很明顯,但是基于速度和能量的OLSR協(xié)議延時抖動很小,而且時延明顯低于DSR協(xié)議與原協(xié)議。

圖5為基于速度和能量MPR選舉的OLSR協(xié)議與原協(xié)議的吞吐量對比。

圖5 吞吐率對比圖

從圖5中可以看出,由于起始階段網(wǎng)絡(luò)中各個模塊處于初始化階段,每個模塊通過發(fā)送自消息進(jìn)行初始化,所以吞吐量為0。但是之后可以看到,基于速度和能量MPR選舉的OLSR協(xié)議吞吐量大于OLSR原協(xié)議,提高了網(wǎng)絡(luò)的穩(wěn)定性。

圖6為基于速度和能量MPR選舉的OLSR協(xié)議與DSR協(xié)議的節(jié)點能量消耗對比。

圖6 節(jié)點能量消耗對比圖

由圖6可以看出,節(jié)點的初始能量值均為0.6J,隨著仿真時間的增加,節(jié)點的剩余能量不斷減少,同時可以清楚的看出基于速度和能量的OLSR協(xié)議在能量消耗方面低于DSR協(xié)議,為網(wǎng)絡(luò)中節(jié)點的生命周期提供了保障。

4 結(jié)論

針對無人機(jī)自組網(wǎng)中節(jié)點高速移動和節(jié)點能量有限的問題,提出一種基于節(jié)點速度和能量的MPR選舉算法。首先,對速度高能量低的節(jié)點進(jìn)行預(yù)處理,減小了MPR節(jié)點計算的規(guī)模,從而提高M(jìn)PR集計算的速度。之后在MPR集計算的過程中對速度和能量進(jìn)行加權(quán)衡量,最終得到最優(yōu)的MPR節(jié)點集。仿真實驗結(jié)果表明,基于節(jié)點速度和能量MPR選舉的OLSR協(xié)議在無人機(jī)自組網(wǎng)中有很好的適用性。進(jìn)一步,我們將考慮通過縮減MPR節(jié)點的數(shù)量,得到一個最小MPR節(jié)點集,從而解決先驗式路由協(xié)議開銷大的問題。