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

路　揚，孫　暉，黃光群，劉俊延

（浙江大學 電氣工程學院，浙江 杭州310027）

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

路揚，孫暉，黃光群，劉俊延

（浙江大學 電氣工程學院，浙江 杭州310027）

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

無線傳感器網絡；三維胞元空間；自適應多跳；協同節點；能量高效

0　引言

WSN是具有數據融合、通信和計算等特定功能的節點以自組織的形式關聯在一起的網絡體系，能夠實時監測、感知和采集周圍環境的相關信息，并把信息經過處理后通過路由協議傳輸給終端計算機[1]。WSN在環境監測、智能交通等領域得到了廣泛的應用[2，3]。

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

3D-SAEAR算法和3D-CSR算法均存在簇首負擔較大的問題，本文在三維胞元空間模型的基礎上，提出了3DSMEER算法。該算法引入協同節點協助最優胞父轉發消息包，減少了總的路徑損耗，降低了網絡的能耗；建立協同節點選舉機制，保護了能量較低的節點，提高了能量利用率。

1　算法模型

1.1能耗模型

當傳輸 g bit字節時，總能耗 Es表達式如下所示[6]：

其中l表示節點之間的距離，Eelec表示發送 1 bit字節時，啟動電路能耗，εamp為放大電路能耗，γ為路徑損耗指數。本文假設在自由空間模型下，取γ=2。

1.2協同節點選擇模型

Bhardwaj等[7]提出當采用最佳傳輸距離Lideal轉發消息包時，通過最佳跳數Hideal，能耗達到最低，由Lideal確定的轉發位置稱為理想轉發節點位置，Lideal和Hideal表達式分別為：

WSN中一般達不到轉發節點相互距離為Lideal的要求，因此提出協同節點代替理想轉發節點多跳傳輸的模型。

基于協同節點的多跳模式的基本思想為：首先在貪婪策略下確定鄰居最優胞父，根據Lideal確定理想轉發節點位置 Mi；然后以 Mi為球心，作半徑為 r的球體，球體內的節點稱為候選協同節點；最后根據協同節點的選擇原則進行選舉：

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

(2)重復選擇避免機制：球體半徑r值增大時相鄰球體出現相離、相切與相交的三種關系，若某節點被選中為協同節點后不能作為另外球體的候選協同節點。

(3)胞父優先原則：球體中有胞父節點，則優先選擇胞父作為協同節點。

(4)能耗節省原則：同類型的節點比較時，優先考慮與理想節點位置距離最短的節點為協同節點。

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

圖1　基于協同節點的多跳模型

2　3D-SMEER算法

該算法根據自適應多跳機制決定傳輸方式，利用協同節點選擇機制選出轉發節點協助當前胞父傳輸消息包。

2.1自適應多跳機制

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

圖2　自適應多跳機制

2.2協同節點選擇機制

選擇協同節點時需要確定協同節點的選擇范圍，即球體的位置和半徑r。

2.2.1球體半徑r的確定

理想轉發節點空間坐標即為球心位置，在圖1中設鄰居最優胞父節點為P，其坐標為(XP，YP，ZP)，同時令當前胞元(XI，YI，ZI)C中胞父為 M0，其坐標為理想轉發位置處球心Mi的坐標為。以Mi的 X軸坐標 XMi為例，表達式為：

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

對于節點密度較小的網絡，r值過小，球體內找不到協同節點；反之，會增加傳輸路徑。假設存在rmax使r

當cosα=1時，即節點 J位于W點處時E2h取得最大值，此時可得到rmax表達式為：

考察式(7)得，0.5 Lideal

圖3　多跳示意圖

2.2.2協同節點的競選法則

協同節點的區域確定后，由低剩余能量保護原則和重復選擇避免機制確定候選協同節點。結合協同節點選擇原則，提出候選協同節點G的競選權重（Election Weight，EW），其表達式為：

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

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

2.33D-SMEER算法的具體過程

結合自適應多跳機制和協同節點選擇機制，總結出基于協同節點多跳路由的步驟為：

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

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

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

(4)依據候選節點的EW選擇出協同節點，將消息包通過協同節點轉發給鄰居最優胞父P。

具體流程如圖4所示。

圖4　自適應多跳路由流程圖

3　仿真實驗

3.1仿真環境及參數設置

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

表1　仿真參數值

3.2仿真結果分析

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

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

圖5　平均能耗仿真結果對比

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

圖6　存活率仿真結果對比

4　結論

3D-SMEER算法利用自適應多跳機制和協同節點選擇機制減輕了鄰居最優胞父傳輸負擔，有效地降低了整個網絡的平均能耗；依靠低剩余能量保護原則平衡了網絡的能量消耗，提高了節點的存活率。仿真結果驗證了其能量的高效性和能耗的高平衡度。進一步將繼續完善協同節點選擇機制，提高消息響應速度。

[1]宋文，王兵，周應賓，等.無線傳感器網絡技術與應用[M].北京：電子工業出版社，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].電子與信息學報，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，Finland，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)

路揚（1989-），男，碩士研究生，主要研究方向：信息處理、無線傳感器網絡與智能儀器。

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

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