路　揚(yáng)，孫　暉，黃光群，劉俊延

（浙江大學(xué) 電氣工程學(xué)院，浙江 杭州310027）

基于三維胞元空間的自適應(yīng)多跳能量高效路由

路揚(yáng)，孫暉，黃光群，劉俊延

（浙江大學(xué) 電氣工程學(xué)院，浙江 杭州310027）

針對(duì)無線傳感器網(wǎng)絡(luò)中三維路由算法的能耗問題，提出了基于三維胞元空間的自適應(yīng)多跳能量高效路由(3D-SMEER)。該路由算法根據(jù)自適應(yīng)多跳機(jī)制確定跳數(shù)，利用協(xié)同節(jié)點(diǎn)轉(zhuǎn)發(fā)消息包到鄰居最優(yōu)胞父，從而減輕當(dāng)前胞父的傳輸負(fù)擔(dān)。同時(shí)，對(duì)協(xié)同節(jié)點(diǎn)的選擇區(qū)域進(jìn)行了研究，并且考慮節(jié)點(diǎn)的剩余能量和相關(guān)位置信息選擇協(xié)同節(jié)點(diǎn)，以平衡網(wǎng)絡(luò)的能耗。仿真結(jié)果表明，與其他算法相比3D-SMEER算法節(jié)省了網(wǎng)絡(luò)的平均能耗，有效地提高了網(wǎng)絡(luò)的能耗平衡度。

無線傳感器網(wǎng)絡(luò)；三維胞元空間；自適應(yīng)多跳；協(xié)同節(jié)點(diǎn)；能量高效

0　引言

WSN是具有數(shù)據(jù)融合、通信和計(jì)算等特定功能的節(jié)點(diǎn)以自組織的形式關(guān)聯(lián)在一起的網(wǎng)絡(luò)體系，能夠?qū)崟r(shí)監(jiān)測(cè)、感知和采集周圍環(huán)境的相關(guān)信息，并把信息經(jīng)過處理后通過路由協(xié)議傳輸給終端計(jì)算機(jī)[1]。WSN在環(huán)境監(jiān)測(cè)、智能交通等領(lǐng)域得到了廣泛的應(yīng)用[2，3]。

由于三維空間的路由協(xié)議更符合實(shí)際的應(yīng)用環(huán)境，近年來其成為WSN研究的熱點(diǎn)。Li等人在文獻(xiàn)[4]中提出3D-SAEAR算法，通過迭代分簇方法一定程度上平衡了網(wǎng)絡(luò)的能耗，但是簇首死亡時(shí)才發(fā)動(dòng)選舉，造成節(jié)點(diǎn)過早死亡。Ke等人在文獻(xiàn)[5]中提出了三維胞元空間模型和 3D-CSR算法，建立了完整的分層路由體系，提出了自適應(yīng)選舉機(jī)制，但是采用貪婪路由方式選擇鄰居胞父節(jié)點(diǎn)中到目的節(jié)點(diǎn)的距離最短的作為下一跳節(jié)點(diǎn)（此節(jié)點(diǎn)為鄰居最優(yōu)胞父），沒有建立有效的能量模型來優(yōu)化傳輸路徑，導(dǎo)致平均能耗較多。

3D-SAEAR算法和3D-CSR算法均存在簇首負(fù)擔(dān)較大的問題，本文在三維胞元空間模型的基礎(chǔ)上，提出了3DSMEER算法。該算法引入?yún)f(xié)同節(jié)點(diǎn)協(xié)助最優(yōu)胞父轉(zhuǎn)發(fā)消息包，減少了總的路徑損耗，降低了網(wǎng)絡(luò)的能耗；建立協(xié)同節(jié)點(diǎn)選舉機(jī)制，保護(hù)了能量較低的節(jié)點(diǎn)，提高了能量利用率。

1　算法模型

1.1能耗模型

當(dāng)傳輸 g bit字節(jié)時(shí)，總能耗 Es表達(dá)式如下所示[6]：

其中l(wèi)表示節(jié)點(diǎn)之間的距離，Eelec表示發(fā)送 1 bit字節(jié)時(shí)，啟動(dòng)電路能耗，εamp為放大電路能耗，γ為路徑損耗指數(shù)。本文假設(shè)在自由空間模型下，取γ=2。

1.2協(xié)同節(jié)點(diǎn)選擇模型

Bhardwaj等[7]提出當(dāng)采用最佳傳輸距離Lideal轉(zhuǎn)發(fā)消息包時(shí)，通過最佳跳數(shù)Hideal，能耗達(dá)到最低，由Lideal確定的轉(zhuǎn)發(fā)位置稱為理想轉(zhuǎn)發(fā)節(jié)點(diǎn)位置，Lideal和Hideal表達(dá)式分別為：

WSN中一般達(dá)不到轉(zhuǎn)發(fā)節(jié)點(diǎn)相互距離為L(zhǎng)ideal的要求，因此提出協(xié)同節(jié)點(diǎn)代替理想轉(zhuǎn)發(fā)節(jié)點(diǎn)多跳傳輸?shù)哪Ｐ汀?/p>

基于協(xié)同節(jié)點(diǎn)的多跳模式的基本思想為：首先在貪婪策略下確定鄰居最優(yōu)胞父，根據(jù)Lideal確定理想轉(zhuǎn)發(fā)節(jié)點(diǎn)位置 Mi；然后以 Mi為球心，作半徑為 r的球體，球體內(nèi)的節(jié)點(diǎn)稱為候選協(xié)同節(jié)點(diǎn)；最后根據(jù)協(xié)同節(jié)點(diǎn)的選擇原則進(jìn)行選舉：

(1)低剩余能量保護(hù)原則：低剩余能量保護(hù)系數(shù)為 β（0<β<1），節(jié)點(diǎn)的初始能量為 Ei-ni，如果節(jié)點(diǎn)剩余能量 Eres<βEini，則該節(jié)點(diǎn)不能作為候選協(xié)同節(jié)點(diǎn)。

(2)重復(fù)選擇避免機(jī)制：球體半徑r值增大時(shí)相鄰球體出現(xiàn)相離、相切與相交的三種關(guān)系，若某節(jié)點(diǎn)被選中為協(xié)同節(jié)點(diǎn)后不能作為另外球體的候選協(xié)同節(jié)點(diǎn)。

(3)胞父優(yōu)先原則：球體中有胞父節(jié)點(diǎn)，則優(yōu)先選擇胞父作為協(xié)同節(jié)點(diǎn)。

(4)能耗節(jié)省原則：同類型的節(jié)點(diǎn)比較時(shí)，優(yōu)先考慮與理想節(jié)點(diǎn)位置距離最短的節(jié)點(diǎn)為協(xié)同節(jié)點(diǎn)。

LEN(A，B)表示節(jié)點(diǎn)A與節(jié)點(diǎn)B之間的距離。圖1為通過協(xié)同節(jié)點(diǎn)轉(zhuǎn)發(fā)的示意圖，其中LEN(C，M1)=LEN(M1，M2)=Lideal，d表示胞元的邊長(zhǎng)，當(dāng)前胞元(XI，YI，ZI)C中胞父節(jié)點(diǎn) C確定的鄰居最優(yōu)胞父 P位于胞元(XJ，YJ，ZJ)C內(nèi)。球M1內(nèi)有胞父節(jié)點(diǎn)，由原則(3)選擇胞父為協(xié)同節(jié)點(diǎn)；球 M2內(nèi)無胞父節(jié)點(diǎn)，由原則(4)選擇距離理想轉(zhuǎn)發(fā)節(jié)點(diǎn)最近的胞子為協(xié)同節(jié)點(diǎn)。

圖1　基于協(xié)同節(jié)點(diǎn)的多跳模型

2　3D-SMEER算法

該算法根據(jù)自適應(yīng)多跳機(jī)制決定傳輸方式，利用協(xié)同節(jié)點(diǎn)選擇機(jī)制選出轉(zhuǎn)發(fā)節(jié)點(diǎn)協(xié)助當(dāng)前胞父?jìng)鬏斚?/p>

2.1自適應(yīng)多跳機(jī)制

由公式(3)知，當(dāng)前胞父和鄰居最優(yōu)胞父的距離L與最佳傳輸距離Lideal的關(guān)系決定了最佳跳數(shù)Hideal。圖2(a)中當(dāng)L2Lideal時(shí)，由公式(3)得Hideal≥2，即采用多跳方式把消息包傳輸給鄰居最優(yōu)胞父；圖2(b)中當(dāng)Lideal< L<2Lideal時(shí)，比較二者傳輸消息包的能耗，協(xié)同節(jié)點(diǎn)位于M1處時(shí)，根據(jù)公式(1)計(jì)算比較兩跳能耗 E2h和單跳能耗E1h得：當(dāng)L>1.5 Lideal時(shí)，E1h>E2h，即多跳能耗更小。但是理想轉(zhuǎn)發(fā)位置處一般不存在節(jié)點(diǎn)，所以采用協(xié)同節(jié)點(diǎn)進(jìn)行多跳的最小距離為L(zhǎng)min=φLideal(1.5<φ<2)，即當(dāng)L

圖2　自適應(yīng)多跳機(jī)制

2.2協(xié)同節(jié)點(diǎn)選擇機(jī)制

選擇協(xié)同節(jié)點(diǎn)時(shí)需要確定協(xié)同節(jié)點(diǎn)的選擇范圍，即球體的位置和半徑r。

2.2.1球體半徑r的確定

理想轉(zhuǎn)發(fā)節(jié)點(diǎn)空間坐標(biāo)即為球心位置，在圖1中設(shè)鄰居最優(yōu)胞父節(jié)點(diǎn)為P，其坐標(biāo)為(XP，YP，ZP)，同時(shí)令當(dāng)前胞元(XI，YI，ZI)C中胞父為 M0，其坐標(biāo)為理想轉(zhuǎn)發(fā)位置處球心Mi的坐標(biāo)為。以Mi的 X軸坐標(biāo) XMi為例，表達(dá)式為：

其中 i∈N且[1，Hideal-1]。

對(duì)于節(jié)點(diǎn)密度較小的網(wǎng)絡(luò)，r值過小，球體內(nèi)找不到協(xié)同節(jié)點(diǎn)；反之，會(huì)增加傳輸路徑。假設(shè)存在rmax使r

當(dāng)cosα=1時(shí)，即節(jié)點(diǎn) J位于W點(diǎn)處時(shí)E2h取得最大值，此時(shí)可得到rmax表達(dá)式為：

考察式(7)得，0.5 Lideal

圖3　多跳示意圖

2.2.2協(xié)同節(jié)點(diǎn)的競(jìng)選法則

協(xié)同節(jié)點(diǎn)的區(qū)域確定后，由低剩余能量保護(hù)原則和重復(fù)選擇避免機(jī)制確定候選協(xié)同節(jié)點(diǎn)。結(jié)合協(xié)同節(jié)點(diǎn)選擇原則，提出候選協(xié)同節(jié)點(diǎn)G的競(jìng)選權(quán)重（Election Weight，EW），其表達(dá)式為：

其中G表示當(dāng)前候選協(xié)同節(jié)點(diǎn)，n表示候選協(xié)同節(jié)點(diǎn)總數(shù)，K[j]表示球體中第j個(gè)候選協(xié)同節(jié)點(diǎn)，LEN(K[j]，Mi)表示球體Mi中第j個(gè)候選協(xié)同節(jié)點(diǎn)與球心Mi的距離，Eres(K[j])表示第j個(gè)候選協(xié)同節(jié)點(diǎn)的剩余能量，權(quán)重系數(shù) λ和η的關(guān)系為：λ+η=1(0≤λ≤1，0≤η≤1)。其中θ的取值遵循以下原則：當(dāng)球體內(nèi)候選協(xié)同節(jié)點(diǎn)是同類型的節(jié)點(diǎn)，即都是胞子或者胞父節(jié)點(diǎn)時(shí) θ=1；否則，胞父節(jié)點(diǎn)θ=1，胞子節(jié)點(diǎn)θ=0。

協(xié)同節(jié)點(diǎn)競(jìng)選法則：將球體內(nèi)每個(gè)候選節(jié)點(diǎn)的剩余能量和空間位置帶入式(8)中，按照上述原則比較球體內(nèi)候選節(jié)點(diǎn)的EW，最后選擇出EW值最大的作為本球體的協(xié)同節(jié)點(diǎn)。

2.33D-SMEER算法的具體過程

結(jié)合自適應(yīng)多跳機(jī)制和協(xié)同節(jié)點(diǎn)選擇機(jī)制，總結(jié)出基于協(xié)同節(jié)點(diǎn)多跳路由的步驟為：

(1)根據(jù)貪婪策略，判斷出鄰居最優(yōu)胞父 P，并計(jì)算LEN(C，P)。

(2)由自適應(yīng)多跳機(jī)制判斷采用多跳或者單跳，如果結(jié)果為單跳則直接把消息包傳遞給鄰居最優(yōu)胞父P，否則進(jìn)入步驟(3)。

(3)利用協(xié)同節(jié)點(diǎn)選擇機(jī)制確定球心的空間位置和協(xié)同節(jié)點(diǎn)的選擇范圍，然后根據(jù)低剩余能量保護(hù)原則和重復(fù)選擇避免機(jī)制確定是否存在候選協(xié)同節(jié)點(diǎn)，若不存在則直接把消息包傳遞給鄰居最優(yōu)胞父P，否則進(jìn)入步驟(4)。

(4)依據(jù)候選節(jié)點(diǎn)的EW選擇出協(xié)同節(jié)點(diǎn)，將消息包通過協(xié)同節(jié)點(diǎn)轉(zhuǎn)發(fā)給鄰居最優(yōu)胞父P。

具體流程如圖4所示。

圖4　自適應(yīng)多跳路由流程圖

3　仿真實(shí)驗(yàn)

3.1仿真環(huán)境及參數(shù)設(shè)置

仿真是在OMNet++V4.1平臺(tái)上進(jìn)行的，節(jié)點(diǎn)分布在體積為400 m×400 m×400 m的立方體內(nèi)。與3D-CSR和3D-SAEAR進(jìn)行仿真結(jié)果比較時(shí)，為了使仿真結(jié)果更有可比性，假定消息包只按照貪婪模式進(jìn)行傳輸。參數(shù)設(shè)定如表1所示。

表1　仿真參數(shù)值

3.2仿真結(jié)果分析

仿真結(jié)果將通過平均能耗和節(jié)點(diǎn)存活率進(jìn)行對(duì)比。平均能耗(average energy consumption)為傳輸 k條消息包所消耗的總能耗與 k的比值；節(jié)點(diǎn)存活率(Alive rate)為傳遞k條消息包后存活節(jié)點(diǎn)占總節(jié)點(diǎn)數(shù)的百分比。

3D-SMEER，3D-SAEAR與3D-CSR的平均能耗曲線如圖5所示。3D-SAEAR與3D-CSR相比增加了角度機(jī)制，所以其平均能耗比3D-CSR略有減少。3D-SMEER通過協(xié)同節(jié)點(diǎn)轉(zhuǎn)發(fā)消息包，相比3D-SAEAR與3D-CSR有效降低了平均能耗。圖5(a)和圖5(b)中每個(gè)胞元的節(jié)點(diǎn)個(gè)數(shù)N分別為2和4，隨著N的增加，3D-SMEER增加了中間協(xié)同節(jié)點(diǎn)的個(gè)數(shù)，使得傳輸能耗減少，所以圖5(a)和圖5(b)中3D-SMEER的平均能耗是逐漸降低的，而3D-SAEAR與3D-CSR的平均能耗基本不變。

圖5　平均能耗仿真結(jié)果對(duì)比

三者的節(jié)點(diǎn)存活率與消息包的關(guān)系如圖6所示。圖6(a)和圖6(b)中胞元的節(jié)點(diǎn)數(shù)N分別為2和4，3D-CSR通過自適應(yīng)胞父選舉平衡了網(wǎng)絡(luò)的能耗，所以3D-CSR與3D-SAEAR相比提高了節(jié)點(diǎn)的存活率，并且隨著胞元內(nèi)節(jié)點(diǎn)數(shù)N的增多，選舉機(jī)制能夠發(fā)揮更好的作用；3D-SMEER與 3D-CSR相比，通過協(xié)同節(jié)點(diǎn)轉(zhuǎn)發(fā)消息包，降低了鄰居最優(yōu)胞父的傳輸負(fù)擔(dān)，從而提高了網(wǎng)絡(luò)節(jié)點(diǎn)的存活率，當(dāng)網(wǎng)絡(luò)的節(jié)點(diǎn)密度增加時(shí)，增加了其他節(jié)點(diǎn)參加傳輸消息包的概率，所以提高了存活率。

圖6　存活率仿真結(jié)果對(duì)比

4　結(jié)論

3D-SMEER算法利用自適應(yīng)多跳機(jī)制和協(xié)同節(jié)點(diǎn)選擇機(jī)制減輕了鄰居最優(yōu)胞父?jìng)鬏斬?fù)擔(dān)，有效地降低了整個(gè)網(wǎng)絡(luò)的平均能耗；依靠低剩余能量保護(hù)原則平衡了網(wǎng)絡(luò)的能量消耗，提高了節(jié)點(diǎn)的存活率。仿真結(jié)果驗(yàn)證了其能量的高效性和能耗的高平衡度。進(jìn)一步將繼續(xù)完善協(xié)同節(jié)點(diǎn)選擇機(jī)制，提高消息響應(yīng)速度。

[1]宋文，王兵，周應(yīng)賓，等.無線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用[M].北京：電子工業(yè)出版社，2007.

[2]LARIOS D F，BARBANCHO J，SEVILLANO J L，et al. Energy efficient wireless sensor network communications based on computational intelligent data fusion for environmental monitoring[J].IET Commun.，2012，6(14)：2189-2197.

[3]BOTTERO M，DALLA C B，DEFLORIO F P.Wireless sensor networks for traffic monitoring in a logistic centre[J].Transportation Research Part C：Emerging Technologies，2013，26：99-124.

[4]Li Y M，Wang X W，Huang M. Space Angle Based Energy-Aware Routing Algorithm in Three Dimensional Wireless Sensor Networks[C].Proceedings of the International Symposium on Distributed Computing and Applications to Business，Engineering&Science (DCABES)，Los Alamitos，CA，USA，September 2-4，2013：217-221.

[5]柯濤，孫暉，劉俊延，等.基于三維胞元空間的無線傳感器路由算法[J].電子與信息學(xué)報(bào)，2013，35(6)：1298-1304.

[6]HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks[C].Proceedings of the Hawaiian International Conference System Sciences，Maui，Hawaii，January 4-7，2000：1-10.

[7]BHARDWAJ M，GARNETT T，CHANDRAKASAN A P. Upper bounds on the lifetime of sensor networks[C].Proceedings of the IEEE International Conference on Communications，Helsinki，F(xiàn)inland，June，2001：151-156.

Self-adaptive multi-hop energy efficiency routing based on 3D cell space

Lu Yang，Sun Hui，Huang Guangqun，Liu Junyan
(College of Electrical Engineering，Zhejiang University，Hangzhou 310027，China)

Considering the problem of energy consumption in 3D routing algorithm of Wireless Sensor Network(WSN),a selfadaptive multi-hop energy efficiency routing algorithm based on 3D cell space(3D-SMEER)was presented.In order to reduce the burden on the current cell leader,the algorithm determined the number of hops based on a self-adaptive multi-hop mechanism, and then the message packets were forwarded by collaborative nodes.Meanwhile,for the sake of the balance of energy consumption of the networks,the algorithm studied the selection region of the collaborative nodes,and the collaborative nodes were selected based on residual energy and related location information.Simulation results show that compared with other algorithms 3D-SMEER saves average energy consumption of the networks,effectively improves the balance of energy consumption of the networks.

Wireless Sensor Networks(WSN)；3D cell space；self-adaptive multi-hop；collaborative nodes；energy efficiency

TP393

A

0258-7998(2015)01-0090-04

10.16157/j.cnki.0258-7998.2014070202447

2014-07-02)

路揚(yáng)（1989-），男，碩士研究生，主要研究方向：信息處理、無線傳感器網(wǎng)絡(luò)與智能儀器。

孫暉（1971-），男，博士，副教授，主要研究方向：信息處理、無線傳感器網(wǎng)絡(luò)與智能儀器。

黃光群（1990-），男，碩士研究生，主要研究方向：信息處理、無線傳感器網(wǎng)絡(luò)與智能儀器。