基于移动Sink的无线传感器网络能量高效的驻留点路由算法

鲍毅，王占刚

（1安徽工程大学 电气工程学院，芜湖 241000；2湖北科技职业学院 软件工程学院，武汉 430000）

无线传感器网络能够部署在人类无法到达的地方，如野生森林、军事环境、战场等恶劣环境中进行监测，并广泛应用于智慧城市和社区、医疗系统和医疗保健、智能农业等场景.无线传感器网络具有自组织部署、自组织、能量约束、动态网络拓扑、无人值守操作等特性，使得传感数据的处理、通信和管理成为一项具有挑战性的任务［1］.由于传感网中部署的节点能量受限，传感器节点的电池电量更续成为一项艰巨的任务.另外，在多跳机制下，部分节点由于承载数据转发任务，导致距离Sink较近的节点需要更多的能量的开销，导致能量空洞或热点问题.这势必影响整个网络的正常工作，造成网络寿命和服务质量的下降［2］.

移动Sink或移动数据采集器（MDC）的概念被提出，以缓解能量空洞问题并延长网络寿命.在基于移动Sink的WSN中，最基本的任务是确定移动Sink如何从网络中获取数据.其中，一种策略是访问每个传感器节点，通过单跳通信直接获取数据.从根本上讲，这是一个旅行商问题（TSP），其目的是确定可以访问所有传感器节点的最短路径［3］.然而，对于大型网络，生成的路径可能无法满足特定应用程序的延迟方面的限制.因此，需要在延迟约束下实现从传感器节点到移动Sink的多跳数据转发.另外，Sink的移动使网络拓扑结构动态变化，传感器节点有必要知道在哪里转发最终可以传送到移动Sink的数据.

1 相关工作

在部署了移动Sink的无线传感网中，如何提高数据收集效率、延长网络生命周期，以及降低节点的部署、运行成本是研究中需要考虑的几个重要问题.大致而言，所有这些数据采集方法大致包括以下几个阶段：驻留点的选择、区域范围内节点至驻留点的数据转发树的形成以及用于数据采集的移动Sink遍历轨迹的优化.

KASWAN等 人［4］提 出 了 定 期 交 会 数 据 采 集（PRDC）和延迟界约化k均值的方法，将网络划分为若干个簇且使得所有簇头节点至所有数据汇聚节点的跳距最小来优化数据采集过程中的能量消耗.KUMAR等人［5］提出了范围约束聚类数据采集方法（RCCDAM），只考虑簇头节点和驻留点之间的距离，而在选择信道时不考虑传感器节点的能量因素.ALNUNIMI等人［6］提出了基于ferry的数据采集方法（FBDAM），考虑距离和能量因素来选择信道.为了找到在避障情况下的最短路径，NANNAPANENIA等人［7］提出了一种启发式旅游规划算法来实现对移动Sink的有效调度.为了提高网络效率和Sink的利用率，LU等人［8］提出了一种基于簇树的节能路由协议（CTEER），通过规划接收器的移动路径来创建交叉通信区域，在区域内构建以移动接收器为中心的交叉路由树.JAIN等人［9］提出了一种基于非均匀分层分簇和动态路由调整方案，通过簇头的交替选择来分配数据收集过程中的负载.SALARIAN等人［10］设计了高效节能的移动路径选择策略，通过加权驻留规划（WRP）的启发式算法来解决移动Sink对驻留点的遍历问题，提高数据采集效率.

上述基于移动Sink的数据收集方案的提出，对于提高数据收集效率和均衡化网络中所有节点的能量消耗起到了积极作用.但是，Sink的移动性会导致数据收集产生更多的数据延迟，需要在数据的可靠传输和Sink节点移动路径规划等方面综合考虑，以提高网络的可用性.

2 本文方法

2.1 系统模型

假设n个传感器随机部署在D×D的正方形区域，基于移动Sink的传感器网络用M=(S，C，Ψ)来定义，其中，S表示传感器节点集合，且|S|=n；C为驻留点集合，且|C|=m；Ψ表示整个系统的感知区域.移动Sink在驻留点之间移动并收集传感器节点的数据，移动Sink具有无限的能量以支持其在整个网络生命周期内运行.其他假设条件包括：Sink知道传感器节点的所有信息，例如位置，可用能量等；Sink节点有足够的空间来存储收集的数据；Sink节点的移动轨迹上没有障碍物.

移动Sink在驻留点停留的时间按轮次来进行计量，每一轮的最小时间间隔用Δt来表示.整个传感器网络的生命周期被定义为从网络初始化到第一个节点耗尽电量，用L来表示，则：

其中，Tc为移动Sink在第c个驻留点停留的时间.

为了表示第t轮移动Sink的驻留点位置，用变量表示：

根据上述定义，移动Sink在第c个驻留点停留的时间能表示为：

传感器感知物理环境并将数据包传输到移动Sink.每个传感器具有相同的有限初始能量Ei，每个传感器的传感数据速率为λ.移动Sink和传感器节点具有最大的通信半径d0.对于传感器节点i来说，当与节点j的距离dis(i，j)≤d0时，节点之间采用单跳进行通信；否则，采用多跳方式将采集的数据交给汇聚节点.

考虑到所有节点采集的数据通过一棵多跳转发树H转发至Sink节点，假设在第t轮，节点i发送的数据为收到的数据为根据流增强算法［11］，的值可以表示为：

其中，Et为节点剩余能量的向量，且表示第t轮所有节点的分布.

当移动Sink结束当前驻留点的停留而移动至下一驻留点，多跳转发树H将重新生成.对于多跳转发树H中的叶子节点来说，它们只产生数据并不需要承担转发其他节点的数据，将其发送和接收的数据分别记为

对于任意传感器节点来说，能量消耗分为数据发送和数据接收两部分，接收和发送B比特数据包的能量消耗为［12］：

对于任意节点i，在整个网络生命周期其能量消耗能被表示为：

因此，网络生命周期最大化问题能被描述为：

其中，约束条件（8）表示移动Sink在每个候选驻留点允许的停留时间；约束条件（9）表示网络中仅包含一个移动Sink；约束条件（10）表示任何节点在每轮的发送数据一定是包含接收其他节点的数据和自身采集数据之和，Δt表示发送数据两轮之间的时间差；约束条件（11）表示在网络生命周期内节点还存在剩余能量.

2.2 优化算法

蚁群算法（ACO）是一种受自然界真实蚂蚁行为启发的仿生技术［13］.通过在图中寻找最优路径，它在求解组合优化问题和旅行商问题的近似最优解方面表现出了足够好的性能［14］.蚁群算法本质上是一种正反馈机制，它在求解过程中具有随机性、适应性和分布性等特点［15］.它适用于并行计算和精确解.移动Sink的驻留点的选择和路径确定提供了事件驱动无线传感器网络的最佳性能，本文采用蚁群优化算法来对上述网络生命周期最大化问题进行求解.使用蚁群优化算法通过迭代更新蚂蚁的信息素值来生成解，信息素的数量计算为：

其中，其中Lk是第k个蚂蚁的总轨迹距离，μ是一个常数值.

对于节点i到j之间由蚂蚁k更新的信息素值为：

其中，ρ表示信息素的衰减，其取值范围为（0，1）之间.(1-ρ)是单位时间内信息素的蒸发率.K表示算法中使用的蚂蚁总数.τij是所有蚂蚁在节点i到j之间沉积的信息素值.

从节点i中选择另一个节点j时，算法考虑节点的数据转发负载，用wj=Rj/Qj来表示.ηij表示强调启发式数据的重要性，并能从当前的网络情况中获得最佳的驻留点集，用ηij=1/dij来表示.则概率函数被定义为：

其中，Nil表示未被蚂蚁k访问过的节点i的邻居节点.参数α，β和γ分别用来控制信息素值、启发式数据和数据转发负载的相对重要性.

从ψ(Sp)中选择一个可行解是由随机构造引导的，从表达式可以看到，构造的结果受与ψ(Sp)的每个值相关的信息素的影响.节点l表示蚂蚁k尚未访问的节点.每个蚂蚁选择下一个节点作为主流点，概率函数为其返回最高值，并更新当前节点和选定驻留点之间的信息素.

一旦选择了合适驻留点，算法需要计算移动Sink的遍历路径长度.构建移动Sink路径的概率函数为：

如果超过现有的解的遍历路径长度，将从集合C中删除驻留点，并选择另一个概率最高的节点重复上述过程.

3 实验结果与分析

通过MatLab进行了仿真实验，将本文提出的算法与NHCDRA［9］和EMPS［10］等典型算法进行了比较.在传感器网络中，随机采用随机部署的方式，区域大小为400 m×400 m矩形平面，传感器节点在其正常工作状态下以20 bit/s的速度产生数据.传感器节点初始能量为5 J，其发射机和接收机参数设置为：εtr=40 nJ/bit，εmp=100 pJ/bit/m2，εrec=50 nJ/bit.蚁群优化算法中的调节参数α，β和γ分别设置为0.2，0.4和0.4，μ=100.为了验证算法的性能，选取了丢包数、网络生命周期、数据包交付率、端到端时延等指标进行了比较分析.

首先，对不同轮次下的丢包数进行对比.从图1可以看出，在前200轮，三种算法的丢包术相差并不明显.随着网络的运行，丢包数逐渐增大.整体上EMPS算法具有较高的丢包数.其主要原因该算法在转发过程中没有充分考虑时延或最大跳数约束条件，离Sink节点最近的节点作为数据转发的根节点，容易因负载过大导致数据缓冲区溢出.本文提出的算法在驻留点的优化选择中充分考虑了节点的数据负载因素，使得丢包数相对较低.

图1 丢包数的比较Fig.1 Comparison of packet loss

图2为不同节点数下的网络生命周期的比较.本文将网络生存周期定义为无线传感器网络从网络初始化到第一个节点耗尽电量的持续时间.随着节点数的增加，网络生命周期呈上升趋势，节点之间可以通过多跳方式转发数据，能够有效降低单跳远距离传输造成的能量过量消耗.EMPS算法的网络生命周期相比较而言更低，这是因为，随着节点数量的增加数据转发跳数也显著增加，这将导致驻留点附近的节点具有更高的能量消耗并过早死亡.当传感器节点高于200时，我们提出的算法的生存期明显优于其他算法.但随着网络规模的增加，本文提出的算法在网络生命周期上的表现逐渐突出，具有更好的节点存活时间.这说明算法在执行时，移动策略中的驻留点的选择更合理，可以平衡网络中节点的能量消耗.

图2 网络生命周期的比较Fig.2 Comparison of network lifetime

图3为不同节点数量时数据交付率的比较.随着网络规模的增加，本文提出的算法具有更明显的优势，始终保持在90%以上.当网络中的节点密集分布时，需要转发的数据量会显著增大，有效的数据收集方案应该能够通过合理调整移动Sink的移动轨迹和对驻留点的遍历，及时回收各感知节点采集的数据.这样不会导致因溢出或时间延迟约束导致丢包，从而影响数据的及时交付.另外，驻留点的优化选择对于提高数据交付率也起到重要作用.

图3 数据交付率的比较Fig.3 Comparison of data delivery rate

图4显示不同节点数条件下端到端时延的比较.更多的传感器节点意味着来自源节点的更多数据需要转发到驻留点，并且由于多跳传输，数据收集必须等待很长时间.移动Sink节点停留在驻留点附近进行数据收集，也会增加了数据传输的延迟.在实验结果可以看到，本文提出的算法相比NHCDRA算法和EMPS算法都具有更好的性能.随着传感器节点数量的增加，在我们提出的算法中，驻留点选择策略和移动Sink的路径的优化调整可以找到更优的解决方案来实现数据的及时收集处理，有效降低了数据传输延迟.

图4 端到端时延的比较Fig.4 Comparison of end-to-end delay

4 结语

为了提高基于移动Sink的无线传感网的数据收集效率，本文提出了一种基于移动Sink的无线传感器网络能量高效的驻留点路由算法.首先，对数据采集过程中的网络生命周期最大化问题进行建模；其次，提出了基于蚁群优化的算法来求解最优的驻留点集合和移动Sink遍历路径.为了验证算法的性能，选取了丢包数、网络生命周期、数据包交付率、端到端时延等指标，将本文提出的算法与NHCDRA和EMP等典型算法进行了比较.实验结果表明，本文提出的算法能够有效延长网络的生命周期、提高交付率和减少端到端时延.