工程科学学报，第40卷，第11期：1412-1421,2018年11月 Chinese Joural of Engineering,Vol.40,No.11:1412-1421,November 2018 DOI:10.13374/j.issn2095-9389.2018.11.015;http://journals.ustb.edu.cn 巡线机器人延迟容忍传感器网络数据传输策略 樊飞)，吴功平1)区，王满)，徐青山2)，曹琪)，杨松) 1)武汉大学动力与机械学院，武汉4300722)国网吉林省电力有限公司，长春1300003)国网吉林省电力有限公司白山供电公司，白山 134300 ☒通信作者，E-mail:即wu@whu.cd.cm 摘要巡线机器人延迟容忍传感器网络(delay tolerant mobile sensor networks for inspection robot,DTMSNR)用于输电线路巡 线机器人远程电网数据收集，具有节点稀疏、异构、随机移动性、间歇连通性和延迟容忍性.针对传统传感器网络数据传输算 法机器人数据传输成功率低与网络可靠性差等问题.提出一种基于巡线机器人位姿信息的数据传输(mobile robot position- based delivery,MPD)策略.为准确计算巡线机器人网络位姿信息，建立机器人路径约束随机运动模型.MPD采用机器人相对 网络位姿信息计算传输概率，进行消息传输路径选择.对网络异构消息引入机器人消息优先传输、消息失效机制进行消息队 列管理.仿真实验表明，相较现有的几种延迟容忍传感器网络(delay tolerant mobile sensor network,DTMSN)数据传输策略，针 对巡线机器人网络MPD能在适当的传输能耗下达到更高的传输成功率与更低的传输延迟. 关键词巡线机器人：延迟容忍传感器网络：数据传输：队列管理：输电线路监控 分类号TP393.1 Date delivery scheme of delay-tolerant mobile sensor networks for high-voltage power transmission line inspection robot FAN Fei),WU Gong-ping,WANG Man),XU Qing-shan2),CAO Qi),YANG Song) 1)School of Power and Mechanical Engineering,Wuhan University,Wuhan 430072,China 2)State Grid Jilin Electric Power Co.,Ltd.,Changchun 130000,China 3)Baishan Power Supply Company,State Grid Jilin Electric Power Co.,Ld.,Baishan 134300,China Corresponding author,E-mail:gpwu@whu.edu.cn ABSTRACT To improve the level of intelligent monitoring,maintenance,and management of transmission lines,research on inspec- tion robots,and key technologies of overhead transmission line have attracted wide attention.With the breakthrough of the theory and technology of the internet of things,robot data transmission based on wireless sensor networks has become an active research area in the field of inspection robotics.Several researchers assume that robots are mobile nodes in wireless sensor networks,and the non-mobile communication node in the network is considered as a static node.The most crucial and difficult aspect of this research is coordinating the relationship among transmission success rate,transmission energy consumption,and delay of dynamic sensors networks.To address this difficulty,a novel method was proposed for the intelligent monitoring and communication system of power grids based on inspection robots.This method aims to realize the remote data collection of inspection robot by delay-tolerant mobile sensor networks for inspection robot (DTMSNR),which is featured by nodes heterogeneity,sparse sensor fields,random mobility,intermittent connectivity,and delay tolerance.It adopts the mobile robot position-based delivery (MPD)method to solve the inadaptability of the traditional methods of sensor networks.A path-constrained random motion model was established,in order to accurately calculate the network pose infor- mation of the inspection robot.The MPD adopts the relative position information of the robot and other nodes to compute transmission 收稿日期：2017-10-31 基金项目：广东省科技计划专项资助项目(2015B090922007):国网吉林省电力有限公司资助项目(JDK2015-21)
工程科学学报,第 40 卷,第 11 期:1412鄄鄄1421,2018 年 11 月 Chinese Journal of Engineering, Vol. 40, No. 11: 1412鄄鄄1421, November 2018 DOI: 10. 13374 / j. issn2095鄄鄄9389. 2018. 11. 015; http: / / journals. ustb. edu. cn 巡线机器人延迟容忍传感器网络数据传输策略 樊 飞1) , 吴功平1)苣 , 王 满1) , 徐青山2) , 曹 琪3) , 杨 松3) 1) 武汉大学动力与机械学院, 武汉 430072 2) 国网吉林省电力有限公司, 长春 130000 3) 国网吉林省电力有限公司白山供电公司, 白山 134300 苣 通信作者, E鄄mail: gpwu@ whu. edu. cn 摘 要 巡线机器人延迟容忍传感器网络(delay tolerant mobile sensor networks for inspection robot, DTMSNR)用于输电线路巡 线机器人远程电网数据收集,具有节点稀疏、异构、随机移动性、间歇连通性和延迟容忍性. 针对传统传感器网络数据传输算 法机器人数据传输成功率低与网络可靠性差等问题. 提出一种基于巡线机器人位姿信息的数据传输(mobile robot position鄄 based delivery, MPD)策略. 为准确计算巡线机器人网络位姿信息,建立机器人路径约束随机运动模型. MPD 采用机器人相对 网络位姿信息计算传输概率,进行消息传输路径选择. 对网络异构消息引入机器人消息优先传输、消息失效机制进行消息队 列管理. 仿真实验表明,相较现有的几种延迟容忍传感器网络(delay tolerant mobile sensor network, DTMSN)数据传输策略,针 对巡线机器人网络 MPD 能在适当的传输能耗下达到更高的传输成功率与更低的传输延迟. 关键词 巡线机器人; 延迟容忍传感器网络; 数据传输; 队列管理; 输电线路监控 分类号 TP393郾 1 收稿日期: 2017鄄鄄10鄄鄄31 基金项目: 广东省科技计划专项资助项目(2015B090922007); 国网吉林省电力有限公司资助项目(JDK2015鄄鄄21) Date delivery scheme of delay鄄tolerant mobile sensor networks for high鄄voltage power transmission line inspection robot FAN Fei 1) , WU Gong鄄ping 1)苣 , WANG Man 1) , XU Qing鄄shan 2) , CAO Qi 3) , YANG Song 3) 1) School of Power and Mechanical Engineering, Wuhan University, Wuhan 430072, China 2) State Grid Jilin Electric Power Co. , Ltd. , Changchun 130000, China 3) Baishan Power Supply Company, State Grid Jilin Electric Power Co. , Ltd. , Baishan 134300, China 苣 Corresponding author, E鄄mail: gpwu@ whu. edu. cn ABSTRACT To improve the level of intelligent monitoring, maintenance, and management of transmission lines, research on inspec鄄 tion robots, and key technologies of overhead transmission line have attracted wide attention. With the breakthrough of the theory and technology of the internet of things, robot data transmission based on wireless sensor networks has become an active research area in the field of inspection robotics. Several researchers assume that robots are mobile nodes in wireless sensor networks, and the non鄄mobile communication node in the network is considered as a static node. The most crucial and difficult aspect of this research is coordinating the relationship among transmission success rate, transmission energy consumption, and delay of dynamic sensors networks. To address this difficulty, a novel method was proposed for the intelligent monitoring and communication system of power grids based on inspection robots. This method aims to realize the remote data collection of inspection robot by delay鄄tolerant mobile sensor networks for inspection robot (DTMSNR), which is featured by nodes heterogeneity, sparse sensor fields, random mobility, intermittent connectivity, and delay tolerance. It adopts the mobile robot position鄄based delivery (MPD) method to solve the inadaptability of the traditional methods of sensor networks. A path鄄constrained random motion model was established, in order to accurately calculate the network pose infor鄄 mation of the inspection robot. The MPD adopts the relative position information of the robot and other nodes to compute transmission
樊飞等：巡线机器人延迟容忍传感器网络数据传输策略 ·1413· probability and selects the message transmission path.This method uses mechanisms of robot message priority transfer and failure time to manage the message queue,considering the different delay requirements for messages.Multiple simulation scenarios were performed,and the influences of different parameters with four routing algorithms were discussed.The results indicate that compared with the commonly used DTMSN data transmission methods,the proposed method can provide a higher delivery ratio and lower transport delay under appropriate transmission energy consumption. KEY WORDS inspection robot;delay-tolerant sensor networks;data delivery;queue management;transmission lines monitoring 近年来，为提高输电线路智能化监控、维护与管 了基于节点运动状态的数据传输(motion state-based 理水平，工作于架空高压输电线路的巡线机器人及 delivery,MSD)策略与基于相对距离感知的动态数 其关键技术研究获得广泛关注).随着物联网技术 据传输策略(relative distance-aware data delivery 突破，特别是无线传感器网络面向机器人等移动对 scheme,RDAD),对节点位置关系进行计算，但缺乏 象数据传输相关理论与应用的创新，基于无线传感 对异构网络的分析.文献[14]提出基于转发概率的 器网络的巡线机器人数据传输问题已成为巡线机器 动态数据转发策略(forwarding probability-based 人领域深入研究热点.巡线机器人及无线传感器网 adaptive data delivery algorithm,FPAD),采用能耗及 络作为物联网技术在智能电网的新应用，是智能电 延迟因子对异构网络进行研究，但节点消息传输只 网系统智能化向输电线路巡检设备智能化的延伸与 发生在相对距离最短时刻，缺乏普遍性.以上方法 发展[].大量研究学者将机器人假设为无线传感器 均未针对输电线路特征及巡线机器人作业方式进行 网络中的移动节点，网络中不可移动通讯节点视作 网铬建模，缺少一种符合架空输电线路与巡线机器 静态节点，以形成动态无线传感器网络.在深入研 人作业特点的数据传输算法 究中如何协调此类网络传输成功率、传输能耗与延 本文提出一种基于机器人位姿信息的巡线机器 迟的关系是研究的重点内容 人延迟容忍无线传感器网络(DTMSNR)及其数据传 普通动态无线传感器网络基于多跳网络实时性 输策略.网络中机器人与静态节点、中心节点组成 要求设计[3).由于传输路径的频繁变更，增加了网 异构网络.策略基本方法是通过机器人在网络中的 络能量空洞几率与网络延迟，降低了传输成功率与 位姿信息计算出机器人与中心节点的传输概率，获 网络可靠性-刀.巡线机器人在输电线路巡检等工 取网络中其他可感知节点转发概率，经过比较将数 作中的运动随机性和沿线路部署节点的分散性、稀 据传递给转发概率大于传输概率的节点.在算法中 疏性必然导致机器人与静态节点间通讯短时非连通 通过特征因子保证数据能以相对更稳定的网络链路 状态，即间歇连通的出现.输电线路巡检数据传输 连接、较小的能量损耗和更低的传输延迟发送到网 是延迟容忍的，非实时信息也可对线路运行进行诊 络其他节点.针对网络中消息不同延迟要求采用机 断评估.在延迟容忍无线传感器网络(DTMSN)中 器人消息优先传输、失效时间机制进行消息队列管 巡线机器人与静态节点形成一个间歇连通无线传感 理，提高传输成功率，控制消息副本与传输能量，增 器网络，传统数据传输方法难以满足DTMSN数据 强网络性能 传输延迟、传输成功率、传输能耗的良好平衡关系. 目前，针对DTMSN的数据传输问题，一些学者进行 1机器人网络模型与传输策略问题描述 了相关研究.这些研究中比较典型的传输策略为文 1.1机器人网络模型 献[8-l1]提出的直接传递算法(direct)、泛洪传递 巡线机器人系统由机器人、普通静态通信节点、 算法(flood)及容错自适应策略(FAD).Direct策略 中心通信节点、集控中心、在线充电装置组成.机器 中网络节点只与中心节点通讯，网络消耗少，但传输 人进行架空输电线路巡检工作时可由在线充电装置 成功率及消息延迟依赖移动节点与中心节点的相遇 进行能量补给，同时其他通它节点可采集机器人、充 概率，网络传输性能受限.Food策略中网络节点与 电装置等数据并传输至集控中心.为满足实际需 所有相邻节点发送消息传递，降低了网络延迟，但在 求，本文定义了基于线路信息与机器人系统特征的 大规模网络中消息量的激增严重影响网络能耗与寿 无线传感器网络.网络初始部署时所有静态节点 命.FAD策略使网络节点有选择的传递消息，基于 (含中心节点)沿输电线路分布并配置于架空输电 历史消息转发记录来计算传输概率，在稀疏网络环 线路杆塔上.网络模型如图1所示，其通信节点满 境中传输概率计算精确性有限.文献[12-13]提出 足以下性质
樊 飞等: 巡线机器人延迟容忍传感器网络数据传输策略 probability and selects the message transmission path. This method uses mechanisms of robot message priority transfer and failure time to manage the message queue, considering the different delay requirements for messages. Multiple simulation scenarios were performed, and the influences of different parameters with four routing algorithms were discussed. The results indicate that compared with the commonly used DTMSN data transmission methods, the proposed method can provide a higher delivery ratio and lower transport delay under appropriate transmission energy consumption. KEY WORDS inspection robot; delay鄄tolerant sensor networks; data delivery; queue management; transmission lines monitoring 近年来,为提高输电线路智能化监控、维护与管 理水平,工作于架空高压输电线路的巡线机器人及 其关键技术研究获得广泛关注[1] . 随着物联网技术 突破,特别是无线传感器网络面向机器人等移动对 象数据传输相关理论与应用的创新,基于无线传感 器网络的巡线机器人数据传输问题已成为巡线机器 人领域深入研究热点. 巡线机器人及无线传感器网 络作为物联网技术在智能电网的新应用,是智能电 网系统智能化向输电线路巡检设备智能化的延伸与 发展[2] . 大量研究学者将机器人假设为无线传感器 网络中的移动节点,网络中不可移动通讯节点视作 静态节点,以形成动态无线传感器网络. 在深入研 究中如何协调此类网络传输成功率、传输能耗与延 迟的关系是研究的重点内容. 普通动态无线传感器网络基于多跳网络实时性 要求设计[3鄄鄄4] . 由于传输路径的频繁变更,增加了网 络能量空洞几率与网络延迟,降低了传输成功率与 网络可靠性[5鄄鄄7] . 巡线机器人在输电线路巡检等工 作中的运动随机性和沿线路部署节点的分散性、稀 疏性必然导致机器人与静态节点间通讯短时非连通 状态,即间歇连通的出现. 输电线路巡检数据传输 是延迟容忍的,非实时信息也可对线路运行进行诊 断评估. 在延迟容忍无线传感器网络(DTMSN) 中 巡线机器人与静态节点形成一个间歇连通无线传感 器网络,传统数据传输方法难以满足 DTMSN 数据 传输延迟、传输成功率、传输能耗的良好平衡关系. 目前,针对 DTMSN 的数据传输问题,一些学者进行 了相关研究. 这些研究中比较典型的传输策略为文 献[8鄄鄄11]提出的直接传递算法( direct)、泛洪传递 算法(flood)及容错自适应策略(FAD). Direct 策略 中网络节点只与中心节点通讯,网络消耗少,但传输 成功率及消息延迟依赖移动节点与中心节点的相遇 概率,网络传输性能受限. Flood 策略中网络节点与 所有相邻节点发送消息传递,降低了网络延迟,但在 大规模网络中消息量的激增严重影响网络能耗与寿 命. FAD 策略使网络节点有选择的传递消息,基于 历史消息转发记录来计算传输概率,在稀疏网络环 境中传输概率计算精确性有限. 文献[12鄄鄄13]提出 了基于节点运动状态的数据传输(motion state鄄based delivery, MSD)策略与基于相对距离感知的动态数 据 传 输 策 略 ( relative distance鄄aware data delivery scheme, RDAD),对节点位置关系进行计算,但缺乏 对异构网络的分析. 文献[14]提出基于转发概率的 动 态 数 据 转 发 策 略 ( forwarding probability鄄based adaptive data delivery algorithm, FPAD),采用能耗及 延迟因子对异构网络进行研究,但节点消息传输只 发生在相对距离最短时刻,缺乏普遍性. 以上方法 均未针对输电线路特征及巡线机器人作业方式进行 网络建模,缺少一种符合架空输电线路与巡线机器 人作业特点的数据传输算法. 本文提出一种基于机器人位姿信息的巡线机器 人延迟容忍无线传感器网络(DTMSNR)及其数据传 输策略. 网络中机器人与静态节点、中心节点组成 异构网络. 策略基本方法是通过机器人在网络中的 位姿信息计算出机器人与中心节点的传输概率,获 取网络中其他可感知节点转发概率,经过比较将数 据传递给转发概率大于传输概率的节点. 在算法中 通过特征因子保证数据能以相对更稳定的网络链路 连接、较小的能量损耗和更低的传输延迟发送到网 络其他节点. 针对网络中消息不同延迟要求采用机 器人消息优先传输、失效时间机制进行消息队列管 理,提高传输成功率,控制消息副本与传输能量,增 强网络性能. 1 机器人网络模型与传输策略问题描述 1郾 1 机器人网络模型 巡线机器人系统由机器人、普通静态通信节点、 中心通信节点、集控中心、在线充电装置组成. 机器 人进行架空输电线路巡检工作时可由在线充电装置 进行能量补给,同时其他通它节点可采集机器人、充 电装置等数据并传输至集控中心. 为满足实际需 求,本文定义了基于线路信息与机器人系统特征的 无线传感器网络. 网络初始部署时所有静态节点 (含中心节点)沿输电线路分布并配置于架空输电 线路杆塔上. 网络模型如图 1 所示,其通信节点满 足以下性质. ·1413·
.1414. 工程科学学报，第40卷，第11期 巡线机器人 ○杆塔。中心通信节点④静态通信节点口巡线机器人塔上通讯节点及充电装置 一机器人运动轨迹------一节点通信链路 图1巡线机器人网络模型 Fig.1 Network model of inspection robot for high-voltage power transmission line (1)节点具有异构的通信能力，为降低能耗，机2中Dx+,表示第X+x(x,X∈N)次运动的终点 器人与普通静态节点通信半径较小为R,中心节点 网络中所有机器人遵循上述运动过程，它们之间 可同时具有两种通信半径：普通静态节点通讯半径 运动相互独立. R、大功率通讯半径C,其中2R<C. 1.2数据传输策略问题描述 (2)机器人具有异构运动速度，机器人巡检作 基于DTMSN与巡线机器人网络特点，高效的 业时根据线路环境、数据采集、能耗等因素调节运动 数据传输策略与路由算法应考虑以下问题： 速度.网络信息、巡检数据具有异构的数据容量与 (1)传输策略应满足机器人网络多跳分布式要 传输延迟要求. 求，网络所有节点都具有独立传输数据的能力和 机器人在网络中简化运动规律如图2所示，机 方式； 器人在输电线路杆塔间移动，杆塔P,到P、+n(n, (2)机器人网络应能动态地根据机器人位姿信 N∈N·)的档段内做匀速直线运动，越过杆塔时作 息、传输延迟、能量损耗综合选择最佳传输节点与 低速越障运动或线路巡检任务.其运动符合沿输电 路径； 线路上的随机运动模型(random waypoint)【s),即路 (3)传输策略应充分满足机器人网络异构特 径约束随机运动模型(path-constraint random way- 性，提出满足异构网络特性的自适应算法； point).模型描述如下：假设运动区域为A,以杆塔 (4)制定高效的消息队列管理机制，合理控制 直线段组成约束路径为S,杆塔P,机器人单次运 消息副本数量，确定优先传输、失效时间等消息更新 动为匀速直线运动，在S上随机选取运动起点B 原则 与终点D且B、D应在同一直线段内，随机取运动 2消息传递机制 速率ue（vn,vm）作为此次运动速率.在D处 机器人随机取时间Tp∈（Tn,T)保持静止， 网络节点传输概率与转发概率表明机器人与中 完成一次运动过程.重复此运动过程并选定前次 心节点及其他节点通信的可能性，节点间的消息转 运动终点Dx点为下次运动起点Bx+1(X∈N),图 发机制依此进行.机器人根据接收其他节点广播能 回杆塔Pw O杆塔 量度量自身在网络中的位姿信息，并预测能量损耗 杆塔P 。运动端点 与传输延迟来计算机器人在网络中的传输概率与转 Q杆塔Pat 发概率 ○约束路径S 2.1机器人位姿信息计算 机器人利用网络中各节点信号强度感知机器人 D (Bxa 与广播节点相对位姿信息.假设机器人在一次运动 中接收3次中心节点定时广播，根据接收信号强度 计算机器人移动速率、网络相对位置、运动趋势等位 可运动区域A 姿信息.第i个机器人M,在线路杆塔P,处结束上 图2巡线机器人运动规律 次运动，设为下次运动起点B(x6,y。),任取从杆塔 Fig.2 Inspection robot movement rule Pw至Pwtn(n,N∈N)的直线路径，设杆塔Pxn为
工程科学学报,第 40 卷,第 11 期 图 1 巡线机器人网络模型 Fig. 1 Network model of inspection robot for high鄄voltage power transmission line (1)节点具有异构的通信能力,为降低能耗,机 器人与普通静态节点通信半径较小为 R,中心节点 可同时具有两种通信半径:普通静态节点通讯半径 R、大功率通讯半径 C,其中 2R < C. (2)机器人具有异构运动速度,机器人巡检作 业时根据线路环境、数据采集、能耗等因素调节运动 速度. 网络信息、巡检数据具有异构的数据容量与 传输延迟要求. 图 2 巡线机器人运动规律 Fig. 2 Inspection robot movement rule 机器人在网络中简化运动规律如图 2 所示,机 器人在输电线路杆塔间移动,杆塔 PN 到 PN + n ( n, N沂N * )的档段内做匀速直线运动,越过杆塔时作 低速越障运动或线路巡检任务. 其运动符合沿输电 线路上的随机运动模型(random waypoint) [15] ,即路 径约束随机运动模型( path鄄constraint random way鄄 point) . 模型描述如下:假设运动区域为 A,以杆塔 直线段组成约束路径为 S,杆塔 P,机器人单次运 动为匀速直线运动,在 S 上随机选取运动起点 B 与终点 D 且 B、D 应在同一直线段内,随机取运动 速率v沂( vmin , vmax) 作为此次运动速率. 在 D 处 机器人随机取时间 Tpause沂 (Tmin , Tmax) 保持静止, 完成一次运动过程. 重复此运动过程并选定前次 运动终点 DX点为下次运动起点 BX + 1 ( X沂N) ,图 2 中 DX + x表示第 X + x ( x, X沂N) 次运动的终点. 网络中所有机器人遵循上述运动过程,它们之间 运动相互独立. 1郾 2 数据传输策略问题描述 基于 DTMSN 与巡线机器人网络特点,高效的 数据传输策略与路由算法应考虑以下问题: (1)传输策略应满足机器人网络多跳分布式要 求,网络所有节点都具有独立传输数据的能力和 方式; (2)机器人网络应能动态地根据机器人位姿信 息、传输延迟、能量损耗综合选择最佳传输节点与 路径; (3)传输策略应充分满足机器人网络异构特 性,提出满足异构网络特性的自适应算法; (4)制定高效的消息队列管理机制,合理控制 消息副本数量,确定优先传输、失效时间等消息更新 原则. 2 消息传递机制 网络节点传输概率与转发概率表明机器人与中 心节点及其他节点通信的可能性,节点间的消息转 发机制依此进行. 机器人根据接收其他节点广播能 量度量自身在网络中的位姿信息,并预测能量损耗 与传输延迟来计算机器人在网络中的传输概率与转 发概率. 2郾 1 机器人位姿信息计算 机器人利用网络中各节点信号强度感知机器人 与广播节点相对位姿信息. 假设机器人在一次运动 中接收 3 次中心节点定时广播,根据接收信号强度 计算机器人移动速率、网络相对位置、运动趋势等位 姿信息. 第 i 个机器人 Mi在线路杆塔 PN处结束上 次运动,设为下次运动起点 B( xb, yb),任取从杆塔 PN至 PN + n (n, N沂N * )的直线路径,设杆塔 PN + n为 ·1414·
樊飞等：巡线机器人延迟容忍传感器网络数据传输策略 ·1415· 下次运动终点D(xu,ya).为简化，计算中设中心节 动模型计算得： 点布置在运动区域原点O(0,0),其他第i个静态节 r-a√-din 点坐标为Z(x,ya).在运动开始后机器人分别接 t= (6) 收到第a次，第b次，第c次，共3次间隔时长为 式中：r为通信距离：v为机器人移动速率；d,为当 、发送能量为E的中心节点与静态节点广播信号， 前通信距离，dn为最小通信距离；a为运动趋势系 机器人接收信号强度En分别为Eree、 数，当机器人趋近节点a=1,当机器人趋离节点 EaEe山Ea,其中，如Enn表示机器人接收中 a=-1. 心节点c的第a次的信号强度，En表示机器人接 针对中心节点与其他节点计算得，机器人与中 收普通静态节点z的第a次的信号强度，其余含义 心节点通信时长t,与第i个其他节点（除去中心节 类似.表示根据信号强度传播公式[6)： 点)通信时长t,综合机器人运动趋势条件结论 KE. 如下： (1) 由运动模型可知机器人t时间内运动位移相 2R--d正，当d<C,Ew<Ed ta= 等，设为s;由公式(1)计算出第a次，第b次，第c 次，共3次接收信号时刻距中心节点距离为dad.、 2R+VG-d;当dm<C,Em>Ed 0 d.·则机器人运动速率v为： (7) din da -2d R+C--d,当dm<C,E<Eed U=S 2 la= 1 12 R+C+园-d,当d<c,E>E (2) (8) 机器人与其他节点最小距离为da,其中与中 _2√(R+C)产-d (9) 心节点与静态节点距离分别为diin计算得： -2Eeea(Eeb+Eee） 2√AR-d= (10) diae2 式(9)~(10)中，tmm与t表示机器人由起点 1 (3) B(xb,yb)运动至终点D(x4,ya)过程中分别与中心 -2EE) 节点、第i个节点Z(x,y:)通信链路连接最大 dm=（+EE-2EEd 时长. E-y'kE. 111 在时间度量下的网络中节点利用率为剩余通信 (4) 时长占总通信时长的比例： 2.2消息传递算 刃=5 (11) 机器人由起点B(x6,y)运动至终点D(x,y) 过程中与第i个节点Z(x:,y:)通信链路连接最大 当满足条件m>0,t>0且-> 时长ts,根据运动模型计算得： 2E- -时，第i个机器人M,相比与中心节点通信， (5) 与邻居节点Z(x,y)通信能提高网络利用率、降 式中：d为节点到机器人运动轨迹最小通信距离， 低消息冲突、提高传输成功率，即满足公式(12)时， 普通静态节点取dmia,中心节点取dmn;rmm为最大 第i个机器人M,消息通过第i个节点Z(xa,y:)转 通信距离，普通静态节点通信距离取2R,中心节点 发比机器人M,与中心节点通信更有利于提高网络 取R+C. 节点利用率、网络消息负载均衡.由式(2)~ 设第i个机器人M,在作BD匀速直线运动过程 (11)得： 中，在时刻入与周围节点进行简单通信获取彼此基 2R+B R+C+aBa (12) 本信息，在入前与其他节点保持通信时长为t,由运 2√4R-dn2√(R+C)'-dn
樊 飞等: 巡线机器人延迟容忍传感器网络数据传输策略 下次运动终点 D(xd , yd ). 为简化,计算中设中心节 点布置在运动区域原点 O(0,0),其他第 i 个静态节 点坐标为 Z(xzi, yzi). 在运动开始后机器人分别接 收到第 a 次, 第 b 次, 第 c 次,共 3 次间隔时长为 t驻、发送能量为 Es的中心节点与静态节点广播信号, 机器人接收信号强度 Erec分别为 Erec鄄ca 、Erec鄄cb、Erec鄄cc、 Erec鄄za 、Erec鄄zb、Erec鄄zc,其中,如 Erec鄄ca表示机器人接收中 心节点 c 的第 a 次的信号强度,Erec鄄za表示机器人接 收普通静态节点 z 的第 a 次的信号强度,其余含义 类似. 表示根据信号强度传播公式[16] : d = 酌 KEs Erec (1) 由运动模型可知机器人 t驻 时间内运动位移相 等,设为 s;由公式(1)计算出第 a 次, 第 b 次, 第 c 次,共 3 次接收信号时刻距中心节点距离为 dca 、dcb、 dcc . 则机器人运动速率 v 为: v = s t驻 = d 2 ca + d 2 cb - 2d 2 cc 2 t驻 = 酌 2 KEs ( 1 Erec鄄ca + 1 Erec鄄cb - 2 Erec ) 鄄cc t驻 (2) 机器人与其他节点最小距离为 dmin ,其中与中 心节点与静态节点距离分别为 dcmin 、dzmin计算得: d 2 cmin = ( - 2Erec鄄ca (Erec鄄cb + Erec鄄cc) Erec鄄caErec鄄cc + Erec鄄cbErec鄄cc - 2Erec鄄caErec鄄cb + 1 Erec鄄ca - ) 1 4 酌 2KEs (3) d 2 zmin = ( - 2Erec鄄za (Erec鄄zb + Erec鄄zc) Erec鄄zaErec鄄zc + Erec鄄zbErec鄄cc - 2Erec鄄zaErec鄄zb + 1 Erec鄄za - ) 1 4 酌 2KEs (4) 2郾 2 消息传递算法 机器人由起点 B(xb, yb)运动至终点 D(xd , yd ) 过程中与第 i 个节点 Z(xzi, yzi)通信链路连接最大 时长 tmax,根据运动模型计算得: tmax = 2 r 2 max - d 2 min v (5) 式中:dmin为节点到机器人运动轨迹最小通信距离, 普通静态节点取 dzmin ,中心节点取 dcmin ;rmax为最大 通信距离,普通静态节点通信距离取 2R,中心节点 取 R + C. 设第 i 个机器人 Mi在作 BD 匀速直线运动过程 中,在时刻 姿 与周围节点进行简单通信获取彼此基 本信息,在 姿 前与其他节点保持通信时长为 t姿 ,由运 动模型计算得: t姿 = r - a d 2 姿 - dmin v (6) 式中:r 为通信距离;v 为机器人移动速率;d姿为当 前通信距离,dmin为最小通信距离;a 为运动趋势系 数,当机器人趋近节点 a = 1,当机器人趋离节点 a = - 1. 针对中心节点与其他节点计算得,机器人与中 心节点通信时长 t c姿 ,与第 i 个其他节点(除去中心节 点)通信时长 t zi姿 ,综合机器人运动趋势条件结论 如下: t zi姿 = 2R - d 2 zi姿 - d 2 zimin v ;当 dcmin < C,Erec鄄ca < Erec鄄cb 2R + d 2 zi姿 - d 2 zimin v ;当 dcmin < C,Erec鄄ca > Erec ì î í ï ïï ï ïï 鄄cb (7) t c姿 = R + C - d 2 c姿 - d 2 cmin v ;当 dcmin < C,Erec鄄ca < Erec鄄cb R + C + d 2 c姿 - d 2 cmin v ;当 dcmin < C,Erec鄄ca > Erec ì î í ï ïï ï ïï 鄄cb (8) t cmax = 2 (R + C) 2 - d 2 cmin v (9) t zimax = 2 4R 2 - d 2 zimin v (10) 式(9) ~ (10)中,t cmax与 t zimax表示机器人由起点 B(xb, yb)运动至终点 D(xd , yd )过程中分别与中心 节点、第 i 个节点 Z ( xzi, yzi ) 通信链路连接最大 时长. 在时间度量下的网络中节点利用率为剩余通信 时长占总通信时长的比例: 浊 = tmax - t姿 tmax (11) 当满足条件 t zimax > 0, t cmax > 0 且 t zimax - t zi姿 t zimax > t cmax - t c姿 t cmax 时,第 i 个机器人 Mi相比与中心节点通信, 与邻居节点 Z( xzi, yzi)通信能提高网络利用率、降 低消息冲突、提高传输成功率,即满足公式(12)时, 第 i 个机器人 Mi消息通过第 i 个节点 Z( xzi, yzi)转 发比机器人 Mi与中心节点通信更有利于提高网络 节点利 用 率、 网 络 消 息 负 载 均 衡. 由 式 ( 2 ) ~ (11)得: 2R + 琢茁zi姿 2 4R 2 - d 2 zimin < R + C + 琢茁c姿 2 (R + C) 2 - d 2 cmin (12) ·1415·
·1416· 工程科学学报，第40卷，第11期 式中， 3消息队列管理 l;当dmn<C,Eeu>或<R,>Eeah a--l,当d<c,Bnn<Eb或d<R,Ea>Eme 无线传感器网络中，消息在传递至下一节点后 B=-心，B=Y延-心，其中a、 自动删除.由于动态节点的存在，DTMSN消息的传 递不同于前者，节点消息传递后仍以消息副本的形 BB为简化公式(12)的计算过程变量，无物理含 式存储在原节点.DTMSNR大量的消息副本保存在 义，变量中的i表示第i个静态节点的相关变量值， 消息队列中，需对网络节点消息合理分类与管理. 如En表示机器人接收第i个普通静态节点z的 本文采用消息失效时间、机器人消息优先传输机制 第a次的信号强度，变量Eea表示机器人接收第i 进行队列管理 个普通静态节点z的当前时刻信号强度，变量Ea 3.1消息丢弃原则 表示机器人接收中心节点的当前时刻信号强度，变 消息失效时间(out of survival time,OT)即消息 量E。、E分别表示当前时刻静态节点与中心节点 在网络中生存时间(survival time,ST)超过网络延 广播信号的发送能量. 迟容忍限度(delay tolerant value,DTV)的时间.消 巡线机器人DTMSN中第i个机器人M,消息依 息失效时间在网络中随着消息的传播增大，同时消 据传输概率进行转发，其通信范围内有n(n>1,n 息传输成功率逐步加大，同时产生更多的消息副本. ∈N)个邻居节点.第i个机器人M的直接传输概 机器人网络中节点容量一定，当节点消息队列容量 率u表明机器人直接与中心节点O通信的可能性， 达到上限且收到新消息，节点依据消息失效时间大 机器人M,由第i个静态节点Z,转发概率u表明机 小，对最大OT消息进行清空.同时节点定时对消息 器人静态节点Z转发消息给中心节点通信的可能 队列进行筛查，完成消息队列的更新.节点在新消 性.u。4由机器人位姿信息ω(Z)决定： 息生成时，在消息头部加入消息DTV与ST,且ST 4:=w(Z) (13) 初值为0.DTMSN节点的定时器触发一次，ST自增 由公式(11)可知，第i个机器人的相对中心节 1,当ST值超过DTV后，0T自增1，由于消息在空气 点位姿因子w(Z.)与静态节点位姿因子w(Z)分 中传播时间非常短，则消息转发过程不影响ST及 别为： 0T. 3.2机器人消息优先原则 w(Z.)=1- R+C+aB (14) 2R+C)'-d 在DTMSNR中，来自机器人的消息，如线路信 息、机器人状态信息等总是最重要的信息.为提高 w(Za)=1 2R+aBi (15) 2√4R-dmn 机器人消息传输成功率，消息的传输采用机器人消 第i个机器人M,在消息j传输前，先与k(k≥1， 息优先原则，即节点先传输机器人消息，再发送自身 消息，最后传递其他节点消息，且消息在队列中的次 k∈N)个邻居节点Z,Z2,…,Z进行握手通信，其 中邻居节点集合为Φ={Z:I1≤i≤k,i∈N,k∈ 序依据ST值由小及大排列. 3.3消息队列管理方法 N},获得直接传输概率u。及转发概率u:,机器人 M将邻居节点传输、转发概率进行大小比较后，按 巡线机器人DTMSN中，节点消息队列消息来 照概率由大到小依次将消息传输给第；个邻居节点 源如图4所示，主要分3个部分. (1)节点接收到机器人消息后，将机器人消息 Z.传输算法如图3所示 巾=0 插入到消息队列头部： for i=l:i<k:i++do (2)节点自身传感器发来消息后，依次插入到 if4a<μthen 消息队列尾部： 小=中UZ (3)节点接收到其他非机器人节点产生的消息 end if 后，依次插入到消息队列尾部 end for 消息在消息队列中传递按列头至列尾进行，消 forj=1;j≤lhl++do 息被传递至下一节点，将以消息副本形式保存至队 forward message (j.) end for 列尾部.消息ST值大于DTV后OT值增长，OT值 图3传输算法伪码 越大消息被丢弃概率越高.消息寿命通过赋予不同 Fig.3 Pseudo-code of the transmission algorithm DTV值调节OT增长来控制.对于紧急消息可直接
工程科学学报,第 40 卷,第 11 期 式中, 琢 = 1;当 dcmin < C,Erec鄄ca > Erec鄄cb或 dzimin < R,Erec鄄zia > Erec鄄zib - 1;当 dcmin < C,Erec鄄ca < Erec鄄cb或 dzimin < R,Erec鄄zia > Erec { 鄄zib , 茁zi姿 = 酌 2KEsz姿 Erec鄄zi姿 - d 2 zimin , 茁c姿 = 酌 2KEsc姿 Erec鄄c姿 - d 2 cmin ,其中 琢、 茁zi姿 、茁c姿为简化公式(12)的计算过程变量,无物理含 义,变量中的 i 表示第 i 个静态节点的相关变量值, 如 Erec鄄zia表示机器人接收第 i 个普通静态节点 z 的 第 a 次的信号强度,变量 Erec鄄zi姿表示机器人接收第 i 个普通静态节点 z 的当前时刻信号强度,变量 Erec鄄c姿 表示机器人接收中心节点的当前时刻信号强度,变 量 Esz姿 、Esc姿分别表示当前时刻静态节点与中心节点 广播信号的发送能量. 巡线机器人 DTMSN 中第 i 个机器人 Mi消息依 据传输概率进行转发,其通信范围内有 n( n > 1, n 沂N)个邻居节点. 第 i 个机器人 Mi的直接传输概 率 滋ci表明机器人直接与中心节点 O 通信的可能性, 机器人 Mi由第 i 个静态节点 Zi转发概率 滋zi表明机 器人静态节点 Zi转发消息给中心节点通信的可能 性. 滋ci、滋zi由机器人位姿信息 棕(Z)决定: 滋i = 棕(Z) (13) 由公式(11)可知,第 i 个机器人的相对中心节 点位姿因子 棕(Zci)与静态节点位姿因子 棕(Zzi)分 别为: 棕(Zci) = 1 - R + C + 琢茁c姿 2 (R + C) 2 - d 2 cmin (14) 棕(Zzi) = 1 - 2R + 琢茁zi姿 2 4R 2 - d 2 zimin (15) 第 i 个机器人 Mi在消息 j 传输前,先与 k(k逸1, k沂N)个邻居节点 Z1 , Z2 , …, Zk进行握手通信,其 中邻居节点集合为 椎 = {Zi | 1臆i臆k, i沂N, k沂 N},获得直接传输概率 滋ci 及转发概率 滋zi,机器人 Mi将邻居节点传输、转发概率进行大小比较后,按 照概率由大到小依次将消息传输给第 i 个邻居节点 Zi . 传输算法如图 3 所示. 椎 = 0 for i = 1;i < k;i + + do if 滋ci < 滋zi then 椎 = 椎胰Zi end if end for for j = 1; j臆| 椎 | ;j + + do forward message (j,椎n ) end for 图 3 传输算法伪码 Fig. 3 Pseudo鄄code of the transmission algorithm 3 消息队列管理 无线传感器网络中,消息在传递至下一节点后 自动删除. 由于动态节点的存在,DTMSN 消息的传 递不同于前者,节点消息传递后仍以消息副本的形 式存储在原节点. DTMSNR 大量的消息副本保存在 消息队列中,需对网络节点消息合理分类与管理. 本文采用消息失效时间、机器人消息优先传输机制 进行队列管理. 3郾 1 消息丢弃原则 消息失效时间(out of survival time, OT)即消息 在网络中生存时间( survival time, ST) 超过网络延 迟容忍限度( delay tolerant value, DTV)的时间. 消 息失效时间在网络中随着消息的传播增大,同时消 息传输成功率逐步加大,同时产生更多的消息副本. 机器人网络中节点容量一定,当节点消息队列容量 达到上限且收到新消息,节点依据消息失效时间大 小,对最大 OT 消息进行清空. 同时节点定时对消息 队列进行筛查,完成消息队列的更新. 节点在新消 息生成时,在消息头部加入消息 DTV 与 ST,且 ST 初值为 0. DTMSN 节点的定时器触发一次,ST 自增 1,当 ST 值超过 DTV 后,OT 自增 1,由于消息在空气 中传播时间非常短,则消息转发过程不影响 ST 及 OT. 3郾 2 机器人消息优先原则 在 DTMSNR 中,来自机器人的消息,如线路信 息、机器人状态信息等总是最重要的信息. 为提高 机器人消息传输成功率,消息的传输采用机器人消 息优先原则,即节点先传输机器人消息,再发送自身 消息,最后传递其他节点消息,且消息在队列中的次 序依据 ST 值由小及大排列. 3郾 3 消息队列管理方法 巡线机器人 DTMSN 中,节点消息队列消息来 源如图 4 所示,主要分 3 个部分. (1)节点接收到机器人消息后,将机器人消息 插入到消息队列头部; (2)节点自身传感器发来消息后,依次插入到 消息队列尾部; (3)节点接收到其他非机器人节点产生的消息 后,依次插入到消息队列尾部. 消息在消息队列中传递按列头至列尾进行,消 息被传递至下一节点,将以消息副本形式保存至队 列尾部. 消息 ST 值大于 DTV 后 OT 值增长,OT 值 越大消息被丢弃概率越高. 消息寿命通过赋予不同 DTV 值调节 OT 增长来控制. 对于紧急消息可直接 ·1416·