基于雙重虛擬力算法的移動自組織網(wǎng)絡(luò)節(jié)點移動策略研究*

趙克華,劉半藤

(浙江樹人大學(xué)信息工程學(xué)院,杭州 310015)

隨著信息技術(shù)的高速發(fā)展,無線自組織網(wǎng)絡(luò)MANETs(Wireless Mobile Ad Hoc Networks)已經(jīng)逐漸發(fā)展成為21世紀信息產(chǎn)業(yè)的重要支柱。由于MANETs具備節(jié)點移動靈活、不受固有通信設(shè)施影響等特點,被廣泛地應(yīng)用于軍事、民用、商業(yè)等領(lǐng)域。由于MANETs節(jié)點移動過程帶來的不確定性容易出現(xiàn)連通性、覆蓋率、生存時間等網(wǎng)絡(luò)性能下降,專家學(xué)者開展了針對性的研究[1-7],也提出了多種節(jié)點移動策略,虛擬力移動策略就是其中的典型代表。

魏連鎖等[1]對傳統(tǒng)的虛擬力進行改進,將網(wǎng)絡(luò)節(jié)點的鄰居節(jié)點數(shù)量以及到鄰居節(jié)點的距離進行屬性加權(quán)修正虛擬力數(shù)值,提出一種錨節(jié)點移動策略。目前,基于虛擬力算法制定的節(jié)點移動策略多以提高網(wǎng)絡(luò)整體覆蓋率為研究目標[7-18]。張穎等[8]采用一種改進的虛擬力和果蠅優(yōu)化算法對水下傳感器網(wǎng)絡(luò)進行節(jié)點部署。首先,將節(jié)點隨機散布在網(wǎng)絡(luò)中;然后,網(wǎng)絡(luò)中的每個節(jié)點都按照虛擬力的方式進行定向移動,直至最優(yōu)位置,從而實現(xiàn)整體網(wǎng)絡(luò)的高效覆蓋。王雪[9]等結(jié)合粒子群算法與虛擬力算法,提出了一種虛擬力導(dǎo)向微粒群優(yōu)化策略,提高整體網(wǎng)絡(luò)覆蓋率,加快算法收斂速度。王婷婷[10]等提出了一種基于Voronoi多邊形形心引力的虛擬力覆蓋優(yōu)化算法,可以有效地降低覆蓋盲區(qū),提高網(wǎng)絡(luò)覆蓋率。滕志軍[11]等利用節(jié)點自身密集度來選擇虛擬力模型中最優(yōu)距離閾值,從而改進傳統(tǒng)的虛擬力模型,最終實現(xiàn)網(wǎng)絡(luò)節(jié)點的部署優(yōu)化。Hamid Mahboubi[12]等采用多權(quán)重的Voronoi方法計算傳感器的傳感范圍,提高網(wǎng)絡(luò)覆蓋的有效性。JIANG Yibo[13]等提出一種基于虛擬勢場的虛擬力增強覆蓋算法,對虛擬力的方向進行分解,再根據(jù)雙節(jié)點覆蓋模型,引入質(zhì)心計算,通過虛擬勢場修正虛擬力指標,對網(wǎng)絡(luò)進行部署,以消除目標區(qū)域內(nèi)的盲區(qū)和重疊區(qū),提高網(wǎng)絡(luò)覆蓋率。GUAN Zhiyan[14]等提出了一種基于差分進化和混合虛擬力的定向傳感器網(wǎng)絡(luò)覆蓋算法,利用差分進化模型和混合虛擬力來避免局部次優(yōu)解,減少重疊面積,提高網(wǎng)絡(luò)有效覆蓋率。傳統(tǒng)的虛擬力算法通過采集鄰居節(jié)點的信息,并與事先確定的閾值進行比較判斷,確定節(jié)點所受斥力或者引力的大小及方向。節(jié)點根據(jù)所受力的大小及方向進行定向移動。但傳統(tǒng)的虛擬力閾值設(shè)置方式較為單一,主要考慮節(jié)點間的距離或者節(jié)點密度。MANET性能指標較多,區(qū)域覆蓋率、節(jié)點連通性、網(wǎng)絡(luò)生存時間等都需要考慮。因此,網(wǎng)絡(luò)節(jié)點的最優(yōu)移動策略屬于多目標優(yōu)化問題,一種NP-hard問題。為此,本文提出了一種雙重虛擬力算法DVFA(Dual Virtual Force Algorithm),同時考慮網(wǎng)絡(luò)節(jié)點密度分布與網(wǎng)絡(luò)生存時間兩項指標,計算節(jié)點所受到的斥力與引力,將兩種不同屬性的虛擬力進行融合,從而制定節(jié)點移動策略。

1 節(jié)點模型

1.1 節(jié)點移動模型

假設(shè)在區(qū)域為Sa×Sb的矩形MANET中部署N個可自由移動的節(jié)點,并為每個節(jié)點標號為1,2,…,N。在時刻t,標號為i的節(jié)點坐標表示為(xi(t),yi(t))。網(wǎng)絡(luò)中的每個節(jié)點每隔Δt時間進行一次移動,節(jié)點的最大移動速率為vmax。節(jié)點的基本移動方式可以表達如下:

式中,(xi(t+Δt),yi(t+Δt))表示標號為i的節(jié)點移動后的坐標。假設(shè)節(jié)點移動過程中遇到網(wǎng)絡(luò)邊界時便進行反向移動。θi(t)表示標號為i的節(jié)點在時刻t的移動方向。vi(t)表示標號為i的節(jié)點在時刻t的移動速率,vi(t)∈[0,vmax]。節(jié)點移動策略就是確定各節(jié)點各時刻的移動方向和移動速率。

1.2 節(jié)點連通性模型

假設(shè)MANET中每個節(jié)點都具有相同通信半徑Rcom以及相同覆蓋半徑Rcov,如圖1所示。如果兩個節(jié)點之間的距離小于通信半徑Rcom,則認為此兩個節(jié)點相互之間一跳連通。

圖1 節(jié)點連通半徑和覆蓋半徑示意圖

由于節(jié)點處于移動狀態(tài),網(wǎng)絡(luò)的連通矩陣也將隨著時間推移發(fā)生變化。時刻t,網(wǎng)絡(luò)節(jié)點之間的一跳(one hop)連通矩陣CO(t)=[coij(t)]N×N計算方式如下:

如果cij(t)=1,說明時刻t標號為i與標號為j的節(jié)點之間可以直接通信。

MANET中,節(jié)點具備信息收發(fā)與信息中轉(zhuǎn)雙重功能。不在一跳通信范圍內(nèi)的兩個節(jié)點之間,可以通過其他節(jié)點作為中間節(jié)點轉(zhuǎn)發(fā)信息實現(xiàn)通信業(yè)務(wù)。時刻t,節(jié)點之間的多跳(multi hops)連通矩陣CM(t)=[cmij(t)]N×N計算方式如下[19]:

式中,TM(t)=[tmij(t)]N×N為臨時變量,表示節(jié)點之間通過N跳轉(zhuǎn)發(fā)實現(xiàn)通信業(yè)務(wù)的情況。如果cmij(t)=1,說明時刻t標號為i與標號為j的節(jié)點之間可以通過多跳轉(zhuǎn)發(fā)實現(xiàn)通信業(yè)務(wù)。時刻t,MANET的節(jié)點連通性指標LT(t)計算方式如下:

1.3 網(wǎng)絡(luò)覆蓋率模型

MANET中,每個節(jié)點都可以采集覆蓋半徑Rcov區(qū)域內(nèi)的信息。網(wǎng)絡(luò)覆蓋率可以用被覆蓋面積與整體網(wǎng)絡(luò)面積之比進行衡量。考慮到連續(xù)性給覆蓋率指標計算帶來的復(fù)雜性,本文采用一種離散方式近似計算網(wǎng)絡(luò)覆蓋率[20-21]。將Sa×Sb的MANET以 1 m 為步長劃分為網(wǎng)格,共計M個格點,并為每個格點標號為1,2,…,M,如圖2所示。以被覆蓋的格點數(shù)量與格點總數(shù)之比衡量網(wǎng)絡(luò)覆蓋率。

圖2 MANET離散示意圖

劃分后的網(wǎng)格中,第i個格點的坐標表示為(pxi,pyi)。格點的坐標不隨時間推移而發(fā)生變化。時刻t,節(jié)點與格點的覆蓋矩陣F(t)=[fij(t)]N×M計算方式表達如下:

如果fij(t)=1,說明時刻t標號為i的節(jié)點可以覆蓋標號為j的格點。當(dāng)格點被一個及以上的節(jié)點覆蓋時,可以認為該格點被覆蓋。MANET覆蓋矩陣G(t)=[gi(t)]M計算方式如下:

如果gi(t)=1,說明時刻t標號為i的格點可以被有效覆蓋。因此,MANET的網(wǎng)絡(luò)在時刻t覆蓋率指標FG(t)計算方式如下:

圖3 一階能量消耗模型示意圖

1.4 節(jié)點能耗模型

假設(shè)MANET中節(jié)點傳輸信息服從一階能量消耗模型[22-23]。節(jié)點發(fā)送信息能耗包括發(fā)射電路能耗、放大電路能耗兩部分,節(jié)點接收信息能耗僅為接收電路能耗,如圖3所示。

一階能量消耗模型計算公式如下所示:

式中,ETx表示節(jié)點發(fā)送信息能耗,Eelec表示發(fā)射電路和接收電路能耗,l表示發(fā)送數(shù)據(jù)的比特數(shù),efs表示能耗常數(shù),ds表示發(fā)送節(jié)點與接收節(jié)點之間的距離。

除發(fā)送信息和接收信息的能量消耗外,假設(shè)節(jié)點移動的能耗為一固定值,且由于節(jié)點待機時能耗較少,故本文假設(shè)待機能耗忽略不計。

2 雙重虛擬力移動模型

2.1 雙重虛擬力的基本思想

MANET中的每個節(jié)點都可以感知其通信范圍內(nèi)鄰居節(jié)點的相關(guān)信息。虛擬力的基本思想可以歸納為:每個節(jié)點都將受到鄰居節(jié)點的影響,這種影響以“力”的方式改變節(jié)點的移動方式。本節(jié)主要討論與距離相關(guān)的“距離虛擬力”和與能量相關(guān)的“能量虛擬力”的設(shè)置方式,將兩種屬性的虛擬力進行融合提出了一種雙重虛擬力算法DVFA。通過DVFA制定節(jié)點移動策略,從而確定節(jié)點的移動方向與移動速率。

MANET的節(jié)點分布不能過于密集,否則將造成MANET的覆蓋率指標下降。同時,節(jié)點分布也不能過于稀疏,否則將造成MANET的連通性指標下降。為此,需要為每個節(jié)點配置距離閾值Td。當(dāng)鄰居節(jié)點與本地節(jié)點之間的距離超過距離閾值時,本地節(jié)點將向靠近該鄰居節(jié)點方向移動;當(dāng)鄰居節(jié)點與本地節(jié)點之間的距離低于距離閾值時,本地節(jié)點將向遠離該鄰居節(jié)點方向移動,如圖4所示。圖中標號為1的節(jié)點通信范圍內(nèi)有4個鄰居節(jié)點,可以感知此4個鄰居節(jié)點到節(jié)點1的距離。節(jié)點2和節(jié)點5到節(jié)點1的距離小于距離閾值Td,節(jié)點1將向遠離節(jié)點2和節(jié)點5的方向移動;節(jié)點3和節(jié)點4到節(jié)點1的距離大于距離閾值Td,節(jié)點1將向靠近節(jié)點3和節(jié)點4的方向移動。

圖4 距離閾值示意圖

由于網(wǎng)絡(luò)中節(jié)點承擔(dān)著信息轉(zhuǎn)發(fā)的業(yè)務(wù),需要避免低能量節(jié)點被頻繁地作為中間節(jié)點轉(zhuǎn)發(fā)信息,而降低網(wǎng)絡(luò)生存時間。為此,需要為每個節(jié)點配置能量閾值tei。當(dāng)鄰居節(jié)點的剩余能量高于能量閾值時,本地節(jié)點將向靠近該鄰居節(jié)點方向移動;當(dāng)鄰居節(jié)點的剩余能量低于能量閾值時,本地節(jié)點將向遠離該鄰居節(jié)點方向移動,從而降低該低能量節(jié)點作為中間節(jié)點轉(zhuǎn)發(fā)信息的概率,如圖5所示。圖中標號為1的節(jié)點通信范圍內(nèi)有4個鄰居節(jié)點,可以感知此4個鄰居節(jié)點的剩余能量。節(jié)點3和節(jié)點5的剩余能量超過能量閾值te1,節(jié)點1將向靠近節(jié)點3和節(jié)點5方向移動;節(jié)點2和節(jié)點4的剩余能量低于能量閾值te1,節(jié)點1將向遠離節(jié)點2和節(jié)點4的方向移動。

圖5 能量閾值示意圖

綜上所述,節(jié)點1的移動方式受到其四個鄰居節(jié)點的影響。這種影響通過能量與距離兩種方式施加于節(jié)點1對其產(chǎn)生“能量虛擬力”與“距離虛擬力”,節(jié)點1將在兩者合力的作用下進行移動,這就是本文的雙重虛擬力算法DVFA。

2.2 雙重虛擬力的參數(shù)設(shè)定

首先,討論距離閾值Td的設(shè)定方式。距離閾值設(shè)定的目的是為達到節(jié)點均勻地分布于MANET。因此,可以考慮將節(jié)點均勻分布時,相鄰兩節(jié)點之間的距離作為距離閾值Td。在區(qū)域為Sa×Sb的MANET中部署N個節(jié)點,每個節(jié)點的覆蓋范圍用正六邊形近似替代,如圖6所示。因此,距離閾值Td的計算方式如下所示:

圖6 距離閾值計算示意圖

然后,討論能量閾值tei的設(shè)定方式。以i表示本地節(jié)點的標號,Ui表示節(jié)點i的鄰居節(jié)點集合。能量閾值設(shè)定的目的是為本地節(jié)點拉近高能量鄰居節(jié)點,遠離低能量鄰居節(jié)點,延長網(wǎng)絡(luò)生存時間。故可以考慮將時刻t節(jié)點i的鄰居節(jié)點集Ui平均能量作為節(jié)點i的能量閾值tei(t)。由于每個節(jié)點的鄰居節(jié)點集合不同,使得每個節(jié)點的能量閾值各不相同,且隨著時間推移而發(fā)生變化。因此,能量閾值tei(t)的計算方式如下所示:

其中,Ej(t)表示時刻t鄰居節(jié)點j的剩余能量。由于節(jié)點能量隨著時間而下降,節(jié)點的能量閾值也將隨著時間推移而發(fā)生變化。

3 數(shù)值仿真

為評估本文所提出的雙重虛擬力DVFA而制定的節(jié)點移動策略對MANET整體性能產(chǎn)生的影響,本節(jié)采用MATLAB軟件進行網(wǎng)絡(luò)性能的數(shù)值仿真。在一個300 m×300 m的正方形網(wǎng)絡(luò)區(qū)域,隨機散布80個節(jié)點。以節(jié)點模塊CC1100[25]作為參考,設(shè)定節(jié)點的最大移動速度為1 m/s,節(jié)點覆蓋半徑為60 m,通信半徑為覆蓋半徑的1.2倍,統(tǒng)計進行節(jié)點100次移動的軌跡。與傳統(tǒng)虛擬力算法VFA(Virtual Force Algorithm)[26]、改進的虛擬力算法TVFA(Triangulation for Virtual Force Algorithm)[27]相比較,在雙重虛擬力DVFA作用下節(jié)點連通性隨時間變化如圖7所示,網(wǎng)絡(luò)覆蓋率隨時間變化如圖8所示。

圖7 網(wǎng)絡(luò)覆蓋率指標隨移動次數(shù)變化趨勢圖

圖8 網(wǎng)絡(luò)連通度指標隨移動次數(shù)變化圖

從圖7、圖8中可以發(fā)現(xiàn):相較于其他兩種虛擬力算法,DVFA移動策略可以獲得更大的網(wǎng)絡(luò)覆蓋率(穩(wěn)定在97%以上)。采用DVFA提升仿真效果主要有以下兩點因素:①閾值設(shè)定方式;②虛擬力構(gòu)造形式。這也是區(qū)別VFA和TVFA的主要不同所在。相比不同的閾值設(shè)定方式,非線性加權(quán)構(gòu)造虛擬力模型使得仿真效果提升更加明顯。DVFA所帶來的節(jié)點連通性也更加穩(wěn)定,連通度85%以上。

圖9 網(wǎng)絡(luò)覆蓋率指標隨節(jié)點數(shù)量變化趨勢圖

對于部署不同節(jié)點數(shù)量,分析獲得的網(wǎng)絡(luò)覆蓋率與節(jié)點連通性變化趨勢如圖9、圖10所示。從圖9、圖10中可以發(fā)現(xiàn):相較于其他兩種虛擬力算法,DVFA帶來的網(wǎng)絡(luò)性能提升優(yōu)勢較為明顯。隨著節(jié)點數(shù)量增長,網(wǎng)絡(luò)覆蓋率與節(jié)點連通度都將明顯提高。在各節(jié)點數(shù)量,DVFA帶來的網(wǎng)絡(luò)覆蓋率與網(wǎng)絡(luò)連通度都高于VFA與TVFA。當(dāng)在網(wǎng)絡(luò)中部署100個節(jié)點時,可以實現(xiàn)網(wǎng)絡(luò)覆蓋率與節(jié)點連通度兩項指標同時逼近100%。

圖10 網(wǎng)絡(luò)連通度指標隨節(jié)點數(shù)量變化趨勢圖

對于為節(jié)點配置不同的覆蓋半徑,分析獲得的網(wǎng)絡(luò)覆蓋率與節(jié)點連通性變化趨勢如圖11、圖12所示。從圖11、圖12中可以發(fā)現(xiàn):相較于其他兩種虛擬力算法,DVFA帶來的網(wǎng)絡(luò)性能提升優(yōu)勢較為明顯。隨著覆蓋半徑增加,網(wǎng)絡(luò)覆蓋率與節(jié)點連通度都將明顯提高。當(dāng)覆蓋半徑增加時,網(wǎng)絡(luò)覆蓋率的指標差異性變小。

圖11 網(wǎng)絡(luò)覆蓋率指標隨覆蓋半徑變化趨勢圖

圖12 網(wǎng)絡(luò)連通度指標隨覆蓋半徑變化趨勢圖

假設(shè)每個節(jié)點的初始能量為10 J。在信息傳輸采取最小跳數(shù)路由協(xié)議,且傳輸過程節(jié)點位置不發(fā)生移動。信息業(yè)務(wù)的源節(jié)點與目的節(jié)點隨機產(chǎn)生,服從均勻分布,數(shù)值仿真800次業(yè)務(wù)傳輸。定義網(wǎng)絡(luò)節(jié)點中能量最低的節(jié)點為瓶頸節(jié)點。由于節(jié)點能量時刻發(fā)生變化,瓶頸節(jié)點的標號也隨時間發(fā)生變化。節(jié)點瓶頸能量變化隨時間變化如圖13所示,網(wǎng)絡(luò)中生存節(jié)點數(shù)量隨時間變化如圖14所示。

圖13 瓶頸節(jié)點隨傳輸輪數(shù)變化趨勢圖

圖14 生存節(jié)點數(shù)量隨傳輸輪數(shù)變化趨勢圖

從圖13、圖14中可以發(fā)現(xiàn):相較于其他兩種虛擬力算法,DVFA可以有效降低瓶頸節(jié)點的能量消耗,保持網(wǎng)絡(luò)中足夠多的生存節(jié)點數(shù)量,延長網(wǎng)絡(luò)生存時間。這是由于DVFA構(gòu)造過程中考慮了“能量虛擬力”,降低低能耗節(jié)點作為中間節(jié)點轉(zhuǎn)發(fā)信息的概率,避免節(jié)點過早地因為能量耗盡而退出網(wǎng)絡(luò),使得網(wǎng)絡(luò)中節(jié)點能耗盡可能均衡。

4 結(jié)論

本文考慮能量與距離雙重因素,提出一種基于雙重虛擬力算法的節(jié)點移動策略。在節(jié)點移動時計算其鄰居節(jié)點的距離與鄰居節(jié)點的剩余能量,以非線性的方式構(gòu)建“距離虛擬力”與“能量虛擬力”。通過將兩種不同屬性的虛擬力進行融合,確定節(jié)點移動的方向與速率。數(shù)值仿真顯示,本文提出的策略可以提高網(wǎng)絡(luò)覆蓋率與節(jié)點連通性,并提高網(wǎng)絡(luò)的生存時間。真實環(huán)境中,可能還需考慮的其他指標都可以加乘在虛擬力公式中,從而構(gòu)成多重虛擬力移動模型。本文中提出的虛擬力模型具有較好的推廣性。