楊 冰 ，鄧曙光 ，文雙春

(1.湖南大學(xué) 信息科學(xué)與工程學(xué)院,湖南 長沙 410082;2.湖南城市學(xué)院 通信與電子工程學(xué)院，湖南 益陽 413000)

無線多媒體傳感器網(wǎng)絡(luò)能量均衡的QoS路由算法*

楊 冰1,2，鄧曙光2，文雙春1

(1.湖南大學(xué) 信息科學(xué)與工程學(xué)院,湖南 長沙 410082;2.湖南城市學(xué)院 通信與電子工程學(xué)院，湖南 益陽 413000)

為保障能量受限的無線多媒體傳感器網(wǎng)絡(luò)(WMSNs)多服務(wù)質(zhì)量(QoS)需求，提出了一種能量均衡的QoS路由 (EBQR) 算法。該算法通過蟻群優(yōu)化將網(wǎng)絡(luò)帶寬、時延、丟包率和能量等因素作為目標(biāo)函數(shù)，并根據(jù)函數(shù)值大小動態(tài)調(diào)整蟻群信息素的揮發(fā)系數(shù)和濃度增量，提供網(wǎng)絡(luò)業(yè)務(wù)中滿足不同QoS需求的最優(yōu)路徑。仿真結(jié)果表明：與AntWMSNs算法和ASAR算法相比，EBQR算法平均端到端時延降低了16 %，丟包率減少22 %，生命周期延長了近50 %，有效實現(xiàn)了網(wǎng)絡(luò)中節(jié)點能耗的均衡性。

無線多媒體傳感器網(wǎng)絡(luò)； 能量均衡； 服務(wù)質(zhì)量路由； 蟻群算法

0 引 言

隨著傳感器技術(shù)和無線通信技術(shù)的不斷發(fā)展，無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)以其自組織、低成本等特點被廣泛應(yīng)用于社會各種活動中[1，2]。監(jiān)測環(huán)境日趨復(fù)雜多變，對監(jiān)測數(shù)據(jù)的要求越來越高,為了實現(xiàn)細(xì)粒度、精準(zhǔn)信息的監(jiān)測，人們將具有音頻、視頻、圖像等多媒體信息感知功能的新型傳感器節(jié)點引入到傳感器網(wǎng)絡(luò)中[3，4]，由此催生了無線多媒體傳感器網(wǎng)絡(luò)(wireless multimedia sensor networks,WMSNs)。網(wǎng)絡(luò)服務(wù)質(zhì)量(quality of service,QoS)是網(wǎng)絡(luò)提供給應(yīng)用或用戶服務(wù)性能的一種測量[5]。傳統(tǒng)的QoS路由算法不能直接適用于WMSNs，因為它具有能量等資源有限和對QoS的要求比較高等特點。WMSNs的QoS要求，包括可用性、吞吐量、時延、時延抖動、丟包率、能耗等參數(shù)[6，7]。

針對WMSNs的特點，國內(nèi)外對QoS路由問題開展了大量研究[8～10],這些研究主要集中在實時性、可靠性或能量約束等方面。例如:文獻(xiàn)[8]提出了一種基于能量感知的可靠路由機(jī)制，充分考慮節(jié)點的剩余能量和路徑的可靠性，選擇相應(yīng)的路徑，從而提高可靠性和降低能耗；文獻(xiàn)[9]提出了一種保證實時性的路由協(xié)議，通過考慮轉(zhuǎn)播速率和剩余能量來降低平均時延和延長網(wǎng)絡(luò)生命周期；文獻(xiàn)[10]提出了角度區(qū)分服務(wù)的路由機(jī)制，根據(jù)實時和非實時數(shù)據(jù)進(jìn)行相應(yīng)處理，滿足其需求并有效均衡能量消耗。此外，也有一些針對多QoS約束條件路由問題的研究,例如:通過綜合考慮路徑的帶寬、時延、丟包率和能耗等方面之間的均衡問題，在滿足這些需求的同時盡量減少網(wǎng)絡(luò)能耗延長網(wǎng)絡(luò)生命周期[11～13]。從如上所述的研究來看，在能量消耗方面，存在某些關(guān)鍵節(jié)點被頻繁使用而過早死亡或為避開能量過低節(jié)點而導(dǎo)致總能耗增大等問題。文獻(xiàn)[14]利用能量因數(shù)有效解決了最小化路由通信所消耗總能量和最大化網(wǎng)絡(luò)生命周期的問題。本文基于能量因數(shù)這一思想，提出一種能量均衡的QoS路由(EBQR)算法，該算法既滿足網(wǎng)絡(luò)對帶寬、時延、丟包率、時延抖動、能耗的QoS需求，同時又能均衡網(wǎng)絡(luò)中節(jié)點的能耗，并有效降低數(shù)據(jù)傳輸?shù)目偰芎摹?/p>

1 WMSNs中EBQR模型

WMSNs可抽象為一個賦權(quán)圖G=(V,E)，其中，V為網(wǎng)絡(luò)的中節(jié)點集合，V={v1,v2,…,vn}，E為網(wǎng)絡(luò)中節(jié)點間通信的鏈路集，E={e1,e2,…,em}。對于任意鏈路e∈E，有e=(vi,vj)，vi∈V,vj∈V,i≠j。每條鏈路具有(bandwidth(eij)，delay(eij)，jitter(eij)，loss(eij))4個屬性的QoS特征值，分別表示節(jié)點vi到節(jié)點vj的帶寬、時延、時延抖動、丟包率。每個節(jié)點具有能量energy(vi)的特征。

QoS路由選擇是在圖G=(V,E)中尋找到一條從源節(jié)點到目的節(jié)點滿足QoS約束條件的路徑P=(vs,…,vd),約束關(guān)系如下：

1)條件1:帶寬約束

BP=min{bandwidth(eij)}≥Bmin,?vi,vj∈P,

(1)

式中Bmin為路徑上要求的最小帶寬。

2)條件2:時延約束

DP=∑delay(eij)≤Dmax, ?vi,vj∈P,

(2)

式中Dmax為路徑上要求的最大時延和。

3)條件3:時延抖動約束

JP=∑jitter(eij)≤Jmax,?vi,vj∈P,

(3)

式中Jmax為路徑上要求的最大時延抖動和。

4)條件4:時延抖動約束

LP=1-∏(1-loss(eij))≤Lmax,?vi,vj∈P,

(4)

式中Lmax為路徑上允許的最大丟包率。

5)條件5:能量約束

EnP=energy(vi)≥Enmin,?vi∈P,

(5)

式中Enmin為路徑上每個節(jié)點要求的最小能量。

6)條件6:目標(biāo)函數(shù)

(6)

式中α,β,γ,δ,φ分別為帶寬、時延、時延抖動、丟包率和能量的比重系數(shù)，α+β+γ+δ+φ=1，EF為能量因數(shù)

(7)

式中IE為節(jié)點的初始能量，M為量化級。

本文的目標(biāo)是在滿足條件1～條件5的情況下使得F值最小。

2 EBQR算法描述

蟻群算法[15～17]是一種模擬螞蟻群體覓食行為的仿生優(yōu)化算法，采用正反饋并行催化機(jī)制，具有較強(qiáng)的魯棒性、優(yōu)良的分布式計算機(jī)功能以及易于與其他啟發(fā)算法結(jié)合等優(yōu)點，在諸多領(lǐng)域已得到廣泛應(yīng)用。WMSNs中信息的動態(tài)性、隨機(jī)性、異步性等特點與蟻群算法中的螞蟻移動非常相似，因此，利用蟻群算法來解決WMSNs中的復(fù)雜問題具有重要意義。本文根據(jù)目標(biāo)函數(shù)值的大小動態(tài)調(diào)整信息素?fù)]發(fā)系數(shù)和信息素濃度增量，尋找滿足QoS約束條件的最佳路由。

WMSNs中的每個節(jié)點都執(zhí)行同樣的路由選擇算法，從源節(jié)點向目的節(jié)點周期性地發(fā)送螞蟻，并根據(jù)QoS需求找到滿足條件的路徑。

步驟1：初始化參數(shù)，產(chǎn)生前向螞蟻。

步驟2：當(dāng)前向螞蟻到達(dá)節(jié)點i時，先判斷該節(jié)點是中間節(jié)點還是目的節(jié)點，同時判斷是否滿足QoS約束指標(biāo)中的條件。若為中間節(jié)點且滿足QoS約束指標(biāo)，則按式(8)選擇轉(zhuǎn)移概率大的鄰居節(jié)點j作為螞蟻移動的下一個節(jié)點，重復(fù)步驟(2)

(8)

(9)

若為中間節(jié)點且不滿足QoS約束指標(biāo)，則執(zhí)行步驟(3)，若為目的節(jié)點，則執(zhí)行步驟(4)。

步驟3：停止轉(zhuǎn)發(fā)前向螞蟻，在節(jié)點i處產(chǎn)生一個后向螞蟻，按式(10)更新前向螞蟻所走過路徑上的信息素

τij(t+1)=(1-ρ1)τij(t).

(10)

重復(fù)執(zhí)行步驟(3)，直到到達(dá)源節(jié)點，執(zhí)行步驟(5)。

步驟4：當(dāng)前向螞蟻到達(dá)目的節(jié)點時，判斷是否滿足QoS約束指標(biāo)，并按式(6)計算目標(biāo)函數(shù)F，丟棄前向螞蟻并產(chǎn)生后向螞蟻，根據(jù)目標(biāo)函數(shù)值F的大小按式(11)或式(13)更新前向螞蟻所走路徑上的信息素濃度，直到到達(dá)源節(jié)點

τij(t+1)=(1-ρ0)τij(t)+Δτij(t),

(11)

Δτij(t)=Q1/F.

(12)

當(dāng)目標(biāo)函數(shù)F的最小值在連續(xù)n次的迭代過程中均無變化時

τij(t+1)=(1-ρ2)τij(t)+Δτij(t),

(13)

Δτij(t)+Q2/F.

(14)

步驟5：當(dāng)源節(jié)點收到返回的后向螞蟻，信息素被更新，同時丟棄該螞蟻。轉(zhuǎn)到步驟(2)反復(fù)執(zhí)行直到到達(dá)設(shè)定的迭代次數(shù)，算法終止，輸出目標(biāo)函數(shù)值最小的路徑。

3 仿真與分析

為驗證本文所提算法的有效性，建立仿真環(huán)境進(jìn)行驗證分析。假設(shè)在200 m×200 m的區(qū)域里隨機(jī)部署100個無線傳感器節(jié)點(包括Sink節(jié)點)，Sink的位置固定于(0,0)m，該節(jié)點的能量不受限制(在處理過程中忽略該點的能量消耗問題)。設(shè)定其他節(jié)點的初始能量為15 J，發(fā)送數(shù)據(jù)和接收數(shù)據(jù)能耗為50 nJ/bit，通信半徑為70 m，網(wǎng)絡(luò)帶寬為[1,10]Mbps之間的隨機(jī)數(shù)，鏈路之間的時延為[10,20] ms之間的隨機(jī)數(shù)，鏈路之間的丟包率為[0,0.045]之間的隨機(jī)數(shù)。同時假設(shè)QoS需求為Bmin=2 Mbps，Dmax=100 ms，Lmax=0.15，Enmin=0.2 J，取α=0.1，β=0.4，γ=0，δ=0.4，φ=0.1。

在上述環(huán)境下，對本文提出的EBQR算法和文獻(xiàn)[12,13]的算法進(jìn)行仿真，分別從平均傳輸時延、平均丟包率、平均能量消耗以及網(wǎng)絡(luò)生命周期4個方面進(jìn)行性能比較。其中，平均傳輸時延為不同測試時間段源節(jié)點傳送有效數(shù)據(jù)包到匯聚節(jié)點所用的平均時間。丟包率為源節(jié)點傳送有效數(shù)據(jù)包到匯聚節(jié)點丟失數(shù)據(jù)包的數(shù)量所占發(fā)送數(shù)據(jù)包的比率。平均能量消耗為每個測量時刻源節(jié)點發(fā)送一個有效數(shù)據(jù)包到匯聚節(jié)點所消耗能量的平均值。網(wǎng)絡(luò)生命周期為網(wǎng)絡(luò)中第一個節(jié)點能量消耗到小于最小能量時所用的時間。

經(jīng)仿真測試，平均傳輸時延、平均丟包率和平均能量消耗分別如圖1～圖3所示，3種算法的網(wǎng)絡(luò)生命周期比較如表1所示。與AntWMSNs算法和ASAR算法相比，由于EBQR算法的目標(biāo)函數(shù)中考慮了帶寬、時延、丟包率和能耗，在中間節(jié)點的轉(zhuǎn)移概率選擇時也考慮這些因素，并根據(jù)每次所得的目標(biāo)函數(shù)值產(chǎn)生不同的揮發(fā)系數(shù)；同時，通過選取具有較高能量節(jié)點為通信節(jié)點，并選取整體能耗較小的路徑為傳輸路徑。由此尋找到的路徑性能值更好，傳輸數(shù)據(jù)時延、丟包率和能耗小。而ASAR算法在目標(biāo)函數(shù)中雖考慮了帶寬、時延、丟包和能耗因素，但每個周期里所尋找的路徑很容易集中經(jīng)過某個節(jié)點，從而導(dǎo)致該節(jié)點能量快速消耗殆盡。AntWMSNs算法在路徑選擇時通過比較節(jié)點的剩余能量，選擇剩余能量較大的節(jié)點作為下跳節(jié)點，但目標(biāo)函數(shù)中丟包率和時延使用的是固定值，故尋找到的路徑時延和丟包率仍相對較大，測試結(jié)果證實了這點。由圖可知，EBQR算法的平均時延比ASAR算法低16.48 %，比AntWMSNs算法低18.89 %。EBQR算法的丟包率比ASAR算法和AntWMSN算法分別低23.22 %，22.83 %。EBQR算法的能耗比ASAR算法和AntWMSNs算法分別少1.912 5×10-4J,2.833 8×10-4J。EBQR算法的生命周期比ASAR算法和AntWMSNs算法分別延長了59 %和42.08 %。

圖1 平均傳輸時延Fig 1 Average transmission delay

圖2 平均丟包率Fig 2 Average packet loss rate

圖3 平均能量消耗Fig 3 Average energy consumption

算法本文算法ASAR算法AntWMSNs算法網(wǎng)絡(luò)生命周期(s)1175739827

4 結(jié) 論

在能量資源受限的WMSNs中，為滿足不同業(yè)務(wù)需求并充分考慮能量的高效使用，本文提出了一種EBQR算法。該算法將網(wǎng)絡(luò)帶寬、時延、丟包率和能量等因素作為目標(biāo)函數(shù)，利用蟻群根據(jù)目標(biāo)函數(shù)值的大小來動態(tài)調(diào)整信息素的揮發(fā)系數(shù)和信息素濃度增量，查找滿足不同QoS需求業(yè)務(wù)的最優(yōu)路徑。仿真表明：與AntWMSNs算法和ASAR算法相比，EBQR算法平均端到端時延降低了16 %，丟包率減少22 %，生命周期延長了近50 %，有效實現(xiàn)了網(wǎng)絡(luò)中節(jié)點能耗的均衡性。

[1] 陳志泊,徐孝成.一種改進(jìn)的基于跳數(shù)的無線傳感器網(wǎng)絡(luò)路由算法[J].計算機(jī)科學(xué),2013,40(4):83-85,114.

[2] Wang L,Ye W,Wang H,et al.Optimal node placement of industrial wireless sensor networks based onadaptive mutation probabi-lity binary particle swarm optimization algorithm[J].Computer Science and Information Systems,2012,9(4):1553-1576.

[3] 周 靈,王建新.無線多媒體傳感器網(wǎng)絡(luò)路由協(xié)議研究[J].電子學(xué)報,2011,39(11):149-156.

[4] 孫 巖,馬華東.無線多媒體傳感器網(wǎng)絡(luò)QoS保障問題[J].電子學(xué)報,2008,36(7):1412-1420.

[5] 段文軒.無線多媒體傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量的研究[D].泉州:華僑大學(xué),2012:1-4.

[6] Cobo Luis,Quintero Alejandro,Pierre Samuel.Ant-based routing for wireless multimedia sensor networks using multiple QoS me-trics[J].Computer Networks, 2010, 54(17): 2991-3010.

[7] Kandris Dionisis,Tsagkaropoulos Michail,Politis Ilias,et al.Energy efficient and perceived QoS aware video routing over wireless multimedia sensor networks[J].Ad Hoc Networks,2011,9(4):591-607.

[8] 李 雪,賀昱曜,武奇生.一種WMSNs能量感知QoS路由機(jī)制設(shè)計[J].計算機(jī)工程與應(yīng)用,2011,47(18):76-79.

[9] 黃 曼,程良倫.一種QoS保證的WMSNs實時路由協(xié)議[J].傳感器技術(shù)學(xué)報,2011,24(9):1341-1346.

[10] 李方敏,方藝霖,李 姮,等.無線多媒體傳感器網(wǎng)絡(luò)QoS區(qū)分服務(wù)路由機(jī)制[J].電子學(xué)報,2010,38(10):2322-2328.

[11] 孫 巖,馬華東,劉 亮.一種基于蟻群優(yōu)化的多媒體傳感器網(wǎng)絡(luò)服務(wù)感知路由算法[J].電子學(xué)報,2007,35(4):705-711.

[12] 謝 慧,吳曉平,張用宇,等.多媒體傳感器網(wǎng)絡(luò)中基于ACO的QoS路由協(xié)議[J].海軍工程大學(xué)學(xué)報,2009,21(6):15-19.

[13] Yu Xiaohua,Luo Jiaxing,Huang Jinwen.An ant colony optimization-based QoS routing algorithm for wireless multimedia sensor networks[C]∥Int’l Conf on Communication Software and Networks(ICCSN),2011:37-41.

[14] 胡耀鋒,張建明,王新勝,等.能量感知的無線傳感器網(wǎng)絡(luò)多路徑路由研究[J].計算機(jī)工程與設(shè)計,2009,30(21):4811- 4814,4827.

[15] 吳華鋒,陳信強(qiáng),毛奇凰,等.基于自然選擇策略的蟻群算法求解TSP問題[J].通信學(xué)報,2013,34(4):165-170.

[16] 周明秀,程 科,汪正霞.動態(tài)路徑規(guī)劃中的改進(jìn)蟻群算法[J].計算機(jī)科學(xué),2013,40(1):314-316.

[17] 高 曼,劉以安,張 強(qiáng).優(yōu)化蟻群算法在反艦導(dǎo)彈航路規(guī)劃中的應(yīng)用[J].計算機(jī)應(yīng)用,2012,32(9):2530-2533,2541.

Energy-balanced QoS routing algorithms for WMSNs*

YANG Bing1,2, DENG Shu-guang2, WEN Shuang-chun1

(1.College of Information Science and Engineering,Hunan University,Changsha 410082,China;2.School of Communication and Electronic Engineering,Hunan City University,Yiyang 413000,China)

To guarantee demand of energy-constrained wireless multimedia sensor networks(WMSNs)multi-QoS,a kind of energy-balanced QoS routing(EBQR)algorithm is proposed.The algorithm through ant colony optimization to make the network bandwidth,time delay,packet loss rate and energy as objective function,and according to function value size dynamically adjust volatility coefficient and density increments of ant colony information element,provide the optimal path to meet different QoS needs in network businesses.Simulation results show that, compare with the AntWMSNs algorithm and the ASAR algorithm,average end-to-end time delay of EBQR algorithm is reduced 16 %,the packet loss rate is reduced 22 %,the life cycle lengthened nearly 50 %,effectively realize equilibrium of node energy consumption in the network.

wireless multimedia sensor networks(WMSNs); energy-balanced; quality of serivce(QoS) routing; ant colony algorithm

2013—08—15

湖南省科技計劃資助項目(2012FJ3025)； 湖南省教育廳科研基金資助項目(12C0585)

TP 212

A

1000—9787(2014)04—0122—03

楊 冰(1981-)，女，湖南益陽人，碩士研究生，講師，研究方向為車域自組網(wǎng)和無線傳感器網(wǎng)絡(luò)理論與優(yōu)化。