基于物理干擾模型的延遲最小化數據匯聚算法

王 亞，李光順

(曲阜師范大學 信息科學與工程學院，山東 日照 276800)

基于物理干擾模型的延遲最小化數據匯聚算法

王 亞，李光順

(曲阜師范大學 信息科學與工程學院，山東 日照 276800)

在無線傳感器網絡(Wireless Sensor Networks,WSN)中,如何快速、準確地將傳感器收集的數據匯聚給匯聚節點是數據匯聚中的一個重要問題。早期，研究者主要研究了協議干擾模型下的數據匯聚問題。由于協議干擾模型不能精確計算節點之間的干擾，而物理干擾模型可以克服這個缺點。因此，針對物理干擾模型中的延遲最小化數據匯聚問題，提出了一個Hexagon-AS算法，得到了一個延遲上界O(m)，其中m為覆蓋網絡的六邊形的層數。該算法首先用六邊形單元格將網絡覆蓋，然后對單元格染色，最后對具有相同顏色的單元格進行并發調度。仿真結果表明，Hexagon-AS算法比現有的算法有更小的延遲。

無線傳感器網絡；數據匯聚；物理干擾模型；延遲

0 引 言

無線傳感器網絡是一個自組織網絡，由部署在受監測區域內的大量低成本、低功耗，具有感知、數據存儲、數據處理和無線通信能力的傳感器節點組成。其目的是協作地采集、處理和傳輸網絡覆蓋區域中被感知對象的信息[1-2]。在傳感器傳遞數據的過程中，如果原始數據可以被聚合且只有聚合值被傳送到匯聚節點，稱它為數據匯聚[3-4]。數據匯聚是無線傳感器網絡的典型傳輸形態[5-6]。經過匯聚，中間節點傳遞給下一跳節點的數據大小僅是接收數據的一小部分[7]。

在數據匯聚中，延遲最小化數據匯聚是眾多研究者關注的問題之一[8]。目前，協議干擾模型下的數據匯聚已取得了大量成果。但協議干擾模型在計算干擾時僅計算了鄰近區域的干擾，忽略了網絡中其他節點的干擾。而物理干擾模型將網絡中所有并發傳輸節點產生的干擾都考慮進來，可以更精確地計算節點間的干擾。

1 相關工作

數據匯聚自從在文獻[9]中被提出以后，便得到了廣泛關注。在文獻[10-14]中提出了若干基于協議干擾模型的集中式延遲最小化數據匯聚算法。Chen等在文獻[10]中證明了延遲最小化數據匯聚是NP難問題，并給出了一個(Δ-1)近似算法。其中Δ為網絡中節點的最大度。隨后Huang等設計了一個基于極大獨立集的集中式算法[13]，得到的延遲為23R+Δ-18,R為網絡半徑。但是，集中式算法不具有可擴展性[15]，因此，后來研究者們開始研究分布式算法來解決這個問題。目前，在分布式算法中取得的最好的延遲界為O(Δ+R、)，R'低于網絡半徑，滿足R'≤R≤D≤2R、，D是網絡直徑[14]。

Li等研究了物理干擾模型下的延遲最小化數據匯聚[16]，得到的延遲界為O(R+Δ)。之后Li設計了一種分布式算法[17]，取得了一個有效的延遲界O(K)，其中K是網絡中最長鏈路長度和最短鏈路長度的比率對數。而文獻[17]中假設節點的功率足以覆蓋網絡中最遠的兩個節點，這個假設太過理想。文中提出了一種Hexagon-AS算法，并證明了算法的有效性。

2 網絡模型

文中考慮由n個傳感器節點V={v1,v2,…,vn}和一個匯聚節點v0組成的無線傳感器網絡，其中vi表示節點i，ei表示節點i的能量。這些節點隨意分布在一個圓形區域A中，A=πr2，r為網絡的區域半徑。匯聚節點位于該區域的中心。假設網絡中任何兩個節點之間的距離至少為1。令T=(V,E)表示以匯聚節點為根的數據匯聚樹，V={v0,v1,…,vn}，E={ei,j|i≠j},ei,j表示從節點vi到節點vj的一條鏈路。

問題是構造一棵數據匯聚樹T，網絡中的傳感器沿著這棵樹將收集到的數據傳遞給匯聚節點，使所用的時隙總數最少。在數據傳輸過程中，需要滿足物理干擾模型的條件，即信號干擾加噪聲比(SINR)：

其中，vi和vj分別表示發送節點和接收節點；Pi表示節點vi的功率；‖vi-vj‖表示節點vi和節點vj之間的歐幾里得距離；vk為與vi并發傳輸的其他節點；N0為背景噪聲；α為路徑損耗因子，其值為[2,6]；β為SINR閾值，通常大于1。

3 網絡劃分

圖1 數據匯聚

圖2 層和段的劃分

4 算法描述

算法的主要思想如下：

第一階段，單元格內的調度。首先在每個單元格內選出一個具有最大能量emax=max{ei|vi∈ci,j}的節點，作為該單元格內的局部匯聚節點，單元格內的其他節點都在給定的時隙內，將收集到的數據傳送給局部匯聚節點。為避免節點間的干擾，給單元格染色，具有相同顏色的單元格需要滿足它們之間的距離足夠遠。文中設定它們之間的距離至少為2(X+1)d，如圖1(b)所示。

算法1：HAS 。

Input: Node setVwith sinkV0

Output:Data aggregation treeTand link scheduleS

1.t=0,d=1,T=φ,S=φ,St=φ,E=φ,E′=φ,E″=φ,E?=φ;

2.Cover the network with cells of side lengthdand color them

3.whilel>0 do

5. cells with coloriselect one node which has the max energy as the local aggregation nodeAij

6. nodes in the cellscijtransmit its data toAijin the specify time soltt

8.St=St∪E′;

9.t=t+1;

10.E=E∪E′ ;

11. for each segment

12. calling LTL;

13. forL=m-ω+1 to 0 do

14. calling STS;

15.end while;

16.T=T∪E;

17.S=S∪St

18. returnTandS；

算法1實現數據匯聚樹的構造以及鏈路調度。算法2、3分別用于實現層到層的調度和段到段的調度。

算法2：LTL 。

Input:Local aggregation nodesAij

Output:Time slottandSt

2. local aggregation nodeAijselect one latest local aggregation node from thei-1 layer;

3. send its data toAi-1,j;

5.St=St∪E″ ;

6.l=l-1;

7.t=t+1;

算法3：STS。

Input:local aggregation nodeAij

Output:Time slottandSt

2. local aggregation nodeAijlocated in theLlayer select one neareast local aggregation nodeAghfrom theL-ωlayer;

3. send its data toAgh;

5.St=St∪E?;

6.t=t+1;

7.L=L-ω;

5 分 析

這一部分首先對算法的正確性進行分析，然后證明算法的有效性。

5.1 正確性

定理1：基于六邊形的分布式數據匯聚調度算法構造了一棵數據匯聚樹，且該算法可以在物理干擾模型下正確地對鏈路進行調度。

證明：算法共三個階段。第一階段是單元格內的數據匯聚，每個單元格內的節點都在指定的時隙向局部匯聚節點發送數據，且僅發送一次。第二階段，每個段的下層局部匯聚節點都將得到的匯聚值傳遞給段首的局部匯聚節點，各層的局部匯聚節點也僅發送一次數據。第三階段，由外到內每段的段首向上一段的段首發送匯聚值，直到將每段的數據都匯聚到匯聚節點。縱觀三個階段，每個階段都由不同的節點發送數據，且每個節點都僅在本階段發送一次，故形成了一棵數據匯聚樹。根據文獻[17]可知，在物理干擾模型中，相距2(X+1)d的兩個單元格之間可以干擾自由地傳輸數據，因此定理成立。

5.2 有效性

定理2：Hexagon-AS算法的數據匯聚延遲上界為O(m)。

證明：首先證明如果單元格中任何兩個節點之間的距離都至少為1，那么在一個邊長為1的六邊形中至多有七個節點，使用文獻[11]中的一個結果來證明。假設U是半徑為r的圓盤中節點間距離至少為1的節點集合，那么

邊長為1的六邊形可以被包含在一個半徑為1的圓盤中，所以

證明完成。

文中算法構造了一棵數據匯聚樹，實現了數據的有效匯聚，并得到了一個延遲上界O(m)。

6 仿 真

對Hexagon-AS算法進行仿真，并將結果與文獻[17]中的Cell-AS算法進行比較。假設網絡部署在一個半徑為100m的圓形區域中，隨機產生0至1 000個傳感器節點，這些節點隨意分布，節點間的距離至少為1。設N0的值設為0.1，α為3和4，β為2、4和6。仿真用C語言編寫，在Matlab7.0中運行。

首先比較不同α和β值下Hexagon-AS算法的數據匯聚延遲。圖3(a)表示當α=3時匯聚延遲隨β值的變化情況。觀察發現隨β的增大匯聚延遲逐漸增大，這是因為當β增大，發送節點的功率不變時，網絡中并發傳輸的節點之間的干擾減小，這意味著并發傳輸的節點數減少，因此匯聚時間增大。圖3(b)表示當α=4時匯聚延遲隨β值的變化情況，與圖3(a)有相同的變化趨勢。

圖3 不同α下的匯聚延遲

圖4給出的是Hexagon-AS算法和Cell-AS算法的比較。圖4(a)表示當α=3時兩種算法得到的匯聚延遲時間，圖4(b)表示α=4時的比較結果。結果顯示，文中算法比Cell-AS算法有更小的延遲時間。

7 結束語

文中分析了基于物理干擾模型的數據匯聚延遲問題，設計了一個分布式延遲最小化數據匯聚算法—Hexagon-AS。首先將網絡用六邊形單元格覆蓋，然后對單元格進行分層、分段，最后對具有相同顏色的單元格進行并發調度，得到了一個O(m)的延遲上界。經理論分析和仿真實驗證明，該算法是有效的。下一步將引入CSMA機制，以期得到更高的數據傳輸成功概率。

圖4 延遲比較

[1] 白永祥.一種LEACH路由協議算法的改進與分析[J].通信技術，2015，48(9):1062-1067.

[2] 張建明,宋迎清,周四望,等.無線傳感器網絡中數據匯聚技術的研究[J].計算機應用，2006,26(6)：1273-1278.

[3]ChenS,WangY,LiXY,etal.Order-optimaldatacollectioninwirelesssensornetworks:delayandcapacity[C]//Procofthe6thannualIEEEcommunicationssocietyconferenceonsensor,meshandadhoccommunicationsandnetworks.Rome:IEEEPress,2009:1-9.

[4]YuB,LiJ,LiY.Distributeddataaggregationschedulinginwirelesssensornetworks[C]//ProcoftheIEEEinternationalconferenceoncomputercommunications.RiodeJanein:IEEEPress,2009:2159-2167.

[5] 朱紅松,孫利民,徐勇軍,等.基于精細化梯度的無線傳感器網絡匯聚機制及分析[J].軟件學報，2007，18(5)：1138-1151.

[6] 王辛果,張信明,陳國良.時延受限且能量高效的無線傳感器網絡跨層路由[J].軟件學報,2011,22(7):1626-1640.

[7] 彭 剛，曹元大，鐘偉軍，等.無線傳感器網絡的數據匯聚機制[J].計算機工程，2006，32(6)：115-117.

[8] 劉文彬，李香寶，付 沙，等.無線傳感器網絡中的改進數據聚集調度算法[J].計算機工程，2014,40(1):93-97.

[9]BoukercheA.Algorithmsandprotocolsforwirelesssensornetworks[M].[s.l.]:Wiley&Sons,2008.

[10]ChenX,HuX,ZhuJ.Minimumdataaggregationtimeprobleminwirelesssensornetworks[C]//ProcofMSN’05.Wuhan:IEEEPress,2005:133-142.

[11]WanPJ,HuangSCH,WangL.Minimum-latencyaggregationschedulinginmultihopwirelessnetworks[C]//ProcofMOBIHOC’09.NewYork:ACMPress,2009:185-194.

[12]XuX,LiXY,MaoX.Adelay-efficientalgorithmfordataaggregationinmultihopwirelesssensornetworks[J].IEEETransactionsonParallelandDistributedSystems,2011,22(1):163-175.

[13]HuangCH,WanP,VuCT.Nearlyconstantapproximationfordataaggregationschedulinginwirelesssensornetworks[C]//Procof26thIEEEinternationalconferenceoncomputercommunications.[s.l.]:IEEEPress,2007:366-372.

[14]LiY,GuoL,PrasadSK.Anenergy-efficientdistributedalgorithmforminimum-latencyaggregationschedulinginwirelesssensornetworks[C]//ProcofIEEEICDCS’11.Genovn:IEEEPress,2010:827-836.

[15] 鄭國強,李建東,周志立.多跳無線傳感器網絡的高能效數據收集協議[J].軟件學報,2010,21(9):2320-2337.

[16]LiXY,XuX,WangS.Efficientdataaggregationinmulti-hopwirelesssensornetworksunderphysicalinterferencemodel[C]//ProcofMASS’09.Macau:IEEEPress,2009:353-362.

[17]LiH,WuC,HuaQS,etal.Latency-minimizingdataaggregationinwirelesssensornetworksunderphysicalinterferencemodel[J].AdHocNetworks,2011,12:52-68.

A Data Aggregation Algorithm of Latency-minimizing Based on Physical Interference Model

WANG Ya，LI Guang-shun

(College of Information Science and Engineering,Qufu Normal University,Rizhao 276800,China)

In the Wireless Sensor Networks (WSN),how to quickly and accurately gather the data collected by sensors to sink node is very important in data aggregation.In the early,researchers mostly focus on the problem of data aggregation under protocol interference model which can’t accurately compute interference between nodes,but the physical interference model can overcome this shortcoming.Therefore,considering that latency-minimizing data aggregation in the physical interference model,a Hexagon-AS algorithm is proposed,and an upper bound of the latencyO(m)isachieved,mofwhichisthelayerofthehexagoninthenetworks.Firstly,thealgorithmproposedcoversthenetworkwithhexagoncells,thencoloringthecells,finallymakingcellswiththesamecoloronconcurrent.SimulationshowsthatHexagon-AShassmallerlatencythantheexistingalgorithm.

wireless sensor networks;data aggregation;physical interference model;latency

2015-10-23

2016-01-27

時間：2016-06-22

國家自然科學基金資助項目(61373027)；山東省優秀中青年科學家獎勵基金項目(BS2014DX005)

王 亞(1991-)，女，碩士研究生，研究方向為無線傳感器網絡；李光順，副教授，研究方向為計算機網絡與通信。

http://www.cnki.net/kcms/detail/61.1450.TP.20160622.0844.024.html

TP

A

1673-629X(2016)07-0080-05

10.3969/j.issn.1673-629X.2016.07.017