基于(ε,ζ)-近似融合的無線傳感網拓撲控制算法

湯　榮　郭　劍

(南京郵電大學計算機學院　江蘇 南京 210003)

?

基于(ε,ζ)-近似融合的無線傳感網拓撲控制算法

湯榮郭劍

(南京郵電大學計算機學院江蘇 南京 210003)

對無線傳感器網絡的拓撲控制問題進行研究。為了節約網絡能量，最大化網絡生命周期，提出一種基于(ε,ζ)-近似數據融合的拓撲結構控制算法QGA-UQ(Quantum Genetic Algorithm-Unique Q)。QGA-UQ引入了節點調度的思想。它首先根據用戶的數據精度要求，確定網絡中工作節點的比例，接著再使用量子遺傳算法，從網絡中選取合適的節點，并形成合理的拓撲結構。網絡在此基礎之上進行數據的傳輸和融合處理。仿真試驗表明，QGA-UQ算法可以在保證融合結果精度的前提下，顯著延長了網絡生存時間，提高了網絡能量利用率。

拓撲控制無線傳感器網絡(ε,ζ)-近似融合節點調度量子遺傳算法

0　引　言

近年來，隨著計算機技術和傳感器技術的發展和成熟，無線傳感器網絡WSNs(Wireless Sensor Networks)成為一個熱門領域，引起了人們的廣泛關注。無線傳感器網絡主要是由部署在監測區域內的大量傳感器節點組成，通過無線通信的方式，形成一個多跳式的自組織網絡。目前主要應用于醫療衛生、環境監測、災難預防、生態保護、智能家居等各個領域[1-3]。

拓撲控制是無線傳感器網絡的核心技術之一，它主要通過節點調度、發射半徑調節、通信鏈路選擇等手段，優化網絡的拓撲結構。通過拓撲控制技術，可以實現節約網絡能量、提升網絡通信性能等目標。在這方面，比較經典的工作是WBHeinzelman等人[4]提出的LEACH協議。為了減少數據傳輸的能耗，LEACH使用了簇結構，并在數據傳輸到基站前使用簇頭節點來融合數據，但是它的簇頭選取和數據傳輸策略存在一定問題，并且不能很好地兼顧到邊緣節點。在LEACH算法的基礎上，SDMuruganathan等[5]提出了BCDCP算法，采用迭代集群分裂算法選出多個簇頭節點，用MST(Minimum Spanning Tree)結構連接簇頭節點，保證任意兩個節點之間都存在有向路徑，這樣整體拓撲結構較復雜，能耗偏大。較早提出用MST結構來連接拓撲的是Li N[6]，其采用了MST結構來連接所有網內傳感器節點，用MST-Z算法來調整拓撲，結構得到一定簡化，但依舊能耗較大。同時，拓撲控制還需考慮其他問題，例如Nishiyama H等[7]研究了動態網絡中的拓撲控制，Kim D等[8]控制拓撲時避免傳感器節點監測區域的覆蓋沖突。

在傳感器網絡的實際應用中，人們往往并不關心節點采集的具體數據，而是更關心宏觀的統計結果，如一個地區的平均溫度、最高濕度等，從而進行評估、決策等處理。這種情況下，就需要對網絡的采集數據進行一定的融合處理[9,10]。由于網絡拓撲不健壯、節點調度休眠等原因，網絡往往會丟失部分采集數據，這時候，一些近似融合技術也就應運而生。ADeligiannakis等[11]和GHartl等[12]分別提出了基于時間的和基于空間的融合算法，它們在進行融合時不需要全部的數據，但是不能有效地控制誤差范圍。Sergiou C等[13]在近似融合過程中隨機選定傳感器節點作為活躍節點，用RANDOM-UQ算法控制節點的工作與休眠，數據精確性依舊得不到滿足。Jianzhong Li等[14]提出的(ε,ζ)-近似融合算法，可以有效地控制融合的精度，但是它采用的網絡拓撲并不是很好。

上述研究表明，為了達到通信性能、節能效果與融合精度的平衡，有必要將拓撲控制技術與數據融合技術結合起來進行研究。從這個角度出發，本文提出了一種基于(ε,ζ)-近似數據融合的拓撲結構控制算法QGA-UQ(Quantum Genetic Algorithm- Unique Q)。QGA-UQ基于節點調度的思想，它首先根據融合結果精度的要求，確定網絡中休眠節點與工作節點的比例，接著再使用量子遺傳算法，從網絡中選取合適的節點，并基于MST樹形成網絡拓撲結構。網絡在此基礎之上進行數據傳輸和數據融合。上述過程可以循環進行，從而使節點輪流休息，達到延長網絡生命周期的目的。實驗結果表明，QGA-UQ算法較好地實現了設計的目標。

1　相關模型與假設

1.1網絡模型

現有一塊無線傳感網的監測區域，該區域部署了大量的傳感器節點，節點的部署方式為隨機部署。所有節點同質，并且可以調節各自的發射功率。

假設網絡初始時共有N個節點。在時刻t，無線傳感網內存活節點的數目為Nt。依次對每次傳感器節點進行編號，編號i從1到Nt。顯然，當t=0時，Nt=N。

傳感器節點i在t時刻對應的感知數據記為kti，把監測區域內所有活動節點的感知數據組合成一個數據集Kt，即Kt={kt1,kt2,…,ktNt}。考慮到任何實際感知數據都是有范圍的，因此假定所有感知數據的上下界的值分別記為max(Kt)和min(Kt)，并假設min(Kt)大于0。

本文假定，網絡要求對監測區域內觀測值的平均值Avg進行融合，并且融合結果要達到(ε,ζ)-近似估計的要求，(ε,ζ)-近似估計的精確定義將在第2節給出。

1.2能耗模型

本文使用了如下的能耗模型[15]。

無線傳感網內的傳感器節點在發送和接收1bit數據時都需要消耗能量，分別記為Ef和Ej。兩者可通過以下公式計算：

當d

而d≥d0時，Ef=Eelec+μampd4

Ej=Eelec

其中，d為該節點與相鄰通信節點的距離，d0為收發兩端的距離門限值，Eelec是發射電路與接收電路的能耗，μfs和μamp分別為慢衰落模型和快衰落模型的參數。

2　活躍節點比率的確定

出于節能的考慮，當網絡中的節點較多時，可以只讓部分節點進入工作狀態，以減少網絡的能耗。但是另一方面，休眠的那部分節點也會導致采集數據的丟失，從而給數據融合的結果帶來一定的誤差。因此，活躍節點的比率q與數據融合的精度存在一定的約束關系。本節首先給出數據融合精度的相關描述，再給出q的計算方法。

關于近似融合，有如下定義[14]：

(1)

假定在時刻t，網絡采集的數據集為Kt，則此刻平均值Avg的融合結果為：

其中，inf(Nt)表示整個融合過程中無線傳感網內活動節點數目的最低值，Φζ/4為標準正態分布的ζ/4分位值。

3　基于(ε,ζ)-近似數據融合的拓撲控制算法

本文提出了基于(ε,ζ)-近似融合的無線傳感網拓撲結構控制算法QGA-UQ，其總體思路是從網絡中選擇部分節點，并對這部分節點進行一定的運算處理，形成合適的拓撲結構。在拓撲調整過程中，控制每個傳感器節點的休眠與工作狀態，不同周期內選取不同傳感器節點進行數據融合。

上一節主要討論了選擇節點的比例，這一節將討論根據這個比例如何來選擇節點并生成網絡拓撲。由于無線傳感網內傳感器節點數目多、密度大，數據傳輸的能耗相當可觀，因此網絡拓撲的構建主要從節能角度來考慮。QGA-UQ采用MST結構[15]連接工作的傳感器節點，計算的過程則采用了量子遺傳算法[16]。

3.1染色體編碼及測量

本文把拓撲結構的求解過程看作是量子遺傳算法中的種群演化過程，每一代種群中含有若干條染色體。每條染色體表示當前無線傳感網內所有節點的選擇情況。如圖1所示，染色體由一串二進制數字表示，長度等于無線傳感網內傳感器節點的總數，即染色體有N位。每一位數字0代表對應的傳感器節點未被選取，1代表對應的傳感器節點被選取。被選取的傳感器節點參與數據信息的傳輸，以及數據融合工作，未被選取的傳感器節點可以暫時休眠。

節點1節點2節點3節點4節點5節點6…節點N100110…1

圖1染色體結構

染色體的測量與量子比特概率幅有關。根據量子比特和量子旋轉門的調整，計算出相應的量子比特概率幅，每一周期的量子比特概率幅不同，測量染色體時，生成一個0到1之間的隨機數，若隨機數的值大于概率幅的平方，則染色體當前位的二進制數取1，反之，則染色體當前位取0。

3.2染色體評價

圖2　MST結構示意圖

對染色體進行評價必須從整個網絡的拓撲結構考慮，圖2所示就是MST樹結構的例子。其中，圖2(a)可以看到6個傳感器節點，節點b是簇頭節點，所有鏈路上標明的數字即為該段鏈路數據傳輸的權值。圖2(b)是圖2(a)對應的MST拓撲結構，它可以保證每個節點都能將數據傳輸到簇頭節點b且網絡總權值最小。

在此基礎之上，本節把染色體的評價函數設為：

f=αEs-βEx+γEmin

其中，α、β和γ是相應的系數，且它們都大于0。染色體評價函數主要考慮了如下三個方面：

(1) 網絡內所有節點的剩余能量之和Es，若第i個傳感器節點的剩余能量為Ei，那么Es可由下式得到：

(2) 網絡內所有傳感器節點消耗的能量總和Ex，可由下式計算得到：

其中Ei′是第i個傳感器節點消耗的能量，該計算可以參考1.2節的能耗模型。

(3) 該方案中網絡內所剩能量最少節點的能量Emin，由式(2)可得。加入該項分量是出于網絡能量分布平衡性的考慮。

Emin=min{E1,E2,…,EqNt}

(2)

3.3QGA-UQ的算法流程

(1) 網絡初始化。在已知的監測區域范圍，隨機部署規定數目的傳感器節點，并且將它們從1到N進行編號，設定觀測數據值的上下界max(Kt)和min(Kt)。

(2) 結合(ε,ζ)-近似融合的要求，計算傳感器節點工作比例q。

(3) 使用量子遺傳算法計算出合適的網絡拓撲結構。

(4) 網絡運行一定周期。在該周期內，未被選中的節點進行休眠，選中的節點則進入數據采集和傳輸等工作狀態，并由sink節點進行數據融合的處理和估計。

(5) 如果網絡中的剩余節點少于qN，算法終止，否則轉入(2)。

4　仿真實驗

本節通過仿真實驗驗證QGA-UQ算法的性能。仿真基于VS2013平臺，參數設置見表1。仿真時傳感器節點位置隨機部署。

表1　實驗仿真參數設置

首先，我們通過改變(ε,ζ)-近似融合中的ε和ζ的值，統計傳感器節點工作比例q的變化情況，表2是max(Kt)、min(Kt)分別為996和902時計算得出的結果。行代表ε，列代表ζ，數值代表的是傳感器節點工作比例q。表中可以看出，ζ相同時，ε越大，傳感器節點工作比例q越小，那是因為根據第2節定義1和2，ε越大融合結果容許的誤差更大，所以節點工作比例不必那么大；ε相同時，ζ越大，傳感器節點工作比例q也越小，同樣也可根據第2節定義1和2分析出，ζ越大其實要求的數據精確度更低，所以只要抽樣較少的傳感器節點。ε和ζ越靠近0時，要求的數據精確率逐步達到最高，于是傳感器節點工作比例q也越靠近于1。當ε為0.1、ζ為0.1時，傳感器節點工作比例q達到0.9835。同時可以進一步發現，ε的值對q的影響較大。

表2　不同ε、ζ對應的傳感器節點工作比例q

在研究QGA-UQ算法的優劣時，主要考慮以下兩個方面：網絡的生存時間和融合結果的相對誤差。本文將QGA-UQ算法與如下兩種算法進行對比：(1)MST-Z算法：基于總體進行數據融合處理，采用Prim算法的思想將所選節點用MST樹結構連接，對拓撲結構進行調整優化。(2)RANDOM-UQ算法：基于概率抽樣法進行數據融合處理，采用隨機取點算法來控制拓撲結構。三種算法同時在ε和ζ都取0.3的情況下仿真比較。

本文中，網絡生命周期定義為網絡內存活節點數低于qN時所經歷的周期數，其中假設傳感器節點自身能量Es小于10 mJ時，該節點已死亡，不能再進入工作狀態。從圖3中可以看出，QGA-UQ算法下的網絡生存時長最長， RANDOM-UQ算法次之， MST-Z算法下的網絡生存時長最短。因此，MST樹結構比隨機拓撲結構更能延長網絡生命周期。同時利用(ε,ζ)-近似融合來處理感知數據時，能極大地提高生存時長。

圖3　三種算法的生存時間對比

在不同周期，對比三種算法融合結果與實際結果的相對誤差，如圖4所示，因為MST-Z算法是對無線傳感網中總體的傳感器節點進行數據采集，計算得出的Avg值沒有誤差。而其他兩種算法由于是抽樣采集，所以都存在不同程度的誤差，但總體來看，均遠遠小于預期的容許誤差0.3。

圖4　三種算法融合結果的相對誤差對比

綜上所述，在本文比較的三個拓撲控制算法中，QGA-UQ算法在保證較低的融合結果相對誤差下，網絡生存時間更長并且整體網絡能耗最少，是最優的一種拓撲結構控制算法。

5　結　語

為盡可能地監測無線傳感網中的真實數據和減少整個網絡的能耗，本文提出了一種基于(ε,ζ)-近似數據融合的無線傳感網拓撲結構控制算法QGA-UQ。首先，根據(ε,ζ)-近似數據融合法計算出抽樣傳感器節點數目，然后利用量子遺傳算法，通過種群染色體的不斷演化，基于MST結構不斷調整，最后得出最優拓撲結構。仿真實驗表明，該算法對比已有算法表現出了良好的性能和穩定性。

[1] Luís M Borges.Survey on the Characterization and Classification of Wireless Sensor Network Applications[J].IEEE Communication Surveys & Tutorials,2014,16(4):1860-1890.

[2] 孫利民,李建中,陳渝,等.無線傳感器網絡[M].北京:清華大學出版社,2005.

[3] Corporation H P.Multihop-Based Optimal Cluster Heads Numbers Considering Relay Node in Transmission Range of Sensor Nodes in Wireless Sensor Networks[J].International Journal of Distributed Sensor Networks,2013,13(2):140-154.

[4] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[C]//The 33rd Annual Hawaii International Conference on System Siences (HICSS-33),Maui,USA,IEEE,Los Alamitos,CA,United States,2000:3005-3014.

[5] Muruganathan S D,Bhasin R I.A centralized energy-efficient routing protocol for wireless sensor networks[J].IEEE Communications Magazine,2005,43(3):S8-S13.

[6] Li N,Hou J C,Sha L.Design and analysis of an MST-based topology control algorithm[J].Proceedings-IEEE INFOCOM,2002,4(3):1195-1206.

[7] Nishiyama H.On minimizing the impact of mobility on topology control in mobile ad hoc networks[J].IEEE Transactions on Wireless Communications,2012,11(3):1158-1166.

[8] Kim D,Noel E,Tang K W.WSN communication topology construction with collision avoidance and energy saving[C]//2014 IEEE 11th Consumer Communications and Networking Conference,CCNC 2014,Las Vegas,NV,United states,IEEE Computer Society,2014:398-404.

[9] 牛淑芬,王彩芬,杜小妮.無線傳感器數據融合技術中基于同態哈希函數的數據完整性算法[J].計算機應用與軟件,2013,30(12):48-51.

[10] Jose J,Manoj Kumar S,Jose J.Energy efficient recoverable concealed data aggregation in wireless sensor networks[C]//2013 IEEE International Conference on Emerging Trends in Computing,Communication and Nanotechnology,ICE-CCN,2013:322-329.

[11] Deligiannakis A,Kotidis Y,Roussopoulos N.Processing approximate aggregate queries in wireless sensor networks [J].Information Systems,2006,31(8):770-792.

[12] Hartl G.A Bayesian Inference Approach towards Energy Efficient Data Collection in Dense Sensor Networks[C]//25th IEEE International Conference on Distributed Computing Systems,Columbus,OH,United states,Institute of Electrical and Electronics Engineers Inc,2005:371-380.

[13] Sergiou C.Source based routing trees for efficient comgestion control in wireless sensor networks[C]//8th IEEE International Conference on Distributed Computing in Sensor Systems,Hangzhou,China,IEEE Computer Society,2012:378-383.

[14] Li J Z,Cheng S Y.(ε,ζ)-Approximate Aggregation Algorithms in Dynamic Sensor Networks.[J].IEEE Transactions on Parallel and Distributed Systems,2011,23(3):385-396.

[15] 韓崇,孫力娟,肖甫,等.基于SVD的無線多媒體傳感器網絡圖像壓縮機制[J].東南大學學報：自然科學版,2012,42(5):814-819.

[16] Huang G Y,Li X W,He J.Dynamic Minimal Spanning Tree Routing Protocol for Large Wireless Sensor Networks[C]//2006 1st IEEE Conference on Industrial Electronics and Applications,ICIEA,2006:1-5.

[17] 孫力娟,郭劍,陸凱,等.基于量子遺傳算法的傳感器網絡拓撲結構控制[J].通信學報,2006,27(12):1-5.

A TOPOLOGY CONTROL ALGORITHM FOR WIRELESS SENSOR NETWORKS BASED ON (ε,ζ)-APPROXIMATE AGGREGATION

Tang RongGuo Jian

(School of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,Jiangsu,China)

We study the topology control of wireless sensor networks in this paper.In order to save network energy and maximise network lifecycle,we propose a (ε,ζ)-approximate aggregation-based topology control algorithm QGA-UQ (quantum genetic algorithm-unique Q).QGA-UQ introduces the idea of node scheduling.It firstly determines the proportion of working nodes in network based on user’s requirement of data accuracy.Then it uses quantum genetic algorithm to select appropriate nodes in network and construct a reasonable topology.On this basis the network carries out the operation of data transmission and data fusion.Stimulation tests show that QGA-UQ can prolong the survival time of the network significantly and improve the utilisation of network energy greatly on the premise of guaranteeing the precision of fusion results.

Topology controlWireless sensor networks(ε,ζ)-approximate aggregationNode schedulingQuantum genetic algorithm

2015-04-17。中國博士后科學基金項目(2014M5516 35)；江蘇省博士后科研計劃項目(1302085B)。湯榮，碩士生，主研領域：無線傳感網。郭劍，副教授。

TP393

A

10.3969/j.issn.1000-386x.2016.09.027