基于能量粒子算法的無線自組織網絡節點移動策略研究*

劉半藤

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

無線自組織網絡MANETs(Mobile Ad Hoc Networks)是由若干可以自由移動節點組成的高度自治系統。由于部署MANETs無需依靠已有的通信設備,具有較強的抗毀性與適用性,被廣泛地應用于抗震救災、野外探測等各種環境,被視為21世紀信息技術的重要產業支柱之一[1]。受限的節點能量與動態變化的拓撲結構是MANETs區別于傳統網絡的重要特征。由于MANETs節點大多分布于野外環境中,需要依靠電池供電且長時間內無法充電。網絡能耗已經成為限制MANETs發展的重要因素,也成為國內外專家學者研究的熱點領域[2]。節點的移動使得網絡拓撲結構實時變化,網絡能量優化計算變得更為困難。因此,研究一種節點移動策略改善網絡能耗狀況是一項非常有意義的工作。

目前,MANETs節點移動策略對于網絡性能的影響主要表現在以下幾個方面[3-10]:時間同步問題、網絡連通性問題、網絡能耗問題、網絡覆蓋率問題。王慧強等人[3]針對水下傳感器網絡移動性對時間同步參數計算帶來的困難,提出一種通信量小、精度高的時間同步算法。劉宴濤等人[4]分別建立隨機點移動策略、隨機方向移動策略、隨機游走移動策略分析MANETs連通性狀況,證明隨機游走移動策略使得網絡具有較高連通性。與此同時,王珊珊等人[5]改進傳統的隨機游走移動策略,并在仿真平臺NS3實現一種以圓形為邊界的隨機游走移動模型,以提高網絡連通性。吳聰等人[6]在經典隨機點移動策略基礎上,建立能量均衡的線性規劃數學模型,說明節點移動性有助于提升MANETs能耗均衡性。無獨有偶,Pala等人[7]利用節點移動特性,建立線性規劃模型對無線傳感網絡的能量均衡指標進行優化。王珊等人[8]建立節點移動模型,提出一種修復網絡覆蓋空洞的聯合補丁法,從而實現降低網絡節點冗余度和提高網絡覆蓋率的目的。Wang等人[9]針對無線傳感網絡覆蓋問題,指出在網絡中部署少量移動節點有助于提高網絡覆蓋性能,并在三種典型應用場景進行仿真分析。Liu等人[10]從二維平面入手,考慮一般凸三維曲面的覆蓋率,并以此作為傳感器節點移動特征參數,及時填補覆蓋空洞。在上述幾方面中,節點移動對于網絡覆蓋性與能耗均衡兩方面的研究更加重要。如何通過節點移動性,提升網絡整體覆蓋性以及改善能耗指標是衡量移動策略的重要指標。由于網絡節點移動性使得網絡能耗優化模型計算變得更為復雜。目前,MANETs節點移動策略主要有以下幾種方式:虛擬力算法VFA(Virtual Force Algorithm)、粒子群算法PSO(Particle Swarm Optimization)。李明等人[11]結合傳統虛擬力算法和差分算法,提出一種異構無線傳感網絡的節點移動策略,提升網絡覆蓋性能,且計算效率較高。李娟等人[12]以路由算法為基礎,建立包含障礙物模型、速度初始化函數、無邊界仿真區域的粒子群算法,并進行數值仿真以此說明算法的有效性。傳統的粒子群算法在計算迭代過程中每個粒子都要實時獲得全局最優的粒子位置,利用全局最優位置和局部最優位置信息指導粒子移動。這一點在MANET節點移動過程中較難實現。如果MANETs節點實時獲知網絡所有粒子的位置,需要進行集中式控制,所花費代價也較大。因此,較多傳統的粒子群算法較難直接應用于MANETs。

為此,本文提出一種基于能量粒子的節點移動策略EPSO(Energy Particle Swarm Optimization)。EPSO將網絡中的節點類比為粒子,每個節點都可以獲得本地節點能量的局部最優信息和鄰居節點的局部最優信息。通過將鄰居節點的局部最優信息看作全局較優解,從而制定策略指導節點進行移動,提升網絡能耗性能。

1 粒子模型

1.1 網絡連通率計算方法

由N個移動節點構成的MANET可視為N個粒子散布在網絡中(下文將網絡中的節點稱為粒子),并對粒子進行標號為i=1,2,…,N。在時刻t,標號為i的粒子位置可以表示為向量Pi(t)={pxi(t),pyi(t)}。每個粒子都具備相同的通信半徑Rcom和感知半徑Rcov。粒子可以與通信半徑內的其他粒子進行信息交互。在時刻t,MANET連通矩陣C(t)=(cij(t))N×N的計算方式如下所示:

如果cij(t)=1,說明該時刻兩個粒子間的距離小于通信半徑。此時,該兩個粒子可以直接進行信息交互。由于MANET的多跳傳輸特性,在連通矩陣C(t)的基礎上,經過多跳傳輸后粒子間連通狀況矩陣MC(t)=[mcij(t)]N×N的計算方式如下所示:

如果mcij(t)=1,說明該時刻兩個粒子可以通過多跳傳輸進行信息交互。在時刻t,網絡連通率指標L(t)的計算方式如下所示:

該指標衡量可以統計某時刻可以實現兩兩信息交互的粒子對總數所占網絡粒子對總數的百分比。一種較好的移動策略可以有效保障粒子之間的連通特性。

1.2 網絡覆蓋率計算方法

將原有的MANET進行網格化劃分,離散成M個獨立的特征點,并對這些特征點進行標號為i=1,2,…,M。標號為i的特征點位置可以表示為向量Pti(t)={xi(t),yi(t)}。在時刻t,粒子對于特征點的覆蓋狀況矩陣G(t)=[gij(t)]N×M的計算方式如下所示:

如果gij(t)=1,說明該時刻標號為i的粒子可以感知標號為j的特征點。對于某個特征點而言,若存在一個粒子可以感知該特征點則可認為該特征點被覆蓋。定義網絡粒子i的冗余度yi(t)為該節點感知范圍內的特征點被覆蓋的平均粒子數,計算方式如下:

對于某個特征點而言,若存在一個粒子可以感知該特征點則可認為該特征點被覆蓋。在時刻t,特征點被覆蓋的狀況矩陣TG(t)=[tgj(t)]1×M的計算方式如下所示:

利用特征點被感知的數量占特征點總數近似計算網絡覆蓋率F(t)計算方式如下:

1.3 網絡能耗計算方法

假設MANET粒子能量消耗方式服從一階能耗模型[13],結構如圖1所示。

圖1 一階能量消耗模型

粒子發送數據包消耗能量包括發射電路耗能、放大電路耗能兩部分,粒子接收數據只有接收電路消耗能量,計算方式如下:

式中:ETx表示發送能量消耗,ERx表示接收能量消耗,Eelec表示發射電路和接收電路的能耗,l表示發送數據包的比特數,d表示發送粒子與目的粒子之間的傳輸距離,εfs是模型常數。

2 能量粒子移動策略

2.1 粒子能量維全局較優解與局部最優解計算方法

圖2 粒子能量維局部最優解與全局較優解搜索圖

圖3 粒子能量信息搜索舉例

由于MANET網絡多跳傳輸特性,粒子將承擔轉發任務。因此,粒子將努力向剩余能量較高的鄰居粒子移動,從而降低剩余能量較低的粒子作為中間粒子轉發信息的概率,實現提高網絡生存時間的目的。

2.2 粒子覆蓋維全局較優解與局部最優解計算方法

圖4 粒子覆蓋維局部最優解與全局較優解搜索圖

2.3 粒子移動策略

通過上式可以發現:t時刻第i個節點根據自身的位置坐標Pi(t)確定需要改變的移動速度fi(t+Δt),從而確定下一時刻的節點位置Pi(t+Δt)。其中,c1與c2被稱為學習因子或者加速度常數;r1與r2是屬于[0,1]范圍內服從均勻分布的隨機數;ω被稱為慣性權重。

這就是本文提出的能量粒子移動策略EPSO,改善傳統PSO算法所要求的全局最優粒子位置無法獲得的困境。本文僅考慮從能量角度對經典的PSO算法進行改進,如果要考慮多個因素時也可構建多維PSO算法求解節點移動多目標優化解。因此,本文的算法具有較好的擴展性。

3 仿真分析

為了驗證該能量粒子移動策略的性能,本節采用MATLAB2018b構建一個300 m×300 m矩形MANET仿真環境。初始時刻,網絡中隨機散布著50個移動節點,每個節點的覆蓋半徑為50 m,通信半徑為60 m。節點進行業務傳輸時首先選擇剩余能量較高的節點作為中間節點轉發信息。

假設網絡初始時刻每個節點的初始能量為10 J。設移動策略參數為c1=c2=2,ω=1。對比僅用局部最優信息的粒子群移動策略(PSO)和傳統的虛擬力移動策略(VFA),三種移動策略下網絡覆蓋率指標變化曲線如圖5所示,三種移動策略下網絡連通率指標變化曲線如圖6所示。

圖5 三種策略下網絡覆蓋率指標變化趨勢圖

圖6 三種策略下網絡連通率指標變化趨勢圖

通過圖5、圖6可以發現:網絡節點的移動特性可以有效地提高網絡覆蓋率指標,且本文提出的EPSO策略覆蓋率高于僅用局部最優信息的PSO策略和傳統的虛擬力移動策略(VFA)。但是,三種移動策略均使得網絡連通性指標提交較為緩慢。這是由于在移動過程中對于連通度指標考慮不足所造成。

定義MANET中剩余能量最低的節點為瓶頸節點。三種移動策略下網絡瓶頸節點能量變化曲線如圖7所示,三種移動策略下網絡剩余節點數量如圖8所示。

圖7 三種策略網絡瓶頸節點能量變化趨勢圖

圖8 三種策略網絡生存節點數變化趨勢圖

通過圖7、圖8可以發現:EPSO移動策略下,網絡的瓶頸節點隨時間發生著變化,且瓶頸節點的能量隨時間下降的速度較僅考慮局部信息的粒子群算法移動策略與傳統虛擬力移動策略更為緩慢,可以延長網絡生存時間。

4 結束語

本文在分析網絡節點能量消耗模型的基礎上,借鑒粒子群的移動方式,提出了一種能量粒子群算法的無線自組織網絡節點移動策略。EPSO將網絡中的節點類比為粒子,每個節點都可以獲得本地節點能量的局部最優信息和鄰居節點的局部最優信息。通過將鄰居節點的局部最優信息看作全局較優解,從而制定策略指導節點進行移動,提升網絡能耗性能。