多移动汇聚节点的无线传感网中基于服务质量的能耗

王漫漫，束永安

(安徽大学 计算机科学与技术学院，合肥 230601)

0 引言

无线传感技术已经被广泛应用到不同的领域，例如健康监测、军事和环境监测与跟踪。由于传感器网络节点部署密度大、环境复杂、节点体积小、电池容量有限，所以通过最优化能量消耗来有效延长网络生命周期是无线传感网络需要解决的一个问题。另外，针对传统Ad Hoc网络提出的服务质量(Quality of Service, QoS)协议都存在由端到端路径发现和资源预留引起的大量开销，因此，它们不适用于资源受限的无线传感器网络。为此，专门设计了一些机制为无线传感网(Wireless Sensor Network, WSN)提供QoS服务。在这里，主要集中在时延和数据完整性的度量上。

在能耗方面，文献[1-2]提出通过利用移动汇聚节点来延长无线传感网的生命周期。该方法通过对移动汇聚节点路径的控制，使得在延长传感网生命周期上有明显的效果；然而，该方法虽然简单，易于实现，但是不可控、性能较差，因此，文献[3]主要通过确定移动汇聚节点的移动的最佳轨迹来延长无线传感网络的网络生存时间。在该类型中，主要存在两个问题。第一，移动汇聚节点必须经过预先确定的特殊位置或特殊节点。第二，在移动节点快速移动的过程中，需要确定移动汇聚节点移动的速度和轨迹。以前的研究表明可以通过数学模型化来解决最佳移动轨迹。另外，在移动轨迹方面，文献[4]还提出了VGDRA(Virtual Grid-based Dynamic Routes Adjustment)方法，该方法通过将网格区域划分为同样大小的网格，从而简单而精确地确定移动汇聚节点的轨迹，因此虚拟骨干网是由格头节点组成的网络。该方法主要是由网格内的传感器节点将数据传送至格头节点，格头节点再通过虚拟骨干网将数据路由至移动汇聚节点，但是，该方法使得数据包经过较长的路径传输至移动汇聚节点，浪费较多的能量。为此，文献[5]提出了GLRM(Grid-based Load-balanced Routing Method)方法，该方法利用文献[4]类似的分簇方法，区别是该方法仅把数据包路由至边界节点，再等待移动汇聚节点移动至该区域内进行数据包传送，从而节省了能量。

在服务质量方面(QoS)，文献[6]提出了ReInforM(Reliable Information forwarding using Multiple paths)。该方法通过采用动态数据包状态的概念来控制所需路径的可靠性，但是，缺点在于该方法需要知道全局拓扑架构。因此，文献[7]提出LIEMRO(Low-Interference Energy-efficient Multipath ROuting protocol)，该方法在网络运行过程中，根据最新感知的路径质量，利用动态路径维护机制监测活动路径的质量和调整该路径数据包的注入率；然而，它并没有根据活动节点的缓冲容量和服务速率估计和调整活动路径的流量。

于是，文献[8]提出LOCALMOR(LOCALized MOdular Routing)，该方法考虑了时延、可靠性和能耗。该方法根据需求将输入的数据包分成三个队列，然后把完整性要求高的数据包发送到主汇聚点和次汇聚点，从而造成很大的开销。在[8]的基础上，文献[9]提出了一种基于两跳邻居信息的梯度路由机制来提高实时性能，该方法中的路由是由源节点到汇聚节点的跳数信息和两跳信息决定的。文献[10]提出了IDDR(Integrity and Delay Differentiated Routing)算法，该算法通过引入引力域的概念，并具体介绍深度引力域和队列引力域，通过该方法将不同要求数据包选择最合适的路径传输至汇聚节点，从而满足了数据包的时延要求和完整性要求，该方法在整体性能上取得进一步的提升。

针对无线传感器网络，如何设计能够提供数据完整性和时延敏感性要求，同时节省能耗的路由协议，是一个极具挑战性的问题。本文的主要工作在于引入多移动汇聚节点的机制,提出一种多移动汇聚节点考虑服务质量的算法——时延敏感和数据完整性(Multi-Sink Time Sensitive Data Integrity, MSTSDI)算法。首先，将网络按照K-means聚类方法分成合适的自治区域，再给每个自治区域分配一个移动汇聚节点；然后利用支持向量回归(Support Vector Regression, SVR)方法确定移动汇聚节点的轨迹；最后引入深度引力域和队列引力域采用Improved-IDDR算法对数据包进行传送，从而提供高完整性和时延敏感的服务。

1 系统场景及模型

本文提出的算法的系统模型如图1所示，系统所设场景为由N个随机部署的传感器节点组成的无线传感网络。该网络中数据仅由传感器节点产生，移动汇聚节点不产生数据。网络中只有汇聚节点移动，传感器节点会根据传感器节点之间的距离调整传输功率使其相一致。另外，移动汇聚节点没有资源限制。在该网络中，每个传感器节点都有两种模式：监视和发送。若传感节点捕获事件，则将状态传感节点改变至发送状态；处于发送节点的传感器节点将会把数据发送至移动汇聚节点。由于移动汇聚节点的速度是有限的，在大规模无线传感器网络中收集数据是不切实际的，因此引入多移动汇聚节点机制。首先，采用K-means方法将无线传感器网络划分为m个自治区域，Zi,i=1∶m，然后给每个自治区域分配一个汇聚节点。其中每个区域由n个随机部署的无线传感器节点Si，i=1∶n和一个移动汇聚节点组成的。该移动汇聚节点以有限的恒定速度V移动。

图1 系统模型图 Fig. 1 Diagram of system model

2 算法总体流程

当该无线传感网部署完成后，所有传感节点进入监测状态。当传感节点捕获事件，将状态转换为发送状态，然后传感器节点将感知的数据发送到该自治区域的移动汇聚节点。

该算法的总体流程如图2所示，主要分为3部分：1)利用K-means聚类算法将该无线传感网聚类成合适的自治区域。2)利用SVR数学模型找出移动汇聚节点的最佳轨迹。3)引入引力域，利用Improved-IDDR算法将时延敏感和数据完整性要求高的数据包传送至移动汇聚节点，普通数据包则采用“坐等算法”。

图2 MSTSDI流程 Fig. 2 Flow chart of MSTSDI algorithm

3 MSTSDI算法各环节设计

3.1 生成自治区域

由于移动汇聚节点的速度和无线传感节点的传输范围是有限的，因此，在大规模的无线传感网中及时有效地收集数据是不现实的，于是，将无线传感网中分成若干个自治区域。

在传感器网络部署阶段，基站向所有传感器节点广播信标信号。传感器节点通过接收信号强度计算到基站(Base Station, BS)的距离。首先，根据节点密度，BS从网络中确定K个传感器节点作为每一个自治区域的平均值或中心值；其次，对于剩余的每个传感器节点，计算其与各自治中心的距离，将它赋给最近的自治区域；然后，重新计算每个自治区域的平均值。这个过程不断重复，直到准则函数收敛。通常采用平方误差准则，其定义如下：

(1)

其中：E是该自治区域中所有传感器节点的平方误差的总和，p是自治区域中的传感器节点，mi是每个自治区域的平均值。该目标函数使生成的自治区域尽可能地紧凑独立，该方法使用的距离是欧几里得距离。K-means聚类算法的流程如下：

1)根据节点密度选择K个传感器节点作为初始的自治区域的中心。

2)根据自治区域的平均值，将其余每个传感器节点划分至距离最近的自治区域。

3)更新自治区域的平均值，即每个自治区域对象的平均值。

4)重复上述步骤，直到自治区域中的传感器节点基本稳定，不再发生变化即可。

3.2 确定最佳轨迹

如引言所述，为了避免发生网络空洞的现象，从而使网络生命周期最大化，因此需要确定移动汇聚节点的最佳轨迹，下面利用SVR方法来确定移动汇聚节点的最佳轨迹。

将传感器节点划分为自治区域以后，采用SVR的方法找出移动汇聚节点的最佳轨迹。假定有一组传感器节点目标对{(xi,yi)},xi∈Rn,yi∈Rn,i=1∶j，线性SVR通过训练找出线性函数F(x)=φTxi+θ的φ和θ。对于所有的训练数据，该线性函数与实际获得的目标yi偏离至多为ε。因此，需要最小化欧几里得范数，它可以写成如下凸优化问题：

(2)

满足：

yi-φTxi-θ≤ε； ∀i

(3)

yi-φTxi-θ≥ε； ∀i

(4)

其中:φ和θ是自由变量，用来确定轨迹方程。

(5)

满足：

yi-φTxi-θ≤ε+ξi； ∀i

(6)

(7)

接下来，采用拉格朗日乘子法，则有：

(8)

满足：

λi≥0；i=1,2,…,n

(9)

(10)

1-yi(xiφT+θ)≤0；i=1,2，…,n

(11)

(12)

消去φ之后得：

(13)

可知，适用拉格朗日乘子法和KKT条件以后，求φ和θ的问题转换为求拉格朗日因子的问题λ的问题。

3.3 使用Improved-IDDR算法将数据传送至移动汇聚节点

如引言所述，在无线传感网中，针对传统Ad Hoc网络提出的服务质量(QoS)协议都存在由端到端路径发现和资源预留引起的大量开销，因此它们不适用于资源受限的无线传感器网络。针对该问题，提出Improved-IDDR算法。

3.3.1 引力域的概念

在确定移动汇聚节点的最佳轨迹以后，将采用Improved-IDDR算法来传输数据包。该算法通过减少时延敏感数据包的路径长度来降低端到端的时延，同时使数据完整性要求高的数据包通过负载低的路径来提高数据包的完整性。

该算法引入引力域模型作为数据传输的模型，即将数据包的传输过程看作是类似于水流从碗的表面流向碗底的过程，那么数据包的传输轨迹即是由作用于数据包上的力决定的。

(14)

深度差[DA(t)-DB(t)]∈{-1，0，1}，因为两个节点之间的跳数多于一跳的话就不是邻居节点。

(15)

可以发现，节点B缓存的数据包越少，队列域力就越大。因此，被这个队列域驱动，包将会绕过负载比较重的区域被提交到轻负载的区域。

(16)

假设α=0，只有队列域工作，它不能保证由节点产生的数据包最后被传送到汇聚节点，因此，让α>0。

3.3.2 包的权值以及α值和β值

每个数据包头部含8位的权值，高4位表示时延敏感度的等级，低4位表示数据完整性的等级。高4位权值越大，则数据包的时延越敏感；低4位权值越大，则数据包的完整性要求越高。Improved-IDDR用权值来计算不同的引力域斜率：

(17)

(18)

0xf0是高四位权值的最大值，0x0f是低四位权值的最大值。较大的α表示深度引力域的权值较大，该数据包很难被踢出最短路径队列；较大的β表示队列引力域的权值较大，该数据包会沿着负载小的路径传输数据包。Improved-IDDR选择较短路径传输高四位权值较大的数据包，从而降低端到端的时延，选择负载小的路径传输低四位权值较大的数据包来提高数据包的完整性。

3.3.3 “坐等”算法

在MSTSDI算法中，采用“坐等”方法传输普通数据包。首先把离移动汇聚节点轨迹最近的左右节点定义为边界节点。当传感器节点产生了普通的数据包，会沿着如图3所示的路径传输，将数据包传输到该行的边界簇头节点，直到汇聚节点移动至距该边界格头节点最近时进行传输。

图3 “坐等”算法图 Fig. 3 Diagram of “wait” algorithm

3.3.4 Improved-IDDR算法

Improved-IDDR在节点i的主要算法步骤如下。

1)如果节点i的队列不空，则队列头部数据包P的α和β为：

2)W(i,b)(t)={βQi(t)+αDi(t)-[βQb(t)+αDb(t)]}其中b∈Ωi[n]。

3)选择{W(i,b)(t)}max为最大值的邻居节点b为下一跳。

4) 节点i发送数据包P。

5) 如此循环，直至数据包发送至汇聚节点。

3.4 复杂度分析

假设该无线传感网中有N个传感器节点，并且被分为K个自治区域，那么每个自治区域的节点个数平均为N/K。自治区域的建立阶段分为控制数据广播、选择自治区域的中心和网络配置。在控制数据的广播阶段，每个传感器节点的控制信息包括自身ID号的HELLO包，共有N个数据包。基站收到所有的信息包之后，在网络配置阶段，会以泛洪的方式发送一个数据包，使得网络节点了解网络的整体情况。

另外，该网络的传感器节点会根据网络的整体情况从N个传感器节点选择K个传感器节点作为初始的中心节点，而对于剩下的传感器节点，则根据它们与这些中心节点的距离将它们分配给距离最近的中心节点。然后，重新计算每个新的中心节点，直到标准测度函数收敛。因此，该算法是一种基于划分的归类算法，算法快速简单，对大数据有较高的效率，并且是可伸缩的，时间复杂度趋于线性为O(NKt)，t是迭代的次数，其中K≪N,t≪N，该算法的空间复杂度为O(N*h),其中N为传感器节点的个数，h是每个传感器节点特征个数。

4 性能仿真与分析

4.1 仿真场景与参数设置

为了验证所提算法的有效性，在Matlab中进行了仿真实验，场景设置：400个传感节点被随机部署在400 m×400 m的正方形区域，表1为该算法设置的实验仿真参数。

表1 实验中所使用的仿真参数Tab. 1 Simulation parameters used in the experiment

4.2 仿真结果分析

参数α和参数β分别代表数据包的时延敏感度的等级和数据完整性的等级，因此，这两个参数在该算法起着非常重要的作用。为了探讨参数α和参数β对该算法的影响，通过设置不同的权值，进而产生不同的参数值，进行一系列的仿真实验。图4所示为不同应用场景下，三种算法在初始能量相同的情况下运行相同轮数时所剩余的能量图。可以看出，这三种算法随着运行的轮数增加，所剩余的能量不断降低。在各个场景中，新算法所剩余能量最多，GLRM次之，低功耗自适应集簇分层型协议(Low Energy Adaptive Clustering Hierarchy protocol, LEACH)最少。原因在于，GLRM采用三个参数的方法选择簇头，因此，在给定的时间内，可以比LEACH节省更多的能量。而本文所提出的算法，针对普通数据包采用“坐等”算法传输数据包至移动汇聚节点。该算法可以使数据包经过最短的路径至移动汇聚节点，节省最多的能量。针对时延敏感的数据包则引入深度引力域，立即采用最短路径传送数据包至移动汇聚节点，经过较短的路径，较短的时间传送至移动汇聚节点，节省较多的能量。针对数据完整性较高的数据包，则引入队列引力域，将数据包经过负载较低的路径将数据包传送至移动汇聚节点。所以，该算法比其他两种算法所剩余的平均能量要高。

图4 三种算法剩余能量随运行轮数的变化曲线 Fig. 4 Relationship between residual energy and rounds

平均时延和包丢失率随参数α和参数β的性能变化曲线如图5和图6所示。

从图5可以看出，在不同的应用下，随着α的增加，平均时延逐渐减小。这是因为随着α的增大，说明数据包的时延敏感等级逐渐增加，该数据包将通过最短路径传输至移动汇聚节点。所以，每个应用都会随着α的增加，数据包的时延会降低。从图6可以看出，在不同的应用下，随着β的增加，丢包率逐渐降低。这是因为随着β的增加，说明数据包的数据完整性等级逐渐增加，该数据包将通过负载比较低的路径被传输至移动汇聚节点。所以，每个应用都会随着β的增加数据包的丢包率降低。

图5 时延随α的变化曲线 Fig. 5 Relationship between end-to-end delay and parameter α

图6 丢包率随β的变化曲线 Fig. 6 Relationship between packet loss rate and parameter β

平均能耗随参数α和β的性能变化曲线如图7。从图7可以看出，在不同的应用下，随着α的增加，能耗逐渐减少。这是因为随着α的增大，说明数据包的时延敏感度等级逐渐增加，该数据包将通过较短的路径被传送至移动汇聚节点，因此该数据包会经过较少的跳数到达移动汇聚节点，从而消耗较少的能量。

图7 能耗随α的变化曲线 Fig. 7 Relationship between energy consumption and parameter α

5 结语

本文分析了传统的无线传感网所面临的挑战，特别是路由策略在减少传感器节点能耗的同时，不能兼顾数据包的时延敏感性和数据完整性。针对该问题，本文进行了多移动汇聚节点关于QoS的能耗研究。本文通过采用多移动汇聚节点的机制，避免能量空洞的发生。首先，将该传感网通过K-means聚类方法分成多个自治区域；然后，采用SVR方法找出移动汇聚节点的最佳轨迹；最后，采用Improved-IDDR算法传输数据包，使得数据完整性高的数据包经过低负载的路径传输至汇聚节点，使得时延敏感的数据包经过较短的路径传输至汇聚节点。实验结果表明，MSTSDI算法利用引力域比普通的路由策略有更好的节能性，并达到较好的服务质量的要求，证明了该路由策略的有效性。下一步，主要综合考虑研究在多移动汇聚节点的情况下，如何使用分布式算法确定最佳轨迹，以及如何使用确定最佳的多跳传输方案从而实现多目标的优化策略。

参考文献(References)

[1] LUO J , HUBAUX J P. Joint sink mobility and routing to maximize the lifetime of wireless sensor networks: the case of constrained mobility [J]. IEEE/ACM Transactions on Networking, 2010, 18(3)：871-884.

[2] LI Z, LI M. WANG J, et al. Ubiquitous data collection for mobile users in wireless sensor networks [EB/OL]. [2017- 03- 09]. http://www3.ntu.edu.sg/home/limo/papers/Mobile-INFO11.pdf.

[3] TASHTARIAN F, HOSSEIN Y M M. SOHRABY K, et al. On maximizing the lifetime of wireless sensor networks in event-driven applications with mobile sinks [J]. IEEE Transactions Vehicular Technology, 2015, 64(7): 3177-3189.

[4] KHAN A W, ABDULLAH A H, RAZZAQUE M A, et al. VGDRA: a virtual grid-based dynamic routes adjustment scheme for mobile sink-based wireless sensor networks [J]. IEEE Sensors Journal, 2015, 15(1): 526-534.

[5] LIU Q, ZHANG K, SHEN J, et al. GLRM: an improved grid-based load-balanced routing method for WSN with single controlled mobile sink [C]// Proceedings of the 2016 18th International Conference on Advanced Communication Technology. Piscataway, NJ: IEEE, 2016: 34-38.

[6] DEB B, BHATHATNAGAR S, NATH B. ReInForM: reliable information forwarding using multiple paths in sensor networks [C]// LCN ’03: Proceedings of the 28th Annual IEEE International Conference on Local Computer Networks. Washington, DC: IEEE Computer Society, 2003: 406.

[7] RADI M, DEZFOULI B, BAKAR K A, et al. Interference-aware multipath routing protocol for QoS improvement in event-driven wireless sensor networks [J]. Tsinghua Science and Technology, 2011,16(5): 475-490.

[8] DJENOURI D, BALASINGHAM I. Traffic-differentiation-based modular QoS localized routing for wireless sensor networks [J]. IEEE Transactions on Mobile Computing, 2010,10(6): 797-809.

[9] QUANG P T A, KIM D S. Enhancing real-time delivery of gradient routing for industrial wireless sensor networks [J]. IEEE Transactions on Industrial Informatics, 2012, 8(1): 61-68.

[10] ZHANG J, REN F, GAO S, et al. Dynamic routing for data integrity and delay differentiated services in wireless sensor networks [J]. IEEE Transactions on Mobile Computing, 2015, 14(2): 328-343.

[11] 冯晓蒲,张铁峰.四种聚类方法之比较[J].微型机与应用,2010,29(16):1-3.(FENG X P, ZHANG T F. Comparison of four clustering methods [J]. Microcomputer & Its Applications, 2010,29(16):1-3.)

This work is partially supported by Natural Science Foundation of Anhui Province (1408085MF125).

WANGManman, born in 1989, M. S. candidate. Her research interests include wireless sensor network.

SHUYong’an, born in 1966, Ph.D., professor. His research interests include wireless sensor network, software defined network, next-generation network.