一种有效的稀疏无线传感器网络路由方案

宋朝，郑迎凤，赵文彬

（1.黄河科技学院现代教育技术中心，河南 郑州 450000；2.石家庄铁道大学信息科学与技术学院，河北 石家庄 050043）

一种有效的稀疏无线传感器网络路由方案

宋朝1，郑迎凤1，赵文彬2

（1.黄河科技学院现代教育技术中心，河南 郑州 450000；2.石家庄铁道大学信息科学与技术学院，河北 石家庄 050043）

稀疏无线传感器网络中节点之间距离过远，使得移动代理节点成为最有效的数据收集方式，然而移动代理节点由于能量限制无法在一次数据收集中到达网络所有节点进行数据收集。为保证在能量受限的移动代理节点总路由路径最短，给出了一种稀疏无线传感器网络能量受限移动代理节点的路由方案。 首先构建移动代理节点的路由数学模型，然后根据移动代理节点初始能量将无线传感器网络划分成不同的子集，最后采用旅行商人问题的模拟退火算法计算出每个子集最短路由，全部子路由的集合即最优路由。 仿真及其分析结果表明：随着网络节点个数增多和移动代理节点能量增大，所给方案的总路由能够比较接近于理想情况，在实际应用中比较有效且适于推广。

稀疏无线传感器网络；移动代理节点；旅行商人问题；路由算法

1 引言

当 前 ，无 线 传 感 器 网 络 （wireless sensor network，WSN）被广泛用于战场监视、环境监测、交通监控医疗监察等各种关键应用领域中。无线传感器网络中所有传感器节点将收集的数据信息传送到基站进行处理分析，所以数据收集的路由选择问题成为无线传感器网络的研究热点。传统的路由解决方法主要采用多跳路由技术，但是由于稀疏无线传感器网络节点之间的距离较远，使得多跳路由技术不能在稀疏无线传感器网络中使用。而移动代理节点方式由于方便、灵活、高效，被认为是稀疏无线传感器网络中比较有效 的 数 据 收 集 方 法［1，2］。根 据 应 用 环 境 （公 路 、河 流 、管 道 等 ）不同，车辆、船舶等都能作为移动代理节点载体。由于部署传感器节点的区域大多是较为偏远且环境比较恶劣的地域，尤其是在稀疏无线传感器网络（比如公路交通监管）中，传感器节点分布比较分散而且无法互相通信，车辆或陆用机器人有可能在崎岖的山路上或者断壁悬崖前无法前进到 指 定 的 区 域 ，所 以 无 人 飞 行 器 （unmanned aerial vehicle，UAV）能够很好地作为移动代理节点的载体应用在大多数条件较为恶劣的环境中。并且无人飞行器所携带的燃料和电池是受限的，经过一段时间的工作后需重返基站补充各种能源，因此关于移动代理节点如何选择路由才能更高效快捷已成为稀疏无线传感器网络研究的热点问 题［3，4］。

假设移动代理节点在理想状态下的各种能量都是充足的，仅在一次数据收集时间内就能够到达部署区域的所有传感器节点，这时可将该问题转化为旅行商人问题（traveling salesman problem，TSP），应 用 模 拟 退 火 （simulated annealing，SA）算 法［5］即 能 计 算 得 到 移 动 代 理 节 点 的 最 优 路由。但移动代理节点在实际状态下能量是有限的，需要在基站和节点之间进行多次往返补充能量，且因无人飞行器等移动代理节点使用代价较高，使得在网络中部署许多个无人飞行器不现实。本文在考虑到移动代理节点能量有限的基础上，给出一种稀疏无线传感器网络中能量有限移动代 理 节 点 的 路 由 方 案 （routing scheme of energy-constrained mobileagentnodein sparsewirelesssensornetwork，E-CMAN）。所给方案首先构建出在相关约束条件下的数学模型，其次利用旅行商人问题解决方法根据移动代理节点的限制能量大小将全网络划分为若干个子集，并在每个子集中采用模拟退火算法计算出最优的子路由，最后将全部子路由组集合即形成最优总路由，且所得到的路由非常接近于理想状态下的路由，能较好地适用在对时间不敏感的稀疏无线传感器网络中。

2 相关研究

在稀疏无线传感器网络中，利用移动代理节点实施数据收集的方法已成为国内外学者研究的重点，提出了针对不 同 情 况 下 的 移 动 代 理 节 点 路 由 问 题［6，7］。Tariq 等 人［8］设 计移动代理节点在传感器节点部署区域内随机移动，且以一定的概率进行数据收集，这种方案的数据收集效率不高且无 法 保 证 收 集 到 所 有 节 点 数 据 信 息 。Jeonghwa 等 人［9］设 计 当移动代理节点能量消耗殆尽，网络中某一成员节点将会转化为移动代理节点继续进行数据收集，该方案要求网络中传感器节点能够移动，这有可能造成区域数据感知缺失，从而影响整个网络的稳定性，而且由于节点更换比较困难这将 会 增 加 该 方 案 实 施 的 复 杂 性 。Almi’ani等 人［10］设 计 了 在 移动代理节点能量有限时进行数据收集所需的最长路由，并使用多跳路由和移动代理节点路由的混合路由方式，首先是根据移动代理节点的初始能量将全网络分成许多个独立的簇，即簇的个数与移动代理节点的初始能量有关，同时选举簇头进行预先数据收集，然后移动代理节点仅收集簇头节点的数据，该方案需要各节点之间可以相互通信，但这将会导致簇头节点的能耗过快，从而影响全网络寿命 。彭 伟 等 人［11］主 要 是 在 考 虑 时 间 敏 感 性 的 情 况 下 ，根 据控制消息时延来确定最少的移动代理节点数目，该方案能够满足对时间敏感度要求较高的网络，但是对于一些非时间敏感度的网络则无疑提升了成本。现有的方案大多是考虑在某一特定环境中的路由选择方法，与所给E-CMAN 方案适用 的应用环境存在一定 的 差别，其中所 给E-CMAN 方 案 的 网 络 应 用 环 境 可 见 于 第 3 节 中 的 网 络 模型介绍。

3 网络模型

E-CMAN 方案 的应用 环 境 主要具备 下 述 4 个特 性 ：在部署范围内所有节点与基站均不能移动，所在坐标一经确定就保持不变；节点之间、节点和基站之间均不能互相通信与信息传输，这是因为所有节点都被高度分散部署在较大区域范围内；移动代理节点的初始能源和电池是有限的，只能支持一段距离的路程，然后需返回基站进行补充后才能继续工作；全网络是非时间敏感度的，为了降低成本仅使用一个移动代理节点，并且依照预设路径实施数据收集。下面给出应用网络环境与移动代理节点的相关假设：

· 节点使用较低的数据采集速率，且其所采集的数据在传送给移动代理节点前不会失效；

· 移动代理节点拥有足够大的存储缓冲区，能收集网络覆范围内所有节点数据信息且不会溢出；

·移动代理节点需到达节点指定位置才可收集数据，不需考虑节点的传输距离和方向；

·移动代理节点在转向时的时间和能耗开销能够忽略不计；

·移动代理节点等待某一节点传输数据过程中的时间和能耗开销同其移动距离所需的时间和能耗开销相比能够忽略不计；

· 移动代理节点在返回基站后，所需能源和电池会自动重新补装填满。

4 E-CMAN 算法设计

4.1 数学模型

E-CMAN 方案的 主要思想 ：首 先 将全网络 分 为 独立的许多个不同子集，各个子集的节点个数应满足移动代理节点的自身能量限制，其次计算移动代理节点在各个子集中的最优子路由，移动代理节点多次往返后到达各个子集中所有传感器节点形成的路由集合即为最优的路由方案，其中移动代理节点的往返次数与划分子集的数目相同。假设S 表 示 稀 疏无线 传 感 器网络，包括 N 个 节 点 ，令 s0表 示 基站 ，si表 示 某 一 节 点 ，且 有 i=1，2，… ，N，其 坐 标 表 示 为 （xi，yi），则 两 个 节 点 sa与 sb间 的 距 离 长 度 是 d（sa，sb）=假定整个稀疏无线传感器网络被分成M 个子集，各个子集包含有 Nq个节点，令 Si表 示第 q 个子集 ，spq表 示 第 q 个 子 集 中 的 第 p 个 节 点 ，且 有 q=1，2，… ，M，p=1，2，… ，Nt。由 于 移 动 代 理 节 点 在 各 个 子 集 中 往 返 一 次 均需 要 两 次 返 回 基 站 ，因 此 令和分 别 表 示 基 站 在 每 个子集代表的出发节点和到达节点。令 F为移动代理节点在其有限能量状态下所能行进的最长距离，从而可以将能量限制转换成距离限制，以便能够更直观地构建数学模型。式（1）给出了移动代理节点的最优总路由表示：

其中，式（1）具有以下约束条件：

（1）Nq≥1，能够确保各个子集均不为空；

（2）Su∩Sυ= ，1≤u≠ υ≤M ， 能 够 确 保 一 个 节 点 仅包含在一个子集中，即移动代理节点仅访问每个节点一次；

（5）F≥2d（s0，si），1≤i≤N，确 保 移 动 代 理 节 点 的 能 量 足够从基站到最远节点之间往返一次，能避免移动代理节点因能量过少而不能进行数据收集；

（6）M＜N，能够确保在稀疏无线传感器网络中至少有两个以上的子集，若 T=N，该模型会退化为移动代理节点每次往返仅能访问一个节点。

4.2 最优路由算法

E-CMAN 算法包括 两 个 步骤：根据移 动 代理节点 自 身能量限制，对全网络实施子集划分；在各个子集内应用旅行商人问题求解方法计算出各个子集的最优子路由，所有最优子路由组成的集合即为整个稀疏无线传感器网络的最优总路由。算法1给出了网络子集划分算法。在子集的划分过程中，要先在假设移动代理节点自身能量为无限大时 ，应 用 TSP 求 解 算 法［12］计 算 出 子 集 中 的 路 由 节 点 序 列 ，并 令 表 示 RTSP此 节 点 序 列 ，然 后 依 次 计 算 节 点 序 列 之 间 的距离，在小于或等于限制距离 F的序列长度内所包含的节 点 表 示 为 一 个 子 集 。 令 RTSP表 示 在 不 受 能 量 限 制 时 利用 模 拟 退 火 算 法 计 算 出 的 路 由 ，MTSP表 示 路 由 RTSP中 具有 的 传 感 器 节 点 个 数 ，Rtemporary表 示 当 前 的 临 时 路 由 ，Rsubset表示移动代理节点在自身能量限制内行进的最长子路径，Ssubset=Compute（Rsubset）表 示 计 算 路 径 Rsubset中 具 有 的 传 感 器 节点个数。

算法1 子集划分算法

输 入 ：S，F，s0；

输出：Sq。

当 i≤MTSP时，则 重 复 执 行 ：

若 i=MTSP，则 跳 出 此 循 环 ；／说 明 移 动 代 理 节 点具有足够的能量遍历全网络中所有传感器节点，则此时跳出该循环

在 算 法 1 中 ，因 子 路 径 Rsubset是 沿 RTSP的 路 径 行 进 的 ，但 RTSP是 在 没 有 能 量 限 制 时 计 算 出 来 的 ，所 以 在 划 分 为 子集 后 ，子 路 径 Rsubset并 不 一 定 是 子 集 Sq中 的 最 优 子 路 由 。同时需要说明的是，算法 1的主要作用是将整个网络划分为相互独立的不同子集区域，移动代理节点在划分过程中仅遍历每个传感器节点一次，即使在算法 1的网络划分过程中存在路径相交的情况，但每个传感器节点仍分属不同的子集网络中，由于移动代理节点每次完成一个子集的数据收集后将会返回基站重新补充能量，然后继续进行下一个子集的数据收集，所以算法1的子集划分过程不会影响此后的最优子集路径计算。在实施网络子集划分后，对每个子集再次采用旅行商问题解决方法计算出移动代理节点在各个子集中的路由才是最优子路由，而全部子路由的集合即是网络最优总路由。算法 2给出了网络最优路由算法。由算法 1可知 ，网络被 分成 M 个子集且每个子集含有 Nq个节点，同时要注意各个子 集 内 均 有 两 个 s0， 即 Sq=s0→spq→s0，1 ≤j≤Nq。 其 中Rsubroute=TSP（Sq）表 示 应 用 模 拟 退 火 算 法 计 算 出 子 集 Sq而 得到的最优子路由。

算法2 最优路由算法

输入：Sq，F，s0；

输 出 ：Roptimal。

对于 q从 1到 M，重复执行：

5 算法性能分析

假设稀疏无线传感器网络部署在二维平面区域内，覆盖 面 积 10 km×10 km，基 站 坐 标 为 （0，0），移 动 代 理 节 点 的初 始 能 量 允 许 能 够 工 作 的 最 长 距 离 为 F=30 km。 利 用MATLAB R2006a 仿 真 环 境 ，图 1 给 出 了 当 稀 疏 无 线 传 感器网络节点为 10 个时，采用所给 E-CMAN 算法 得到的路由示意。可以看出，整个网络被分为两个子集，分别包含 6个和 4 个 节点（除基站 外 ），且两 个子 集 的 面 积 基 本 相 似，说明移动代理节点每一次在子集内的数据收集都最大化且均衡地利用了自身有限的能量和燃料。

图1 E-CMAN 算 法 在 节点个数为 10 时的路由

在稀疏无线传感器网络中，移动代理节点的路由主要同节点个数和能量大小有关。图2和图3分别给出了移动代理节点的总路由随着节点个数增加和限制能量增大时的变 化 情 况 ，同 时 分 别 同 理 想 情 况 下［13］的 路 由 Rideal、最 近 邻 居 节点 查 找 算 法［14］的 路 由 Rneighbor及 旅 行 商 人 问 题 求 解 算 法［15］的 路 由 RTSP进 行 了 分 析 比 较 。由 图 2 可 以 看 出 ，随 着 网 络节点的个数增多，移动代理节点在 4种算法下的路由长度均是增大的，这是因为移动代理节点的能量是既定的，随着节点增加使得子集的数目也在增多，进而移动代理节点需往返基站的次数也要增多，从而增大了总路由 的 长 度 。然 而 E-CMAN 算法的路由增加幅度总体较小，且比较接近于 理想状态 下 的 路由长度 。另外，E-CMAN 算法在同样的节点个数下与其他 3种算法相比，总路由的长度最短。

图2 随着网络节点个数增加总路由的变化

图3 随着移动代理节点限制能量增大总路由的变化

由图3可以看出，随着移动代理节点的限制能量增大，4 种算法下的移动代理节点 路由长度均 是减少 的，主要是因为移动代理节点的能量增大将会减少子集的个数，从而使移动代理节点往返基站的次数减少，因而总路由的长度也在减少。然而，根据 E-CMAN 算法计算所得路由减少的幅度更大，更加接近于理想状态下的路由。且E-CMAN 算法在同样的能量限制条件下，与 其 余 3 种 算 法的 路 由 长 度 相 比 ，其 总 路 由长 度 是 最 短 的 。另 外 ，图 3 的横 坐 标 从 30 km 处 开 始 ， 这 表 示 移 动 代 理 节 点 自 身 能量可以支持其一次往返节点和基站的最短距离，假如移动代理节点初始能量所能支持的工作距离小于该距离，则该移动代理节点就不能执行这个网络的数据收集工作。

6 结束语

因稀疏无线传感器网络中的传感器节点数量比较少，可将移动代理节点访问每个传感器节点的路由问题看作旅行商人问题。但因移动代理节点自身能量存在限制，使得其不能一次完成整个网络中传感器节点的数据收集。所以，本文给出了一种稀疏无线传感器网络中能量有限移动代理节点的路由方案，通过将全网络划分为移动代理节点，可以一次全部访问许多个子集区域，然后对各个子集利用旅行商人问题求解方法计算出各个子路由，最终全部子路由的集合即最优总路由。性能分析结果表明，E-CMAN算法随网络规模的增加与限制能量的增大均比较接近于理想状态下的路由，非常适用于实际应用，具有很好的研究和推广价值。

［1］ 汤文俊，张国良，曾静，等. 一种适用于稀疏 无线传感 器网 络 的改 进 分 布 式 UIF 算 法［J］.自动化学报，2014，40（11）：2490-2498. TANG W J，ZHANG G L，ZENG J，et al.An improved distributed unscented information filter algorithm for sparse wireless sensor networks［J］.Acta Automatica Sinica，2014，40（11）：2490-2498.

［2］ 苗 勇 ，崔 莉. 稀 疏 无 线 传 感 器 网 络 移 动 节 点 定 位 算 法 ［J］. 高技 术 通 讯，2010，20（5）：454-460. MIAO Y ，CUI L.A mobile node localization method for sparse mobile wireless sensornetworks ［J］.Chinese High Technology Letters，2010，20（5）：454-460.

［3］ 孙 子 文 ，刘 加 杰 ，纪 志 成. 无 线 传 感 器 网 络 中 基 于 代 理 的D-S 数 据 融 合 ［J］. 计 算 机 工 程 与 科 学 ，2014，36 （10）：1919-1924. SUN Z W，LIU J J，JI Z C.Agent based D-S data fusion in wireless sensor networks［J］.Computer Engineering and Science，2014，36（10）：1919-1924.

［4］ 赵辉，贾 宗璞. 基 于移 动辅 助 的 无 线 传 感 器 网 络 信 息 获 取 技术 研 究 ［J］. 计 算 机 应 用 研 究 ，2014，31（11）：3447-3454. ZHAO H，JIA Z P.Mobile assisted wireless sensor network information acquisition technique ［J］.Application Research of Computers，2014，31（11）：3447-3454.

［5］ 李 忠. 采 用 遗 传 模 拟 退 火 策 略 的 WSN 节 点 部 署 优 化 ［J］. 系 统仿 真 学 报，2014，26（2）：353-356. LI Z.Application research of computers deployment of wireless sensor network nodes by improved genetic simulated annealing algorithm ［J］.Journal of System Simulation，2014，26 （2）：353-356.

［6］ 张 胜，杨 郑 龙，曹 凯 英. 基 于 移 动 agent的 能 量 平 衡 环 形 路 由算 法 ［J］. 计 算 机 应 用 研 究 ，2014，31（9）：2661-2664. ZHANG S，YANG Z L，CAO K Y.Energy balanced ring routing algorithm based on mobile agent ［J］.Application Research of Computers，2014，31（9）：2661-2664.

［7］ 杨 郑 龙 ，张 胜，吴 卉. 基 于 移 动 agent的 能 量 平 衡 螺 旋 形 路 由算 法 ［J］. 传 感 器 与 微 系 统 ，2014，33（10）：128-132. YANG Z L，ZHANG S，WU H.Energy balanced spiral routing algorithm based on mobile agent ［J］. Transducer and Microsystem Technologies，2014，33（10）：128-132.

［8］ TARIQ M M B，ZEGURA M A，ZEGURA E.Message ferry route design for sparse ad hoc networks with mobile nodes ［C］／／The 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing，May 22-25，2006，Florence，Italy. New York：ACM Press，2006：37-48.

［9］ JEONGHWA Y，YAND C，AMMAR M，et al.Ferry replacement protocols in sparse MANET message ferrying systems ［C］／／Wireless Communications and Networking Conference，March 13-17，2005，New Orleans，USA.New Jersey：IEEE Press，2005：2038-2044.

［10 ］ALMI’ ANI K ，VIGALS A ，LIBMAN L.Energy-efficient datagathering with tourlength-constrained mobile elementsin wireless sensor networks ［C］／2010 IEEE 35th Conference on Local Computer Networks （LCN），Oct 10-14，2010，Denver，USA.New Jersery：IEEE Press，2010：582-589.

［11］PENG W，ZHAO B K，YU W R，et al.Ferry route design with delay bounds in delay-tolerant networks ［C］／The 2010 IEEE 10th International Comference on Computer and Information Technology （CIT），June 29- July 1，2010，Bradford，UK.New York：IEEE Press，2010：281-288.

［12］ZHENG J G，WU D Q，ZHOU L.Traveling salesman problem using an enhanced hybrid swarm optimization algorithm ［J］. Journal of Donghua University （English Edition），2014，31 （3）：362-367.

［13］IBM.ILOG CPLEX Optimizer［EB／OL］.［2015-06-20］.http：／www-01. ibm.com／software／integra- tion／optimization／cplex-optimizer／.

［14］LONG J，GUI W H.Node deployment strategy optimization forwireless sensor network with mobile basestation ［J］. Journal of Central South University of Technology，2012，19（2）：453-458.

［15］Helsgaun K.IKH ［EB／OL］. ［2015-06-20］.http：／www.akira.ruc. dk／～keld／reaserch／LKH／.

An effective routing scheme of sparse wireless sensor networks

SONG Chao1，ZHENG Yingfeng1，ZHAO Wenbin2
1.Modern Educational Technology Center，Huanghe Science and Technology College，Zhengzhou 450000， China 2.College of Information Science and Technology，Shijiazhuang Railway University，Shijiazhuang 050043，China

Mobile agent node has become the most efficiency way of data collection in sparse wireless sensor networks，because the distance of the nodes is too far.However，the mobile agent node could not access all the nodes to gather the data in a routing travel because of energy-constrained.In order to make the energy-constrained mobile agent node obtain the minimum total route，an effective routing scheme of energy-constrained mobile agent node in sparse wireless sensor networks was presented.The mathematic model of the route of mobile agent node was built firstly，and then the whole wireless sensor network was split into different subsets according to the energy of the mobile agent node.Then the shortest routes were computed by adopting simulated annealing of traveling salesman problem.Finally，the obtained total route of sub-routes was the optimal route.The analysis results of simulation and performance show that the total route of the presented scheme is close to the ideal situation along with the increase of the number of nodes and the raise of the energy of mobile agent node.So the presented scheme is very effective in the practice and is propitious to popularize.

sparse wireless sensor network，mobile agent node，traveling salesman problem，routing algorithm

The National Natural Science Foundation of China（No.61232008）

TP393

：A

10.11959／j.issn.1000-0801.2016094

宋 朝 （1983-）， 男 ， 黄 河 科 技 学 院 现 代 教 育技术中心讲师，主要研究方向为计算机应用、信息安全。

郑 迎 凤 （1984-）， 女 ， 黄 河 科 技 学 院 现 代 教育技术中心讲师，主要研究方向为计算机应用、信息安全。

赵文彬（1985-），男 ，博 士 ，石 家 庄 铁 道 大 学信息科学与技术学院讲师，主要研究方向为科学可视化、复杂网络和信息安全。

2015-07-01；

2016-03-08

国 家 自 然 科 学 基 金 资 助 项 目 （No.61232008）