王 亞，李光順

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

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

王 亞，李光順

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

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

無線傳感器網(wǎng)絡(luò)；數(shù)據(jù)匯聚；物理干擾模型；延遲

0 引 言

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

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

1 相關(guān)工作

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

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

2 網(wǎng)絡(luò)模型

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

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

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

3 網(wǎng)絡(luò)劃分

圖1 數(shù)據(jù)匯聚

圖2 層和段的劃分

4 算法描述

算法的主要思想如下：

第一階段，單元格內(nèi)的調(diào)度。首先在每個單元格內(nèi)選出一個具有最大能量emax=max{ei|vi∈ci,j}的節(jié)點，作為該單元格內(nèi)的局部匯聚節(jié)點，單元格內(nèi)的其他節(jié)點都在給定的時隙內(nèi)，將收集到的數(shù)據(jù)傳送給局部匯聚節(jié)點。為避免節(jié)點間的干擾，給單元格染色，具有相同顏色的單元格需要滿足它們之間的距離足夠遠。文中設(shè)定它們之間的距離至少為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實現(xiàn)數(shù)據(jù)匯聚樹的構(gòu)造以及鏈路調(diào)度。算法2、3分別用于實現(xiàn)層到層的調(diào)度和段到段的調(diào)度。

算法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：基于六邊形的分布式數(shù)據(jù)匯聚調(diào)度算法構(gòu)造了一棵數(shù)據(jù)匯聚樹，且該算法可以在物理干擾模型下正確地對鏈路進行調(diào)度。

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

5.2 有效性

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

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

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

證明完成。

文中算法構(gòu)造了一棵數(shù)據(jù)匯聚樹，實現(xiàn)了數(shù)據(jù)的有效匯聚，并得到了一個延遲上界O(m)。

6 仿 真

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

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

圖3 不同α下的匯聚延遲

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

7 結(jié)束語

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

圖4 延遲比較

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

[2] 張建明,宋迎清,周四望,等.無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)匯聚技術(shù)的研究[J].計算機應(yīng)用，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] 朱紅松,孫利民,徐勇軍,等.基于精細化梯度的無線傳感器網(wǎng)絡(luò)匯聚機制及分析[J].軟件學報，2007，18(5)：1138-1151.

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

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

[8] 劉文彬，李香寶，付 沙，等.無線傳感器網(wǎng)絡(luò)中的改進數(shù)據(jù)聚集調(diào)度算法[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] 鄭國強,李建東,周志立.多跳無線傳感器網(wǎng)絡(luò)的高能效數(shù)據(jù)收集協(xié)議[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)；山東省優(yōu)秀中青年科學家獎勵基金項目(BS2014DX005)

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

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