基于移动汇聚节点延迟容忍的节能策略

匡哲君，师唯佳，胡 亮，周 航

（1.吉林大学 计算机科学与技术学院，长春130012；2.罗格斯新泽西州立大学 教育研究与学术规划处，新布伦斯威克 新泽西州 美国08901；3.吉林大学 数学学院，长春130012）

0 引 言

无线传感器网络的生命周期的定义很多，通常认为无线传感器网络的生命周期是从正常工作到出现一个传感器节点能量耗尽为止为一个无线传感器网络的生命周期。在传感器节点通信的过程中，一般由多个节点进行数据的收集，然后由底向上进行数据的汇聚。也就是说，数据收集后的多个节点向一个或者少部分的汇聚节点发送数据。根据多跳路由的机制，一般由边缘节点进行数据的收集，然后由汇聚节点附近的节点进行转发。在这种过程中容易出现“中心拥挤效应”［1］，也就是通常所说的“能量洞”问题［2］。这种问题是由于汇聚节点附近的邻节点能提前耗尽，使得边缘节点还有能量却无法将数据发送至汇聚节点。文献［3］提出了移动代理的机制，移动代理节点代替静态的汇聚节点能够移动到节点附近进行数据的收发。当移动到汇聚节点附近再将接受到的数据发送到汇聚节点。在这个结构下，节点只需要与移动代理节点进行单跳的数据传输，而移动代理节点对汇聚节点也同样是单跳进行数据的传输。这样就减轻了节点由于作为中继节点所消耗的能量。这种结构是在移动代理节点的能量非常大的假设条件下进行的。文献［4］论证了移动代理的移动规律，通过移动规律和停留时长来延长整个网络的生命周期，其框架应用的网络拓扑结构以网格模式进行考虑，过于单一。文献［5］表明，移动节点的消耗取决于汇聚节点移动的范围和汇聚节点最短的停留时间，并且当移动节点移动到下一站时，模型定义了跳宽；同时，作者提出了一种MILP的方法来取得移动汇聚节点的最优移动路径和最适合的停留时间来保证网络生命周期。文献［6］表明，移动代理在边缘点附近移动可以提高整体网络的生命周期，文中假设如果移动代理节点能够调整整体网络节点的负载平衡，这样可以提高整体网络生命周期；作者以负载中的节点作为移动节点，降低恶劣节点负载不平衡的问题。由于假设环境是在最短路径下进行的，网络生命周期提升的效果并不明显。随着移动汇聚节点的产生，在不考虑监测环境的空间复杂度和节点停留的基础上，很难进行移动路径的规划。文献［7］研究了如何找出移动路径的最短停留时间和停留时间表。如果监测区的停留时间不受到约束，就会成为一个NP 问题。然而停留在一个有限的已知区域，这样问题就可以转化成为一种线型。作者提出一种接近算法，将监测区看作无限的未知区域。这样就能将无限的问题转化为有限的问题，然而一个好的逼近问题需要消耗大量的计算资源及能耗。文献［8－10］在节点功耗管理方面提出了优化的策略。文献［11］提出了一种分簇式自主移动机制，该机制设定汇聚节点单跳邻居节点集的数据流量发生较大变化时，汇聚节点开始移动。文献［12］根据移动的特性，即移动节点只能在若干个小的区域内移动，得出网络生命周期的延长不仅依赖于停留时长，还需要考虑流量。

本文通过应用层对数据传输的延迟容忍级别，利用移动汇聚节点，进行周期性的数据收集。移动汇聚节点延迟容忍策略能够缓解网络中的“能量洞”问题，并且在延迟容忍的基础上，能够很大程度上降低数据传输的能耗，达到延长网络生命周期的效果。

1 汇聚节点能耗模型

1.1 静态汇聚节点

对无线传感器网络能耗进行分析，首先需要了解静态汇聚节点下的能量消耗与数据传输的关系。设传感器节点集合为N。假设所有的传感器节点都是随机散落在以R 为半径的圆形区域内。以圆形区域的中心作为起点，每个节点i以固定比例生成数据di且i的初始能量为Ei。此外，节点能够根据传输距离来调整传输功率。节点i向j发送固定比例的通信量速率Xij，在一个单位时间内所需要的能量可以表示为：

式中：dis（i，j）为节点i与j的欧几里得距离；α和β为非负数常量；e为路径的损耗指数，一般来说，e的范围为2～6，e值的选取主要取决于监测的环境。

单位数据的传输能耗不依赖于链路速率，而是取决于有效的低速率机制。因此，假设相比于无线链路速率，通信量速率Xij足够小。节点i单位时间内接收到节点k 发送的数据能耗可以表示为：

式中：γ为给定的一个常量。

节点i在一个单位时间内总的能耗可以表示为：

1.2 移动汇聚节点

在移动汇聚节点模型中，假设汇聚节点可以在传感器监测区域进行移动，并且可以在特定的区域进行停留来与传感器节点进行数据的收发。假设每一个节点都有相同的传输范围，I 表示为汇聚节点。在本文中，设移动汇聚节点I属于一个特殊的节点（不同于其他节点），可以表示为I ∉N。设L 为汇聚节点停留的位置节点集合。为了提高网络生命周期，汇聚节点没有必要在所有的L位置上进行停留。假设在不考虑汇聚节点移动时间的条件下，为简化问题，可以通过明确的数学解法来进行评估。

在此模型中，节点的访问顺序对网络的整体生命周期并不会带来太大的影响。汇聚节点在一个位置I∈L 的停留时间可以表示为ZI，也就是说汇聚节点使用I时间对传感器节点进行数据的收发。因此，整体的生命周期为当汇聚节点停于I 位置，节点i的下游邻节点可表示为：

移动汇聚节点的停留时间需要根据流量来制定。根据之前静态汇聚节点延长网络生命周期的基本感知数据流量的聚合和静态汇聚节点数据聚合的基本理论，将移动汇聚节点的条件进行迭代。用X（I）ij表示移动汇聚节点在I 站点停留时节点i到j 的数据流聚合。最大网络生命周期可以表示为：

式（7）表示所有的汇聚节点在i位置是流量守恒的。式（8）表明所有的节点i的能耗必须少于或等于初始能量Ei，即能量是守恒的。通过将式（7）乘以ZI，并且用新的参数替换，有：

同理，式（8）可转换为：

2 移动汇聚节点延迟容忍策略

无线传感器网络生命周期最大化是建立在应用层面的延迟容忍条件基础上的。一般将这种模型称之为延迟容忍模型。假设每一个节点能够延迟到移动汇聚节点停留在最有利的位置之后再进行数据的收发，这样使得收发同样数据量时能耗达到最小，从而延长了整个网络的生命周期。

设D 为最大延迟容忍，或者是最高延迟级别。假设在D 个单位时间内移动汇聚节点能够完成所有停留节点的一轮访问，并且在适当的站点进行数据收集，以此为周期进行重复。

延迟容忍模型相比于静态汇聚节点模型和移动汇聚节点模型在延长网络生命周期方面有明显的优势。如图1所示，N1和N2为两个传感器节点，L1和L2为移动汇聚节点的备用站点。为了简化说明，忽略节点收发的能量消耗，并且假设一个单位量的数据传输耗能为收发节点之间距离的平方。在初始环境下，两个节点的初始能量都为100单位量，初始基本感知数据为1bit／s。如果在静态汇聚节点模式下，汇聚节点将处于O 位置并保持不变。那么1bit的数据传输能耗约为4个单位量。也就是说从开始到节点衰竭，其网络周期约为25s。同样的环境，在动态汇聚节点模式下，由于是对称的结构，移动节点会周期性地停留在L1和L2进行数据传输。这种情况之下，每一个节点都需要消耗1个单位或者9个单位能量来传输1bit的数据量。无论移动汇聚节点停留在L1还是L2。也就是说平均能耗约为5个单位量，其网络生命周期约为20s。

图1 静态节点与移动汇聚点的假设Fig.1 Assuming static and mobile sink node

在延迟移动汇聚节点模式下，假设移动汇聚节点在每一个站点都停留1s的时间，且周期性地重复。在此情况下，最大延迟D＝2s。当移动汇聚节点停留在L1位置时，只有N1与汇聚节点进行数据传输，并传输2bit的数据。当移动汇聚节点停留至L2位置时，只有N2与汇聚节点进行数据传输通信，同样传输2bit的数据。也就是说，当移动汇聚节点与N1在L1位置上进行数据传输时，N2只是进行数据的采集并将数据放入缓冲池，等到移动汇聚节点移动至L2时，再将采集来的所有数据发送给汇聚节点。如此一来，每一个节点只需要使用2个单位能量就能传输2bit的数据，其生命周期约为100s。相比于静态汇聚节点和移动汇聚节点模型，网络的生命周期延长非常显著。这是因为节点并不是需要持续地与汇聚节点进行通信的。在移动汇聚节点停留时，每一个节点都需要等待汇聚节点移动至最有利的位置才进行数据的传输。

延迟容忍模型中，可以通过局部子区域的方式对所有节点进行数据收集。设N 为传感器节点集合，RI为N 的子集并且只有RI区域的节点与停留在I 站点的汇聚节点进行数据交换，I ∈L。可以将RI称为站点I 的覆盖区域。所有I站点RI的集合应该为N。也就是说，所有传感器节点都至少能够有一个站点与其进行通信。当节点i在RI的范围内，则节点i就是站点i的区域节点（I∈L）。设r为汇聚节点的适合通信半径。对所有的I属于L 来说，如果dis（i，l）≤r且i∈N，则i∈RI。因此，汇聚节点的通信半径必须足够大，保证至少有一个节点在RI的范围内。r半径的最小值取决于移动汇聚节点停留的位置。

节点i基本感知数据的生成和数据的传输速率在静态汇聚节点和动态汇聚节点模式下是一样的，不会产生数据的堆积。然而在延迟容忍模型中，数据收集的速率与出具传输的速率不一样。当移动汇聚节点没有移动到合适节点i的传输站点，节点i不进行数据的传输，却需要将收集来的数据存储至缓冲区，在周期性产生基本感知数据的同时，等待汇聚节点移动到合适的站点，然后将新旧数据一起传输给汇聚节点。因此，节点i的缓冲区空间应该为Ddi。假设移动汇聚节点按一定顺序访问所有L里的站点1→2→3→…→｜L｜→1…。根据流量移动汇聚节点可能在某些站点不停留，如果网络的生命周期为T，那么实际移动节点工作的时间为TD。缓冲区能够有效地帮助延迟容忍模型来延长网络的生命周期，但是需要根据应用环境的需求来制定不同的缓冲策略。

2.1 子流模式

在此模型中，覆盖区域RI的节点不需要缓存其他节点的转发信息，节点在RI区域接收到其他节点的数据后，将立即发送给相邻节点。在这种模式条件下的每一个节点i需要区分节点i 自身生成的数据和节点接收到其他相邻节点初始生成的数据。

节点i∈N，基本感知数据或子流量的其他节点C ∈RI，C ≠i，则必须接收后尽快地转发出去，可以得到：

在此，定义NI（i）＝R∩N（i，I）。在式（5）里给出了N（i，I）。与移动汇聚节点模式的理论一样，通信流量起源于节点i本身，并且加入了新的决策变量；I∈L，i∈RI），节点i的数据流量守恒可以表示为：

在移动汇聚节点前一次离开后，在缓冲区产生的数据流量需要在当前周期被传输给汇聚节点，并清空缓冲区。可表示为：

基于子流模式的延迟容忍可表示为：

上述是根据周期性产生节点的基本感知数据来进行解决的，与静态汇聚节点模型问题相似，还有一种更为简单、类似的流量聚合方案，它仅限于聚合拥堵数据量I。相 反 地，对 于聚合 方 案 的 可 行 性 解，可 以 将看作汇聚节点停留在I时对每个节点i的支持度。每一个节点i可以分解由基本感知产生的拥堵数据量，其路径流量为。因此，为可行性解。

2.2 队列模式

在队列模式中，传感器节点能够缓存其他节点产生的数据，设移动汇聚节点从I位置移动到I＋1之前，节点i的队列长度为。假设每个节点i在周期开始时的数据量为Ddi，并且队列为当汇聚节点完成一个循环，节点i的队列数据必须清空，即。在此模式下，根据流量守恒其动态的序列长度公式为：能量约束与之前的模式相同，可以通过将代入，并引入新的变量u＝1／T，将优化问题转化成为一个线性问题。这种线性方法也同样适用于子流模式。

这两种模式以公式化的形式表示了缓冲区的两种策略。子流模式缓冲区存储的是节点自身产生的数据，而队列模式的缓冲区允许存储任何数据，队列模式能够根据不同的策略来调整，达到延长生命周期的效果。两种模式可以看作是两种极端，可以根据实际情况进行调整缓冲区策略。在子流模式中最大空间区为节点i的Ddi。而队列模型中的最大缓冲区空间由覆盖区域的总节点数和覆盖面积来决定，其缓冲区需要的空间远远大于子流模型。

3 实验结果

根据静态汇聚节点、移动汇聚节点和延迟移动汇聚节点的策略在网络环境的Matlab下进行了实验。本文尝试了不同的参数，例如节点的数量，可能的接收器的位置和参数的能耗模型的数目。在所有的实验中，本文使用GLPK 求解线性规划问题。实验参数如下：传感器节点数为｛100，200｝，汇聚节点站点数为｛5，6，7，8，9，10，15，20，30｝，路径能源消耗比为｛2，3｝，初始能量为500J，数据收集速率为500bit／s。

根据移动汇聚节点的位置来比较各种模型的网络生命周期。节点的数量设置为100或200，路径损耗指数e为2或3。覆盖区域半径设置得足够大，且总是覆盖整个传感器领域。通过多次循环实验，移动汇聚节点模型和移动延迟容忍模型的生命周期明显比静态汇聚点模型的生命周期长。如图2所示，移动汇聚节点模型的生命周期为静态汇聚节点模型的100%～200%。而移动延迟容忍模型的网络生命周期与静态汇聚模型相比，提高了200%～1000%。此外，可以看出网络生命周期的延长曲线为线性增长，随着节点数量的增加，移动汇聚节点的停留位置增多，算法性能差距可能更大。

图2 相对生命周期对比Fig.2 Comparison of relative lifetime

4 结束语

提出了一种基于移动汇聚节点的方式来延长传感器网络生命周期的策略。实验结果证明，移动汇聚节点模型的生命周期为静态汇聚节点模型的100%～200%。而移动延迟容忍模型的网络生命周期与静态汇聚节点模型相比，提高了200%～1000%。延迟容忍模型相比传统的静态汇聚节点模型，在延长网络生命周期的效果上有显著的提升。然而，随着节点数的增加，汇聚节点的通信半径的增大，延迟容忍模型也存在相应的问题。延迟容忍模型需要大量的缓冲空间对数据进行储存，提高了对节点缓冲空间的要求。因此，如何有效地利用节点缓存空间，以及移动汇聚节点的合理路径规划问题也是今后需要研究的一个重要方向。

［1］Popa L，Rostamizadeh A，Karp R，et al.Balancing traffic load in wireless networks with curveball routing［C］∥Proceedings of the Proceedings of the 8th ACM International Symposium on Mobile ad Hoc Networking and Computing，ACM，2007：170－179.

［2］Li J，Mohapatra P.An analytical model for the energy hole problem in many－to－one sensor networks［C］∥Proceedings of the IEEE Vehicular Technology Conference，IEEE，2005：2721－2725.

［3］Wang Z M，Basagni S，Melachrinoudis E，et al.Exploiting sink mobility for maximizing sensor networks lifetime［C］∥Proceedings of the System Sciences，2005HICSS＇05Proceedings of the 38th Annual Hawaii International Conference on，IEEE，2005：287a.

［4］Luo J，Hubaux J－P.Joint mobility and routing for lifetime elongation in wireless sensor networks［C］∥Proceedings of the INFOCOM 2005 24th Annual Joint Conference of the IEEE Computer and Communications Societies Proceedings IEEE，IEEE，2005：1735－1746.

［5］Shi Y，Hou Y T.Theoretical results on base station movement problem for sensor network［C］∥Proceedings of the INFOCOM 2008 The 27th Conference on Computer Communications IEEE，IEEE，2008：1－5.

［6］Chang J H，Tassiulas L.Maximum lifetime routing to mobile sink in wireless sensor networks［J］.IEEE／ACM Transactions on Networking，2004，12（4）：609－619.

［7］Shah R C，Roy S，Jain S，et al.Data mules：Modeling and analysis of a three－tier architecture for sparse sensor networks［J］.Ad Hoc Networks，2003，1（2）：215－233.

［8］庄伟，宋光明，魏志刚，等.具有机动能力的无线传感器网络节点的设计与实现［J］.吉林大学学报：工学版，2007，37（4）：939－943.Zhuang Wei，Song Guang－ming，Wei Zhi－gang，et al.Design and implementation of a mobile node for wireless sensor networks［J］.Journal of Jilin University（Engineering and Technology Edition），2007，37（4）：939－943.

［9］王毅，张德运，马新新，等.无线传感器网络传感器节点动态功耗管理方法［J］.吉林大学学报：工学版，2008，38（4）：880－885.Wang Yi，Zhang De－yun，Ma Xin－xin，et al.Novel dynamic power management of sensor node in wireless sensor networks［J］.Journal of Jilin University（Engineering and Technology Edition），2008，38（4）：880－885.

［10］孙强，徐晨，黄勋.无线传感器网络移动汇聚节点的研究［J］.通信技术，2008，40（11）：173－175.Sun Qiang，Xu Chen，Huan Xun.Research on mobile sink of wireless sensor network［J］.Communications Technology，2008，40（11）：173－175.

［11］孟中楼，王殊，王骐.分簇式无线传感器网络汇聚节点移动策略研究［J］.华中科技大学学报：自然科学版，2009（6）：67－70.Meng Zhong－lou，Wang Shu，Wang Qi.Research on the moving strategy for mobile sink in cluster wireless sensor networks［J］.Journal of Huazhong University of Science and Technology（Nature Science Edition），2009（6）：67－70.

［12］Basagni S，Carosi A，Melachrinoudis E，et al.A new MILP formulation and distributed protocols for wireless sensor networks lifetime maximization［C］∥Proceedings of the Communications，2006ICC＇06 IEEE International Conference on，IEEE，2006：3517－3524.