基于移动节点数据收集路径规划的整数线性规划模型*

满存金，杜庆治，黄冰倩

（昆明理工大学 信息工程与自动化学院，云南 昆明 650500）

0 引 言

无线传感器网络（Wireless Sensor Network，WSN）由许多传感器节点组成，优点在于节点成本和功耗较低，且形成的网络拓扑结构具有自组的特点，通过节点和节点可进行有效的信息传递，已广泛应用于许多领域，如军事、航海、自然科学、森林保护以及自然灾害监测等领域。应用过程中，把这些有用的数据高效收集是研究的重点。在一定范围内，节点具有感知和监测的功能，随即将一些数据传给特定的基站和节点融合处理[1]。

一般情况下，节点的通信半径为几十米，且受节点容量、通信能力和计算的能力的影响。在非常大的WSN中，在范围区域边缘的传感器节点必须需要多跳转发，才能将大量数据传输给Sink进行处理。这需要大量的能耗，且一些节点在经过许多次转发后易导致数据失效或丢失[2]，从而缩短网络生存的时间。

为了解决WSN中节点能耗特别快的问题，一些研究人员运用移动的节点当做数据的收集器，这样传感器节点就可以将大量感知的数据直接发送给移动节点。移动节点则可以直接处理数据或者返回给Sink，显然这种方法可以解决能耗量大的问题。但是，移动节点的移动速度要远远小于节点和节点之间的无线信息的传递速度。在一些危险的环境下，对数据的实时性要求较高，如森林火灾监控，需要低能耗和快速地将感知信息传送给基站进行处理分析[3]。所以，低能耗、低延时、最优化成为研究的重点。

本文要解决的问题是网络节点能耗和数据收集[4]延迟的最优化问题，即在特定转发跳数的情况下，研究从节点集合中如何选取一部分节点作为停靠节点，使移动节点对这些停靠节点的位置进行访问并收集数据时，路径长度最短。因此，本文提出基于移动节点数据收集路径规划的整数线性规划模型。

1 网络模型

假定有N个传感器的节点均匀分布在边长为M的正方形目标区域中。在该目标区域的中间位置存在一个固定的Sink，可以定期从区域中的传感器节点收集数据。整个无线传感器网络[5]组成一个连通图G(V,L)，其中V={v1,v2,v3,…,vn}表示所有传感器节点的集合，n表示节点数量；L={l1,l2,…,lm}表示节点间边的集合，即两个节点之间能相互通信，m表示边的数量。

2 相关定义

定义1 收集树：在网络中节点转发跳数为h的情况下，构造的多棵高度不超过h的树。

定义2 转发跳数：网络中收集树的最大树高，用于限制网络中节点的多跳传输。

定义3 汇集点：将网络中以收集树为根的节点称为汇集点。

定义4 停靠节点：移动节点在数据收集过程中的停靠位置。

定义5 网络生命周期：在WSN中，第1个节点死亡时的存活轮数称为无线传感网的生命周期。

定义6 节点生命周期：节点vi在树T中能存活的轮数[6]：

其中，C(vi)表示每轮节点接收和发送数据时消耗的能量，E(vi)为节点vi的能量，k表示数据包大小，Er、Et分别表示接收和发送1 bit数据所消耗的能量，N(vi)表示节点vi在树上的子孙节点数量。

定义7 节点vi的负载Li为：

定义8 节点树高：在一颗路由树中，某个节点到该树上最远叶子节点的转发跳数。

3 问题描述与建模

本文充分考虑危险场景下WSN不同类型的实际应用，通过设定转发跳数，以满足不同类型实际应用场景的要求。

针对数据收集延迟不敏感的应用，如研究原始森林中动物种群的生活习性时，因为需要长期的监视。这类应用对网络寿命有更高要求，可以设定较小的转发跳数，使得汇集点接收的数据量不会过大，从而均衡各节点的能量消耗。针对数据收集延迟敏感的应用，如对泥石流、滑坡等灾害环境的监测与预警，这类应用需要及时将监测信息发送回Sink进行处理，对数据的实时性有更高的要求。这时可以不限制其转发跳数，构造一棵最短路径树，使得所有节点都在同一棵最短路径树上。数据可以通过节点之间的多跳转发及时传送回Sink，能够有效缩短数据收集延迟。

本文要解决的关键问题是如何在网络节点能耗与数据收集延迟中找一个折中，即在给定转发跳数的情况下，研究如何从节点集合中选取部分节点作为停靠节点，使得移动节点访问这些停靠节点所在位置收集数据时，其路径长度最短。

为了解决这个问题，本文提出基于移动节点数据收集路径规划的整数线性规划模型。表1中列出建模中所需的符号及其含义。

表1 模型符号及含义

该问题规划的具体表达式如下。

目标函数：

约束条件：

式（3）为该问题的优化目标，保证移动节点在网络中进行数据收集时路径最短，式（4）～式（11）为该优化问题的约束条件。式（3）中，vi、vj为网络中任意两个传感器节点，|vivj|是移动节点路径上的一条线段；U为移动节点的数据收集路径集合，其具体表示方法如约束条件（4）所示。

约束条件（5）和约束条件（6）确保每个节点发送的数据能够被接收且能够发送到移动节点。其中，式（5）使得网络中的节点为收集树上子孙节点或汇集点，也可以是移动节点的停靠节点。停靠节点不在收集树上，汇集点为收集树的根节点，负责汇总收集树上节点的数据。汇集点和停靠节点是将数据发送给移动节点，可以确保每一个节点发送的数据能够被接收。式（6）约束了在每个汇集点的通信区域内至少有一个停靠节点。其中，N(vi)表示节点vi的邻居节点集合。因为移动节点在收集数据的过程中只访问停靠节点所在位置进行数据收集，可以确保当移动节点到达停靠节点所在位置时，汇集点和停靠节点能够将缓存的数据发送给移动节点。

约束条件（7）和约束条件（8）保证了收集树的结构，且限制了树的高度不超过转发跳数h。式（7）保证了一个传感器节点仅隶属于一个汇集点；式（8）保证了一棵以汇集点为根节点、最大树高为h的收集树能够被建立。约束条件（9）表示如果节点不在收集树上，则节点为停靠节点。

约束条件（10）和约束条件（11）确保移动节点在每轮数据收集过程中，能够访问所有停靠节点和Sink仅一次。其中，式（10）约束了在每轮数据收集过程中，移动节点仅会访问停靠节点一次，两个停靠节点之间的距离称为线段。式（11）表明数据收集路径上的线段数量等于停靠节点的数量加1。

4 结 语

这个模型的提出能够在转发跳数一定的情况下，使得移动节点访问这些停靠节点所在位置收集数据时，路径长度最短。