基于雙重虛擬力算法的移動自組織網絡節點移動策略研究*

趙克華,劉半藤

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

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

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

1 節點模型

1.1 節點移動模型

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

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

1.2 節點連通性模型

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

圖1 節點連通半徑和覆蓋半徑示意圖

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

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

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

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

1.3 網絡覆蓋率模型

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

圖2 MANET離散示意圖

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

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

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

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

1.4 節點能耗模型

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

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

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

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

2 雙重虛擬力移動模型

2.1 雙重虛擬力的基本思想

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

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

圖4 距離閾值示意圖

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

圖5 能量閾值示意圖

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

2.2 雙重虛擬力的參數設定

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

圖6 距離閾值計算示意圖

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

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

3 數值仿真

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

圖7 網絡覆蓋率指標隨移動次數變化趨勢圖

圖8 網絡連通度指標隨移動次數變化圖

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

圖9 網絡覆蓋率指標隨節點數量變化趨勢圖

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

圖10 網絡連通度指標隨節點數量變化趨勢圖

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

圖11 網絡覆蓋率指標隨覆蓋半徑變化趨勢圖

圖12 網絡連通度指標隨覆蓋半徑變化趨勢圖

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

圖13 瓶頸節點隨傳輸輪數變化趨勢圖

圖14 生存節點數量隨傳輸輪數變化趨勢圖

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

4 結論

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