李道清,张荆沙
(武昌工学院 信息工程学院,武汉 430065)
无线传感器网络中基于最小延时的数据汇集树构建与传输调度算法
李道清,张荆沙
(武昌工学院 信息工程学院,武汉 430065)
无线传感器网络的数据通信模式问题是目前的研究热点,针对现有的无线传感器网络数据汇集算法延时较大这一不足,对最小延时数据汇集树和传输调度问题进行了研究;提出一种基于度约束的汇集树构建算法(DCAT);该算法按照 BFS 方式遍历图,当遍历到每个节点时,通过确定哪些节点与汇点更近来确定潜在母节点集合;然后,选择图中度数最小的潜在母节点作为当前被遍历节点的母节点;此外,为了在给定的汇集树上进行高效地数据汇集,还提出两种新的基于贪婪的TDMA传输调度算法:WIRES-G 和 DCAT-Greedy;利用随机生成的不同规模的传感器网络,参照当前最新算法,对文中方法的性能进行了全面评估;结果表明,与当前最优算法相比,文中调度算法与文中汇集树构建算法结合起来,可显著降低数据汇集的延时。
无线传感器网络;数据汇集;最小延时;度约束;传输调度
在无线传感器网络的多种应用中,数据由传感器节点采集后发往汇点(即Sink)处,这种通信模式称为汇集模式[1-3]。该模式通过构建以汇点为根并通往汇点的树,然后沿着树向汇点传输报文,进而完成数据汇集。在部分应用中,汇集树上的部分节点接收到子节点的数据后,首先对数据进行汇集,然后再发往母节点,以便降低需要传输的报文数量。数据汇集技术可将汇集操作时传输的报文数量从Ω(n2)下降到O(n)个,极大地节约了网络能耗[4-6]。文献[7]研究了用单位圆盘图表示的传感器网络中的最小延时汇集调度问题(minimum latency aggregation scheduling, MLAS),提出了一种集中式(△-1)近似算法,称为最短数据汇集算法(shortest data aggregation, SDA),其中△表示图中节点的最大度。然而,该算法性能的优劣依赖于网络拓扑结构,可扩展性较差。Huang等人[8]提出一种基于MIS的集中式算法来求解MLAS问题,延时为 23R+△-18 ,其中R表示汇点和其他任意节点的最大距离。然而,该算法在求解MIS的过程中需要节点多次交换信息,时间复杂度较高。
此外,文献[9]提出了称为BSPT均衡式最短路径树)的构建算法和称为WIRES(基于加权增量排序的汇集调度)的算法来实现数据汇集。BSPT 算法给出了数据汇集延时的范围为max{ζi+hi:i=1,2,…,n}的下界,其中ζi和hi分别为指定树中节点i从根节点开始的子节点数量和跳数。它采取宽度优先搜索方式遍历图,然后采用双枝半匹配算法[10]来构建可使延时最小的最短路径树。而WIRES调度算法则将汇集树作为输入,并将树中所有叶节点作为可在单位时间内被调度的合格节点。为每个合格节点计算一个权重,权重越高,表明该节点在当前时隙内被调度的优先级越高。然后挨个考察合格节点,对于在传输时不与先前节点发生干扰的所有节点进行调度。所有节点考虑完毕后,一个轮次完毕,通过删除已被调度的节点,增加从各个子节点接收到数据的母节点来更新合格节点集合。重复上述步骤,直到所有节点被调度一次。然而该方法使用汇集树中非叶相邻节点的数量来进行权重计算,因为节点被调度后从汇集树中删除,所以每一轮次均需重新计算权重,导致数据汇集延时增大,且额外耗费了能量。
针对以上方法的不足,本文提出一种新的汇集树构建算法,称为度约束汇集树(Degree-Constrained Aggregation Tree,DCAT)。此外,我们还提出两种新的调度算法,称为WIRES-G和DCAT-Greedy。通过全面的仿真实验评估了本文汇集树构建算法和调度算法的性能,并与当前最优算法BSPT-WIRES[9]进行了性能比较。结果表明,DCAT算法与WIRES调度算法结合起来可将延时性能提升21%。如果将本文调度算法WIRES-G与DCAT算法结合起来,可实现进一步的性能提升,将这种融合算法称为DCAT-WIRES-G。此外,DCAT-Greedy的性能比BSPR-WIRES高出32%-40%,具体取决于网络规模大小。
本文利用单位圆盘图来模拟无线传感器网络中的数据汇集过程,然后对TDMA调度问题进行研究。如果两个节点互相位于对方的传输范围内,则认为这两个节点连通。沿着图的生成树进行数据汇集。在传输时隙期间必须对链路进行调度,以便使可能发生干扰的链路在不同时隙内传输数据,同时使每个节点在其所有子节点传输完毕后再传输数据,保证数据汇集的有效性。本文采用基于图的干扰模型[11]:如果v1在u2传输范围内,则认为链路 (u1,v1) 和(u2,v2)对接收器v1产生干扰。一次汇集操作的延时,定义为汇点接收到所有节点的数据所需要的时间。
假设节点同步,且共享相同的无线信道。假设所有节点固定布置,传输范围相同且恒定。同时假设干扰半径等于传输半径[12]。时间经过时隙处理,每个节点经过调度后在指定时隙内传输数据。如果在同一时隙内传输数据时不会发生干扰,则两个节点可在同一时隙内传输数据。我们还假设节点具有求取最小值、最大值、求和和计数功能,将n个数据元素作为输入,产生一个元素作为输出。
已知一组传感器节点S= {s0,s1,… ,sn-1} ,其中sn-1表示汇点,每个节点均有一个数据需要传输给汇点。我们希望找到一种传输调度策略,使所有节点在各自子节点传输完毕后自己只需传输一次,便可将所有融合数据发往汇点,同时不发生干扰。用图G=(V,E)表示一个无线传感器网络,s∈V表示汇点,我们为图G定义一个生成树T作为它的有效调度,该树以汇点s为根并通往汇点,对于数据传输任务A:V→Z+,我们要求:
1)vchildren(u)A(u) >A(v) ;
2) (u,v)∈T且 (ω,v)GA(u)A(ω)。
第一个条件可保证每个节点在其子节点传输完毕后才开始传输,保证数据经过融合;第二个条件可保证传输过程未被干扰。图G有效调度A的延时可表示为L(G,A),并定义L(G,A)=maxv∈V{A(v)}。于是,MLAS问题可表示如下:已知图G= (V,E),为图G寻找一种可使延时最小化的有效调度。很显然,这一问题可分为两个阶段:汇集树构建过程,和基于树的调度策略搜索过程。下面对这两个问题进行研究。
本节给出了基于度约束的汇集树构建算法。当对节点的潜在母节点进行选择时,本文算法的主要思想就是选择图中度数最小的节点。原因是潜在母节点的度非常关键,只有对节点进行调度,才能避免受到其母节点在图中其他子节点的干扰,同时避免受到母节点在图中其他相邻节点的干扰。本文算法与 BSPT 算法不同,BSPT 算法通过将节点均匀分布于它们的潜在母节点之间来尽量提高并行化水平。也就是说,该算法尽量降低树中节点的度,并忽略潜在母节点在图中的相邻节点。 DCAT 的步骤为:首先,按照BFS 方式遍历图,当遍历到每个节点时,通过确定哪些节点与汇点更近(少一跳距离)来确定潜在母节点集合。然后,选择图中度数最小的潜在母节点作为当前被遍历节点的母节点。限于篇幅,该算法的具体内容略。
本节给出了两种用于数据汇集的调度算法。第一种算法称为 WIRES-G,是对文献[9]中 WIRES 算法的一种改进:我们在 WIRES 算法中增加一个步骤,以便每个时隙期间调度更多个节点。每一轮次中,新添步骤需要为原来算法无法调度的合格节点匹配新的母节点。WIRES-G 的具体内容请见算法1(G表示贪婪)。工作流程如下。第 5-9 行表示原来 WIRES 算法每一轮次的步骤。第 9 行结束时,S包含经过调度将在时间j发送数据的节点,R包含从S中节点接收数据的节点集合。此时,如果我们继续保持原来的树,则其他所有节点经过调度后传输数据总会与已被调度的节点发生干扰。
算法1:WIRES-G
输入:G=(V,E),s:汇点,v.p:树中v∈V的母节点
输出:G的一个有效调度,其中v.t表示v∈V的传输时间
1:procedure WIRES-G(G;s)
2:∀v∈G.Vvht= 0 //对时隙初始化
3:j=1
4:whiles.t= 0 do
5:L= GETELIGIBLENODES(G)
6: COMPUTEWEIGHTS(L)
7: SORTDECREASING(L)
8:S=R=//发送节点和接收节点集合开始为空
9:SCHEDULENODES(L;S;R)
10:L=LS//将发送节点从合格节点中删除
11: GREEDY-SCHEDULING(L;S;R)
12:j=j+1
13:end while
14:end procedure
15:procedure SCHEDULENODES(L;S;R)
16:for eachu∈Ldo
17:ifu∉N(R)且u.p∉N(S) then //如果u在传
输时不发生冲突
18:u.t=j//通过调度使u在时间j传输
19:S=S∪{u}
20:R=R∪{u.p}
21:end if
22:end for
23:end procedure
24:procedure GREEDY-SCHEDULING(L;S;R)
25: for eachu∈Ldo
26: ifu∉R且u∉N(R) then
27:r= nil //未发现母节点
28: for eachp∈N(u) do //寻找母节点
30:r=p
31: end if
32: end for
33: ifr≠ nil then //如果找到新的母节点
34:p=u.p
35:u.p=r//分配新的母节点
36: if ISELIGIBLE(p) then
37:L=L∪{p}
38: end if
39:u.t=j
40:S=S∪{u}
41:R=R∪{u.p}
42: end if
43: end if
44: end for
45:end procedure
在算法1 的 GREEDY-SCHEDULING 中,我们对之前未被顺利调度的所有合格节点进行迭代。首先,我们考查当前节点p是否已经不再作为接收节点,同时考察该节点在传输数据时是否会对R中的接收节点造成干扰。如果如此,则为p选择一个未被调度且可在时间j传输数据并不发生干扰的相邻节点,同时该相邻节点的度在图中所有类似相邻节点间最小。找到相邻节点后,便将其作为当前节点在汇集树中新的母节点。如果先前母节点未遗留下未被调度的子节点,并且在当前轮次内不作为接收节点,则将其添加到合格节点列表中,原因是它可在时间j被调度(第 36-38 行)。
算法 2:DCAT-Greedy
输入:G= (V,E),s:汇点
输出:G以s为根的生成树,及G的一个有效调度,其中v.t和v.p分别表示v∈V的传输时间和母节点
1:procedure DCAT-GREEDY(G)
2:DCAT(G;s)
3: ∀v∈G.V v.t = 0 //时隙初始化
4:j=1
5: whiles.t= 0 do
6:L= GETELIGIBLENODES(G)
7: COMPUTEWEIGHTS(L)
8: SORTDECREASING(L)
9:S=R=
10: GREEDY-SCHEDULING(L;S;R)
11:j=j+1
12: end while
13:end procedure
本文提出的第二种调度算法称为DCAT-Greedy,具体内容见算法 2。该算法融合了本文的汇集树构建算法DCAT及GREEDY-SCHEDULING 算法,目的是进一步降低延时。DCAT-Greedy 算法首先采用 DCAT 构建一个汇集树。每次迭代时,我们确定哪些节点有资格在此轮接受调度。只有所有子节点均被分配了一个时隙的节点才是有资格被调度的节点(合格节点)。DCAT-Greedy 采用与WIRES 相同的方法计算权重(非叶相邻节点的数量),并根据权重对节点降序排列。然后,GREEDY-SCHEDULING 对所有合格节点进行迭代,在不发生干扰的前提下使尽可能多的节点被调度。
DCAT-Greedy算法与 WIRES-G 有两点不同:(1)它利用DCAT 来构建树;(2)没有调用 SCHEDULENODES。
本文结合小型、中型和大型无线传感器网络对汇集树构建算法DCAT及传输调度算法进行性能评估,通过将节点随机均匀分布于5*5、10*10 和20*20 的地理区域上生成小型、中型和大型网络。节点的传输范围为1,节点的密度范围为8-200,其中密度定义为图中节点的平均度。如果节点间的欧氏距离小于等于传输范围,则认为节点连通。对每个被选密度值,共生成 100 个连通图,对这 100 个图求取平均作为最终结果。
首先,我们单独评估汇集树构建算法。为此我们比较了DCAT-WIRES和BSPT-WIRES的性能,同时衡量了所生成调度方案的延时。如图1所示,网络尺寸20*20,采用WIRES 调度。DCAT 树无论在哪种密度设置下,延时均较低。鉴于篇幅有限,我们在这里只给出大型网络的运行结果,对小型和中型网络具有相同结论。
图1 DCAT 和 BSPT 树的平均汇集延时性能比较
下面我们评估WIRES-G和DCAT-Greedy两种调度算法的性能。图2给出了WIRES-G、DCAT-Greedy和WIRES在小型传感器网络上的性能比较。很显然,DCAT-Greedy对小型网络的性能最优。可以看出,DCAT-Greedy所生成的调度方案的平均延时,要远低于其他算法,当密度设置较高时更是如此。DCAT-Greedy甚至远低于BSPT生成的汇集树的下界。当密度为 200 时,DCAT-Greedy 的性能比排名第二的算法DCAT-WIRES-G高出25% ,比先前最优算法BSPTWIRES 高出近 40%。此外,用百分比表示的性能增益随着密度稳定上升。鉴于篇幅所限,对中型网络的运行结果类似,此处略。我们可以看出,无论在哪种情况下,WIRES-G均可降低调度方案的延时,且与采用的树构建算法无关;WIRES 无法实现这一性能。BSPTWIRES-G 和 DCAT-WIRES的性能比较接近,前者略优于后者。因此,无论是采用本文新提出的调度算法IRES-G,还是新提出的树构建算法DCAT-Greedy,均可实现性能提升。DCAT-WIRES-G 的性能优于其他算法,但低于DCAT-Greedy,且密度越大,性能增益越大。
图2 网络规模为 5*5 时平均汇集延时
图3 网络规模为 20*20 时平均汇集延时
图3给出了调度算法对大型传感器网络的性能。结果特点与上文类似。然而,几乎在所有密度设置下,DCAT-WIRES 的性能均优于BSPT-WIRES-G。实际上,对中等密度水平,DCATWIRES-G的性能比BSPT-WIRES-G高出15%。DCAT-reedy 和DCAT-WIRES-G的性能相近,但当密度在15到75之间(含)时,DCAT-WIRES-G 略优于DCAT-Greedy。与BSPT-IRES相比,DCAT-WIRES-G的性能提升了34.66%,而DCAT-Greedy相对于BSPT-WIRES 提升了32.25%。请注意,DCAT-Greedy 结果的标准差低于DCAT-WIRES-G(4.48 vs 5.35)。
为了更好理解性能特点,我们考察了图中节点度与汇集树中子节点平均数量之间的关系。图4给出了密度为30时中等随机网络下的关系。可以看出,各种基于DCAT的算法为度数较高的节点分配的子节点数量很少,这与我们预期相一致。DCAT-Greedy 算法为低度节点分配的子节点数量最多,为高度节点分配的子节点数量最少。这也是该算法在实验中表现优异的原因。对高密度设置具有类似特点。
图4 图的度数与汇集树子节点平均数量间的关系
另外,我们还考察了汇集树中子节点数量最多的节点所处位置。 图 5 给出了中等规模网络在密度为30 时的运行结果 。可以看出,汇点(距 离为0 的节点 )在除了DCAT-Greedy 的各种算法下,子节点数量均较高。这是因为我们开始时采用最短路径树。因此,所有与汇点相距一跳距离的节点将是汇点的子节点。DCAT-Greedy不存在这个问题,因为它为了同时调度尽可能多的节点而修改了初始树。此外,我们发现,如果使度较高的节点与树顶较近,往往会导致延时上升。这是因为与汇点的距离近了,可供选择的节点少了,并行化的概率便会降低。使度较高的节点位于树的底层,也不利于性能提升, 因为只有当所有节点传输完毕才能使数据向上传输,这解释了为何对密度中等的大型网络,DCATWIRES-G 的性能要优于DCAT-Greedy。为此,一种可能的思路是设计一种将上述两种算法综合起来的混合算法来提升面对大型传感器网络时的性能。例如,对树的底层采用 DCAT-WIRES-G 算法,对树的高层采用 DCAT-Greedy 算法。
图5 汇集树中度数较高节点的位置( 密度为 30)
本文研究了WSN 中进行TDMA 调度时的数据汇集问题,提出一种新的汇集树构建算法及两种新的调度算法。与当前最优算法相比,如果将本文提出的汇集树构建算法与调试算法结合起来,可显著降低延时。在下一步工作中,我们研究的重点主要包含两个方面:1)在多种应用场景下分析数据汇集可靠性与汇集树构建以及调度算法之间的关系,以进一步提高数据汇集的质量; 2)基于压缩感知理论,分析数据汇集树的构建过程对于延长网络生命周期的影响,进而提出一种可提高网络生命周期的基于压缩感知的数据汇集算法。
[1] Bagaa M, Younis M, Djenouri D, et al. Distributed low-latency data aggregation scheduling in wireless sensor networks [J]. ACM Transactions on Sensor Networks (TOSN), 2015, 11(3): 49-60.
[2] 石为人, 唐云建, 王燕霞. 基于拥塞控制的无线传感器网络数据汇集树生成算法[J]. 自动化学报, 2010, 36(6): 823-828.
[3] Yousefi H, Malekimajd M, Ashouri M, et al. Fast aggregation scheduling in wireless sensor networks[J]. IEEE Transactions on Wireless Communications, 2015,14(6): 3402-3414.
[4] Liu X Y, Zhu Y, Kong L, et al. CDC: Compressive data collection for wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(8): 2188-2197.
[5] 杨 庚, 李 森, 陈正宇, 等. 传感器网络中面向隐私保护的高精确度数据融合算法 [J]. 计算机学报, 2013, 36(1): 189-200.
[6] 邱立达, 刘天键, 傅 平. 基于稀疏滤波的无线传感器网络数据融合[J]. 电子测量与仪器学报 , 2015, 29(3): 352-357.
[7] Guo L, Li Y, Cai Z. Minimum-latency aggregation scheduling in wireless sensor network[J]. Journal of Combinatorial Optimization, 2016, 31(1): 279-310.
[8] Huang S C H, Wan P J, Vu C T, et al. Nearly constant approximation for data aggregation scheduling in wireless sensor networks[A].26th IEEE International Conference on Computer Communications(INFOCOM)[C]. Anchorage, Alaska, USA: IEEE Press, 2007: 366-372.
[9] Malhotra B, Nikolaidis I, Nascimento M A. Aggregation convergecast scheduling in wireless sensor networks[J]. Wireless Networks, 2011, 17(2): 319-335.
[10] Harvey N J A, Ladner R E, Lovász L, et al. Semi-matchings for bipartite graphs and load balancing[J]. Journal of Algorithms, 2006, 59(1): 53-78.
[11] Incel Ö D, Ghosh A, Krishnamachari B, et al. Fast data collection in tree-based wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2012, 11(1):86-99.
[12] Yao Y, Cao Q, Vasilakos A V. EDAL: An energy-efficient, delay-aware, and lifetime-balancing data collection protocol for heterogeneous wireless sensor networks[J]. IEEE/ACM Transactions on Networking, 2015, 23(3):810-823.
Data Aggregation Tree Construction and Transmission Scheduling Algorithm Based on Minimum Latency in Wireless Sensor Networks
Li Daoqing,Zhang Jingsha
(School of Information Engineering, Wuchang Institute of Technology, Wuhan 430065, China)
Data communication problem in wireless sensor networks is the research hotspot at now,aiming at the shortcomings of the larger delay at the existing data aggregation algorithms in wireless sensor networks, the problem of the minimum latency data aggregation tree and transmission scheduling is studied, and an aggregation tree construction algorithm based on degree constraint is proposed(DCAT). It works by traversing the graph in a BFS manner. As it traverses each node, the set of potential parents is determined by identifying the nodes that are one-hop closer to the sink. The potential parent with the lowest degree in the graph is selected as the parent for the currently traversed node. Furthermore, two new approaches based on greedy for building a TDMA transmission schedule WIRES-G and DCAT-Greedy is proposed to perform efficient aggregation on a given tree. the evaluation to the performance of our algorithms is given through extensive simulations on randomly generated sensor networks of different sizes and the comparison to the previous state of the art is given. the results show that both our new scheduling algorithms when combined with our new tree-building algorithm obtain significantly lower latencies than that of the previous best algorithm.
wireless sensor networks; data aggregation; minimum latency; degree constraint; transmission scheduling
2016-07-01;
2016-07-17。
李道清(1963-),男,湖北京山人,硕士,副教授,主要从事传感器网络、数据采集与处理方向的研究。
1671-4598(2016)12-0147-04
10.16526/j.cnki.11-4762/tp.2016.12.042
TP393
A