基于Grover路由策略的無線傳感網絡剩余容量構造與研究*

周 凱,孟利民*,華驚宇

(1.浙江工業大學,信息工程學院,杭州 310023;2.浙江省通信網技術應用研究重點實驗室,杭州 310023)

?

基于Grover路由策略的無線傳感網絡剩余容量構造與研究*

周 凱1,2,孟利民1,2*,華驚宇1,2

(1.浙江工業大學,信息工程學院,杭州 310023;2.浙江省通信網技術應用研究重點實驗室,杭州 310023)

網絡容量計算問題是無線網絡研究的熱點領域之一,也是構建網絡的重要評價指標。在前人的基礎上,本文認為網絡能耗和路由均衡技術是網絡容量計算過程中兩個重要因素,定義網絡生存時間內所能傳輸的信息總量為網絡總容量,網絡剩余能量是隨時間而變化的函數。首先,本文介紹信息傳輸信噪比和網絡生存時間的數學模型;然后,建立整數規劃數學模型,給出網絡傳輸總容量和剩余容量的數學表達式;最后,仿真對比基于能量均衡的Grover路由策略和AODV路由策略下,網絡總容量和剩余容量的變化情況。得到結論:節點移動性和能量均衡路由策略有助于提高網絡總容量。

剩余容量;網絡生存時間;能耗均衡;路由策略

由大量傳感器節點以多跳自組織方式構成的無線傳感網絡俱有組網靈活、不受有線設備約束等優勢,被廣泛應用于緊急搜救、軍事演習和醫療救治等實際應用中,已經引起產業界的高度重視,并逐漸發展成為21世紀最有前景的技術[1]。其中,如何計算無線傳感網絡整體信道特性和傳輸協議下所能夠支持的最大信息流,便是無線網絡容量問題,屬于無線網絡研究和設計的熱點領域[2]。由于無線傳感網絡的特殊性(拓撲結構多變、多路徑衰落效應等)使得網絡吞吐量遠小于有線網絡,并不能直接應用香農公式計算無線傳感網絡容量。因此,針對無線傳感網絡的特點,設計算法計算網絡容量并采取措施提高網絡容量成為一個非常關鍵的課題。

1 相關研究

近年來,國內外學者針對無線網絡容量進行了廣泛地研究,主要體現在以下3個方面。

針對不同的應用環境,學者們提出了各種不同關于無線網絡容量的定義。如文獻[3]中作者定義了網絡運輸容量,即網絡傳輸的所有信息量和傳輸距離乘積之和;文獻[4]中作者定義了網絡吞吐容量,即指單位時間內從源節點傳送到目的節點的信息比特數;文獻[5]中作者定義了網絡傳輸容量,即網絡中最大節點密度與成功傳輸的比特速率的乘積。這3種容量定義各具不同的物理含義。其中,Gupta和Kumar提出的傳輸容量被認定為無線網絡容量研究的里程碑。

在無線網絡容量定義的理論建立之后,學者們開始研究如何有效地計算網絡容量。如文獻[6]中基于鏈路信噪比的信息傳輸方式,作者提出通過建立混合整數規劃模型來解決網絡傳輸容量計算問題,并指出信息傳輸策略和路由協議都會對容量產生較大的影響。文獻[7]中基于信息流分布模型,作者研究了多信道無線網絡容量計算問題。在給定網絡拓撲結構和信息流分布后,通過建立線性規劃模型計算網絡容量,并提出信息流優化分布方案可以提高無線網絡的容量。由于無線網絡拓撲結構的時變特性,學者們還探討了隨機網絡容量上界和下界問題。如文獻[8]中Gupta等人在協議模型和節點隨機分布的情況下,利用地理幾何的分析方法,得到網絡每節點的吞吐容量為O[W/(nlog2n)1/3]bit/s。文獻[9]中作者以隨機點過程分析為基礎,對跳頻Ad Hoc網絡的信息傳輸能力進行分析,推導了無線容量的上界和下界,討論了可用頻率數對網絡容量的影響。文獻[10]中作者討論了由基站和Ad Hoc節點組成的異構網絡容量上下界問題,推導得到網絡容量界為O[log(n)]。其中,n表示網路中節點數量,W表示網絡帶寬。

在上述的研究中,無線網絡容量的計算過程僅與鏈路信噪比有關,具有一定的局限性,且他們都沒有明確地指出網絡容量與網絡生存時間之間的關系,而且認為網絡容量是一個常量。但是,當網絡能量耗盡殆盡時,網絡信息也無法正常傳輸,網絡容量也失去了原有的意義。作為創新點,本文中提出了網絡傳輸總容量和網路剩余容量兩個概念。網絡傳輸總容量是受到網絡生存時間約束的最優化模型,網絡剩余容量是一個時變的函數,描述可用容量在傳輸進程中的消耗情況。對于網絡信息傳輸而言,研究網絡剩余容量具有非常重要的意義,它可以有效地指導信息傳輸。

2 網絡傳輸總容量和剩余容量的數學模型

本文將網絡生存時間內所能傳輸的信息總量定義為網絡傳輸總容量,將某時刻網絡的可用容量定義為網絡剩余容量,剩余容量是一個時變函數。本文假設每次源節點與目的節點之間只發送1bit的數據信息;且在信息傳送過程中,節點不發生移動。在一個S×S的矩形網絡中隨機散布著N個節點。以0-1矩陣Y(t)=(yij(t))N×N表示t時刻網絡信息傳輸狀況。元素yij(t)的含義如下:

因此,生存時間T內所能傳輸的信息總量即網絡傳輸總容量C計算方式表達如下:

(1)

將網絡中第1個節點因能量消耗殆盡退出網絡的時間定義為無線網絡生存時間。引入網絡一階能耗模型[15],網絡中節點發送信息耗能包括發射電路耗能和放大電路耗能兩個部分;節點接收信息耗能僅考慮接收電路耗能。以Ek(t)表示節點k在t的剩余能量,生存時間T可以由以下優化模型得到:

(2)

時刻t源節點s到目的節點d之間正常通信,即ysd(t)=1需要滿足以下兩個條件:

①信息發送過程是從源節點s到目的節點d形成的一條通路。為了描述這一約束,引入0-1變量xij(t):

xij(t)=

(3)

(4)

其中,χ表示發送節點和接收節點間正常通信時所需的信噪比閾值,η表示網絡中的環境噪聲功率。如果僅考慮大尺度路徑損耗[17],信道增益可以表示如下:

γij(t)=‖Xi(t)-Xj(t)‖-μ

(5)

其中,2≤μ≤4,Xi(t)和Xj(t)分別表示t時刻發送節點和接收節點的位置坐標。

綜上所述,可以得到無線傳感網絡總容量的整數規劃模型。其中,式(1)是模型的優化目標,式(3)、(4)是模型的約束條件。無線網絡剩余容量Rc(t)是衡量當前時刻網絡有效容量的重要指標,可以通過如下式(6)計算得到。可見,網絡總容量一個優化常量,而剩余容量是一個時變函數。

(6)

3 基于Grover算法的能量感知路由策略

上述的整數規劃模型中,關于通路的約束方程組(3)與具體路由協議無關,是任何路由協議必須滿足的基本要求。但在不同路由協議下,通過最優化模型計算得到的網絡傳輸總容量各不相同。因此,只有在給定網絡節點分布和路由策略后,才能夠通過整數規劃模型計算網絡傳輸總容量以及網絡中的剩余容量。

文獻[17]指出能量均衡算法和能量感知路由協議有助于提高網絡容量。為了印證這一點,本文提出基于Grover算法的能量感知路由策略,并計算在此策略下網絡傳輸總容量和剩余容量。2009年,學者提出可以采用Grover量子搜索的方式實現在無線自組織網絡中的QoS路由信息傳輸,并在文中詳細介紹了Grover算法的操作矩陣和擴散矩陣構造方法[18]。在文獻[18]的基礎上,本文將介紹能量感知路由策略中Grover操作矩陣和擴散矩陣的構造方式。

首先介紹操作矩陣U的構造方式,每個節點i都維護著一個操作矩陣U=(uimn)N×N。

(7)

擴散矩陣的作用在于放大正確的解徑[19],在Grover搜索過程中擴散矩陣恒定不變,構造方式如下:

(8)

在Grover搜索過程中,每個節點初始化振幅都相等,表達如下:

(9)

在第k跳鏈路選擇時,網絡節點的振幅為Γk;在第k+1跳鏈路選擇時,網絡節點的振幅為Γk+1。它們之間的迭代計算公式如下:

(10)

綜上所述,基于Grover算法的路由均衡策略可以簡單地描述如下:

Step 1:源節點s發起向目的節點d的路由建立請求信息。

Step 3:中間節點i收到來自上一節點的路由建立請求信息后,搜索其一跳通信范圍的節點。如果中間節點i一跳范圍內沒有節點,則通信失敗,轉到Step 5;否則,按照式(7)、式(8)構造操作矩陣和擴散矩陣。然后通過式(9),迭代計算得到中間節點i一跳通信范圍內,且信噪比大于閾值的節點被選擇概率。

Step 4:按照概率從高到低,選擇前50%的節點作為信息轉發的中間節點。轉到Step 3。

Step 5:通信失敗。

Step 6:路由建立請求發送成功,建立路由進行信息傳輸。

為了印證能量感知的路由策略對于網絡傳輸總容量和剩余容量的影響,本文選取AODV路由策略進行對比。AODV是無線網絡中較早提出的一類路由策略,是一種源驅動路由協議。當一個節點需要給網絡中的其他節點傳送信息時,如果沒有到達目標節點的路由,則必須先以多播的形式發出路由請求報文。路由請求報文中記錄著發起節點和目標節點的網絡層地址,鄰近節點收到路由請求報文,首先判斷目標節點是否為自己。如果是,則向發起節點發送路由回應;如果不是,則首先在路由表中查找是否有到達目標節點的路由,如果有,則向源節點單播路由回應,否則繼續轉發路由請求報文進行查找。

圖1 兩種策略下網絡傳輸總量的變化圖

4 數值仿真

為了驗證算法的性能,本文采用MATLAB軟件進行仿真分析。在一個300 m×300 m的矩形網絡中,隨機散布若干個節點,節點位置服從均勻分布。假設網路中每個節點的通信范圍為50 m;信道信噪比閾值χ=1.3,信道衰落因子μ=2,噪聲功率。

由于不同的路由策略,網絡中節點能耗變化不同,造成網絡生存時間不同,網絡傳輸總量也會不同。本文對比了AODV路由策略與基于Grover算法的能量感知路由策略在網絡傳輸總容量上的表現,如圖1所示。在一個30個節點組成的無線網絡中,兩種路由策略在網絡剩余容量上的表現,如圖2所示。

圖2 兩種策略下網路剩余容量變化仿真圖

從圖1中可以發現:網絡路由策略會影響網絡傳輸總量,本文提出的基于Grover算法的能量感知路由策略比AODV路由策略更加有利于提高傳輸總量。從圖2中可以發現:網絡剩余容量隨時間的變化而變化,是一個動態時變函數,而且隨著網絡能耗增加逐漸趨向于零。得到能量感知路由策略有助于提高網絡動態容量的結論。

圖4 兩種網絡下剩余容量的變化仿真圖

網絡節點移動可以改變網絡拓撲結構,對鏈路信噪比造成影響。節點的移動性可以改變網絡傳輸總容量和剩余容量。本節仿真移動性網絡與非移動網絡在傳輸總容量方面的表現。

在移動性網絡中,本文定義網絡中的每個節點速度隨機分布在[0,2 m/s]的區間內,干擾節點移動方向朝遠離發送節點的方向移動,遇到邊界時便反向移動,采用基于Grover能量感知的路由策略傳輸信息,得到仿真結果如圖3、圖4所示。從圖中可以發現:節點的移動性可以有效地提高網絡傳輸總容量。

圖3 兩種網絡下傳輸總容量的變化仿真圖

5 結束語

本文在前人的基礎上,將網絡生存時間內所能傳輸的信息總量定義為網絡傳輸總容量,將某時刻網絡的可用容量定義為網絡剩余容量,剩余容量是一個時變函數。通過建立整數規劃數學模型,得到網絡傳輸總容量和剩余容量的數學表達式。最后,本文進一步提出基于Grover算法的能量感知路由策略,通過仿真分析能量感知路由策略和節點的移動性可以提高網絡傳輸總容量與網絡剩余容量。

[1] 劉志,裘正定.基于分環多跳的無線傳感網分簇路由算法[J].通信學報,2008,29(3):104-113.

[2]楊娟,李穎,張志軍,等.移動Ad hoc網絡容量非合作規劃博弈模型的穩定性[J].電子與信息學報,2012,34(1):75-81.

[3]Renato M,de Moraes,Hamid R,et al.Garcia-Luna-Aceves.Mobility-Capacity-Delay Trade-Off in Wireless Ad Hoc Networks[J].Ad Hoc Networks,2006,4(5):607-620.

[4]Jae Young Seol,Seong Lyun Kim.Node Mobility and Capacity in Wireless Controllable Ad Hoc Networks[J].Computer Communications,2012,35(11):1345-1354.

[5]Gupta P,Kumar E R.The Capacity of Wireless Networks[J].IEEE Transactions on Information Theory,2000,46(2):388-404.

[6]Vishwanath Ramamurthi,Abu(Sayeem)Reaz,Dipak Ghosal,et al.Channel,Capacity,and Flow Assignment in Wireless Mesh Networks[J].Computer Networks,2011,55(9):2241-2258.

[7]劉永靖.多跳無線網絡容量與資源優化技術研究[D].電子科技大學,2011.

[8]涂來,王芙蓉,張劍,等.基于多跳蜂窩網的合群網絡模型網絡容量效能分析[J].通信學報,2008,29(2):45-51.

[9]Liu Min,Xu Shijun,Sun Siyi.An Agent-Assisted QoS-Based Routing Algorithm for Wireless Sensor Networks[J].Journal of Network and Computer Applications,2012,35(1):29-36.

[10]Song Guo,Oliver Yang.QoS-Aware Minimum Energy Multicast Tree Construction in Wireless Ad Hoc Networks[J].Ad Hoc Networks,2004,2(3):217-229.

[11]Meng Limin,Zhou Kai,Shen Xinyu,et al.Research on Qos Routing Protocol Based on Grover Algorithm for MANET[C]//Proceedings of the IASTED International Conference on Computational Intelligence,2009:138-142.

[12]楊汝濤,張紹謙,竇萬春.一種基于QoS剪枝的Top-k自動服務組合方法[J].電子學報,2012,40(7):1489-1491.

[13]郝曉辰,竇晶晶,劉彬.基于路徑損耗的無線傳感器網絡分布式拓撲控制算法[J].軟件學報,2009,20(12):3213-3222.

[14]姜向遠,張煥水,王偉.一種基于非完全數據的路徑損耗模型選擇算法[J].電子與信息學報,2012,34(6):1438-1344.

[15]Zhu Junhua,Hung Ka-Lok,Brahim Bensaou,et al.Rate-Lifetime Tradeoff for Reliable Communication in Wireless Sensor Networks[J].Computer Networks.2008,52(1):25-43.

[16]王維,楊明,羅軍舟,等.多射頻無線Mesh網絡組播端到端時延建模與優化[J].計算機學報,2012,35(7):1358-1369.

[17]李輝,張安,徐琦,等.多徑衰落信道中的一種定想多用戶檢測算法[J].傳感技術學報,2006,19(1):238-240.

[18]孟利民,周凱,沈鑫宇,等.基于Grover搜索思想的無線自組網絡路由算法研究[J].傳感技術學報,2010,23(2):251-255.

[19]Geetha V,Kallapur P V,Sushma Tellajeera.Clustering in Wireless Sensor Networks:Performance Comparison of LEACH and LEACH-C Protocols Using NS2[J].Procedia Technology,2012,4:163-170.

Residual Capacity Algorithm of Wireless Sensor Network Using Grover Routing Strategy*

ZHOUKai1,2,MENGLimin1,2*,HUAJingyu1,2

(1.College of Information Engineering,Zhejiang University of Technology,Hangzhou 310032,China;2.Zhejiang Provincial Key Laboratory of Communication Networks and Application,Hangzhou 310023,China)

Capacity estimation is the hotspot in the research of wireless sensor networks.This paper investigates capacity algorithms based on the physics SINR model by using the integer linear programming to formulate the routing problem.This paper proposes the residual capacity algorithm and total traffic algorithm based on the lifetime of network.The numerical results show the capacity will be improved with the increase of the nodes in networks and the dynamic capacity is a time-varied function which will decrease with time.Finally,this paper points out that routing strategies and mobility will improve the capacity.

residual capacity of networks;lifetime of network;energy model;routing protocol

周 凱(1985-),講師,博士研究生,就讀于浙江工業大學信息工程學院,主要研究方向:無線網網絡建模、無線網絡容量計算、無線網絡路由設計;

孟利民(1963-),教授,博士生導師,信息與通信工程專業工學博士,浙江工業大學信息與通信系統研究所所長,浙江省光纖通信技術重點實驗室主任。主要研究方向:多媒體數字通信、無線通信與網絡、通信信號處理與軟件無線電、IP核設計,mlm@zjut.edu.cn。

項目來源:國家自然科學基金項目資助(61372087)

2014-08-02 修改日期:2014-11-24

C:7230

10.3969/j.issn.1004-1699.2015.02.018

TP393

A

1004-1699(2015)02-0249-05