水环境无线传感网中的分布式招募调度算法

林志贵，程晓伟，刘英平，王 鹏，王 玺

（1.天津工业大学电子与信息工程学院，天津300387；2.国家海洋技术中心近海海洋环境观测与监测技术研究室，天津300112；3.天津工业大学机械工程学院，天津300387；4.天津工业大学现代机电装备技术天津市重点实验室，天津300387）

水环境无线传感网中的分布式招募调度算法

林志贵1，2，程晓伟1，刘英平3，4，王 鹏2，王 玺1

（1.天津工业大学电子与信息工程学院，天津300387；2.国家海洋技术中心近海海洋环境观测与监测技术研究室，天津300112；3.天津工业大学机械工程学院，天津300387；4.天津工业大学现代机电装备技术天津市重点实验室，天津300387）

针对基于测距的睡眠调度算法（RBSS）招募节点能耗大，导致网络过快失效问题，结合水环境无线传感网规则部署，采用分布式思想，提出一种基于测距的分布式招募调度算法（RBDRS）.RBDRS算法采用分布式招募方法，将协作节点招募的任务转移到新招募的协作节点上，均衡网络能耗.招募节点通过测距招募距其最远的邻居节点作为协作节点，协作节点再依次为招募节点招募新的协作节点，直至无法招募到新的协作节点.仿真实验结果表明：与RBSS算法相比，RBDRS算法可均衡网络能耗，延长网络生命周期.

节点调度；RBDRS；分布式招募；水环境无线传感网

近年来，一些学者将无线传感器技术应用于水环境监测，形成水环境无线传感网[1-2].利用廉价的无线传感器节点监测数据并组建网络，形成对水环境的区域监测，获得水环境区域状况.这对于水环境监测来说，由点监测扩展到面监测，具有里程碑意义.

水环境无线传感网中，除了突发事件（如污染物排放、油轮泄漏等）外，数据变化缓慢，节点通常采用规则的部署方式.为了保证网络的全覆盖、稳定性，部署节点有一定的冗余.如果这些冗余节点没有好的调度，节点可能发送相同的信息，造成节点能量的浪费以及网络拥堵.节点调度[3-7]通过一定方法对网络中的节点进行分组，在不影响区域覆盖、通信质量、任务等前提下，使一部分节点处于活跃状态而另一部分节点进入休眠状态，节省节点能量，延长网络的生命周期.

与位置无关的节点调度算法中，节点的位置信息无需作为已知条件，节点通过与邻居节点交换信息，获取邻居节点个数、距离等信息判断节点是否为冗余节点.Kumar等[8]通过研究k度覆盖、网络区域面积、节点感知半径、网络生命周期和初始部署节点数量、节点休眠概率之间的关系，提出一种随机独立休眠调度算法，可实现k度覆盖，实现简单，但所需初始节点数量较大.Wu等[9]研究邻居节点数目与网络覆盖率之间的关系，提出一种轻量级节点调度算法.根据需求覆盖率计算所需邻居节点数目，去除多余邻居节点，实现减少冗余工作节点的目的.该算法在执行过程中，节点间需要频繁交换邻居节点信息，易造成能量消耗和网络拥堵.Yen等[10]提出一种与地理位置无关的基于测距的睡眠调度算法（RBSS），假设网络区域中的节点均匀随机部署，节点通信半径为感知半径的倍时，RBSS算法通过测距在已部署节点中寻找和逼近正六边形覆盖模型，保证网络的覆盖率和连通性，但是RBSS算法未考虑节点调度过程中招募节点能耗过大，导致招募节点过早死亡，影响网络生命周期情况.

从搜索文献看，目前针对水环境无线传感网的节点调度算法尚未见报道.本文针对RBSS算法中由招募节点发布协作节点招募消息，节点频繁发送和接收数据，导致能量消耗过快及网络过快失效，基于分布式思想，结合水环境无线传感网规则部署，提出基于测距的分布式招募调度算法（RBDRS）.

1 假设条件及问题描述

1.1 相关假设

本文对水环境无线传感网做出如下假设：网络区域为一个二维平面上的正方形区域；网络中节点同构，节点具有相同的感知半径Rs和通信半径Rt；节点采用布尔感知模型（0-1模型），即感知半径Rs内发生的事件以概率1感知，Rs外发生的事件不能感知，概率为0；节点可实现时间同步，利用节点间的无线信号强度计算邻近节点间的距离，节点不具备获取位置信息及移动能力；网络内的节点采用随机分布，存在大量冗余节点，不存在孤立节点.

1.2 问题描述

文献[11]已证明二维区域正六边形覆盖模型，且节点通信半径大于或等于倍感知半径，可获得最小全覆盖且连通.对于节点调度来说，实现正六边形覆盖问题转化为当Rs时，如何选择中心工作节点S，以及如何围绕节点S寻找6个相距Rt的邻居工作节点C1—C6的问题.中心工作节点S称为招募节点、6个邻居工作节点称为协作节点，如图1所示.

图1 正六边形部署示意图Fig.1 Schematic of network hexagonal deployment

2 RBDRS算法设计

2.1 基本思想

RBDRS算法将网络生命周期划分为长度相同的若干轮，每轮开始时执行节点调度策略，如图2所示.

图2 RBDRS调度策略示意图Fig.2 Scheduling policy schematic of RBDRS algorithm

假设节点S1竞争成为招募节点，其余节点等待被招募节点招募为协作节点或满足睡眠条件进入睡眠状态.S1发出协作节点招募消息，S1的邻居节点判断其与S1的距离，如果距离小于Dm（Dm=Rt/2，2个工作节点间的最小距离），节点在本轮进入睡眠状态；如果距离大于Dm，则节点发送协作节点响应.招募节点S1收到协作节点响应消息后，选择距其最远的节点C11作为协作节点.C11发送协作节点请求消息，为S1招募新的协作节点.只有S1的邻居节点响应C11的请求消息，收到请求消息的节点睡眠规则与节点S1相同.依次类推，招募C12—C16为协作节点.如果C16无法招募到协作节点，则由C11发送协作节点招募消息.如果C11也无法招募到协作节点，则由招募节点S1发送协作节点招募消息.如果S1也无法再招募到协作节点，则本轮招募结束，招募节点和协作节点都进入工作状态.

2.2 算法结构

RBDRS算法将网络时间划分为相同时长的轮，如图3所示.每轮开始为招募节点竞争阶段，任意节点都可通过竞争成为招募节点，招募节点间不互为邻居节点，即每个招募节点的传输范围内不存在其它招募节点.其后，进入招募协作节点阶段，招募节点按照招募协议招募协作节点.最后，招募节点和协作节点作为工作节点执行任务，其余节点进入睡眠状态，直至本轮结束.网络中每个节点拥有自己独立的ID号以及邻居节点表和工作节点表.邻居节点表用来保存当前已知邻居节点的ID号和节点距离.工作节点表用来保存当前已知招募节点和协作节点的ID号和节点距离.

图3 节点调度时间结构图Fig.3 Chart of nodes scheduling time

2.3 算法流程

节点依据不同条件，其状态可以相互转换，如图4所示.

图4 节点状态转换图Fig.4 Transition diagram of node states

2.3.1 招募节点竞争

每轮开始 ，节点进入招募节点竞争阶段，经过一段随机延时后，节点周期性发送招募节点请求消息，直至节点竞争成功或失败.招募节点竞争流程图如图5所示.首先对本轮调度过程中所用变量进行初始化，包括邻居节点表、工作节点表和招募节点ID初始化等.等待调度开始信号.接收到开始调度信号后，启动本轮调度总计时器，随机延时，执行招募节点竞争程序.在招募节点竞争过程中，如果节点始终未接收到其他节点的招募节点竞争消息，则节点成为招募节点，招募节点ID设置为本机ID，工作状态修改为协作节点招募状态；反之，节点成为普通节点，节点状态修改为普通节点.

图5 招募节点竞争流程图Fig.5 Flowchart of competing recruitment node

2.3.2 协作节点招募

节点成为招募节点或协作节点后，进入协作节点招募状态.节点首先发送协作节点招募消息，启动定时Ts，Ts为2次数据接收的最长间隔时间.在Ts延时内，节点循环查询接收标志位.如果接收到数据，则对接收到的数据进行处理.如果为协作节点响应消息，比较接收到数据的距离和本地存储的最大距离，保存两者中较大的距离，及其相应的节点ID.重新启动定时Ts，等待接收新的协作节点响应消息.

如果在Ts延时内，节点未收到新的协作节点响应消息，则节点判断是否招募到新的协作节点.如果招募到新的协作节点，发送协作节点确认消息，如果发送确认消息的节点是由招募节点招募到的，节点状态修改为招募完成状态，否则节点状态修改为工作状态.如果没有招募到新的协作节点，节点状态修改为工作状态，开始环境监测工作.协作节点招募流程图如图6所示.

2.3.3 普通节点（待招募）

节点在招募节点竞争过程中失败，成为普通节点，等待被招募为协作节点或进入休眠状态.等待被招募的过程中，节点循环查询接收标志位.如果接收到数据，计算发送数据节点与本节点之间的距离，对接收到的数据进行解析，判断为何种指令消息.指令消息共分为3种：协作节点请求消息、协作节点响应消息和协作节点确认消息.普通节点流程图如图7所示.

图6 协作节点招募流程图Fig.6 Flowchart of cooperating recruitment nodes

图7 普通节点流程图Fig.7 Flowchart of ordinary nodes

（1）如果收到消息为协作节点请求消息，判断节点距离是否小于Dm（两个工作节点间的最小距离）.如果节点距离不大于Dm，节点直接进入睡眠状态；否则计算协作节点响应延时Tr，打包协作节点响应消息，启动定时Tr.Tr延时结束后，发送协作节点响应消息.

（2）如果收到消息为协作节点响应消息，节点判断本身是否已启动定时Tr，即是否接收到协作节点请求消息.如果没有启动定时Tr，则对该响应消息不做处理.如果该消息为本网络协作节点响应消息，则比较本节点Tr与接收到响应消息中Tr大小.如果本节点Tr大于接收到响应消息中Tr，则表明发布响应消息的节点比本节点更适合成为协作节点（该节点距离招募节点更远），本节点停止定时Tr，取消协作节点响应消息发送，否则继续等待Tr延时后，发送协作节点响应消息.

（3）如果收到消息为协作节点确认消息，则节点更新工作节点表，消息中的协作节点ID是否为本节点ID.如果本节点成为协作节点，则更新招募节点ID为消息中的招募节点ID，节点状态修改为协作节点招募状态.

2.3.4 招募完成

如果节点为招募节点，或招募节点招募的协作节点，则节点在招募到协作节点后进入招募完成状态.招募完成流程图如图8所示.节点进入招募完成状态，启动定时Tw.在延时Tw到达前，节点循环查询接收标志位，如果收到数据，则判断是否为协作节点确认消息.如果是协作节点确认消息，更新工作节点表，判断是否为本网络协作节点确认消息，如果是，则重启定时Tw，否则，不做处理.延时Tw完成后，判断是否第一次进入招募完成状态，如果是，表明节点还没有更改招募方向，则节点状态修改为协作节点请求状态.如果不是，表明节点在更改招募方向后，再次没有招募到新的协作节点，则节点修改为工作状态.

2.3.5 工作或睡眠状态

节点进入工作状态，开始执行水环境监测任务，直至本轮结束，节点状态修改为招募节点竞争状态，开始下一轮招募.工作状态流程图如图9所示.节点进入睡眠状态，关闭收发器，直至本轮结束，节点状态修改为招募节点竞争状态，开始下一轮招募.睡眠状态流程图如图10所示.

图8 招募完成流程图Fig.8 Flowchart of recruitment completion

图9 工作状态流程图Fig.9 Flowchart of working state

图10 睡眠状态流程图Fig.10 Flowchart of sleep state

3 仿真与分析

实验仿真基于Matlab仿真平台.网络规模为50m× 50 m，随机部署终端节点9个，数据传输错误率和丢包率均为0，节点感知半径Rs为10 m，通信半径Rt为17 m.节点感知模型为圆形，节点具备测距能力，节点初始能量为1 J，所有节点起始时均为唤醒状态.为了便于计算网络覆盖率，将网络划分为1 m×1 m的方格，如果方格的中心被某个节点感知到，则认为方格区域被覆盖[12].覆盖率为被覆盖方格数与划分的方格总数比值.如果网络是分割的，则只计算拥有最多连通节点（最大覆盖率）的区域.

3.1 网络覆盖情况

网络覆盖情况如图11所示.基于RBSS算法的网络覆盖情况如图11（a）所示.由图11（a）可以看出，网络工作节点数为7个，其中招募节点1个，协作节点6个，睡眠节点2个，节点5竞争成为招募节点，在其邻居节点中依次招募距其最远的6个节点作为协作节点.

图11 网络覆盖情况图Fig.11 Figure of network coverage

基于RBDRS算法的网络覆盖情况如图11（b）所示.由图11（b）可以看出，网络工作节点数为7个，其中招募节点3个，协作节点4个，睡眠节点2个，网络覆盖模型近似正六边形.RBDRS算法招募节点数大于RBSS算法，减少节点频繁发送和接收数据带来能量消耗.比较图11（a）和图11（b），与BRSS算法相比，基于RBDRS算法的网络覆盖模型更加趋近于正六边形覆盖.

3.2 网络生命周期

随着时间延长，网络中的部分节点因能量的耗尽而死亡.需要进一步对网络生命周期进行分析，假定所有节点时间同步，每100 s（轮）存活节点同时唤醒，执行节点调度算法，决定节点在本轮的工作状态（睡眠或工作）.

RBSS算法和RBDRS算法的网络覆盖率随时间变化曲线如图12所示.当网络覆盖率小于50%时，认为网络失效.比较图12（a）和图12（b）可以看出，当时间超过3 040 s时，RBSS算法的网络覆盖率小于50%，而RBDRS算法需要时间超过6 420 s.与RBSS算法相比，RBDRS算法的网络有效时间延长了111%.造成这种结果原因在于，在算法执行过程中，RBSS算法总是由招募节点来发布协作节点招募消息，节点频繁发送和接收数据，导致能量消耗过快，一般招募节点连续工作两轮后就会死亡.RBDRS算法的协作节点招募消息由每次新招募的协作节点发布，将数据发送所消耗的能量平均分给每个协作节点，使整个网络的节点能量消耗更加均衡，有效地延长网络生命周期.

图12 网络覆盖率随时间变化曲线Fig.12 Curve of network coverage with times

4 结语

基于测距的睡眠调度算法（RBSS）通过招募节点进行节点调度，招募节点能耗过大，造成其过早死亡，影响网络的生命周期.针对这个问题，本文基于分布式思想，结合水环境无线传感网通常采用的规则部署，提出基于测距的分布式招募调度算法（RBDRS）.给出了该算法适用的假设条件，基于正六边形节点覆盖模型，RBDRS算法考虑到招募节点在算法执行过程中能量消耗过高而导致节点快速死亡的情况，将协同节点招募的任务转移到每个新招募的协作节点上，使网络的能量消耗更加均衡.

仿真实验结果表明，与RBSS算法相比，RBDRS算法均衡网络能耗，延长网络生命周期.

[1]郭忠文，罗汉江，洪锋，等.水下无线传感器网络的研究进展[J].计算机研究与发展，2010，47（3）：377-389.

[2]ALBALADEJO Cristina,SANCHEZ Pedro,IBORRA Andrés, et al.Wireless sensor networks for oceanographic monitoring：A systematic review[J].Sensor，2010，10（7）：6948-6968.

[3]XUE Weilian,CHI Zhongxian.A flexible node scheduling scheme of minimum delay and energy efficient for wireless sensor networks[J].International Journal of Parallel，Emergent and Distributed Systems，2012，27（2）：123-131.

[4]KHOSRAVI Hamid.Optimal node scheduling for desired percentage of coverage in wireless sensor networks[J].Wireless Sensor Network，2012，4（5）：127-132.

[5]胡湘华，杨学军.传感网节点调度方法综述[J].计算机工程与科学，2008，30（3）：93-96，129.

[6]洪锋，褚红伟，金宗科，等.无线传感器网络应用系统最新进展综述[J].计算机研究与发展，2010，47（S2）：81-87.

[7]陆游，禹素萍，姜华，等.一种能量可计算的星型无线传感器网络协议[J].天津工业大学学报，2013，32（4）：60-65.

[8]KUMAR Santosh，LAI Ten H，BALOGH Jozsef.On k coverage in a mostly sleeping sensor network[J].Wireless Networks，2003，14（3）：277-294.

[9]WU Kui，GAO Yong，LI Fulu，et al.Lightweight deploymentaware scheduling for wireless sensor networks[J].Mobile Networks and Applications，2005，10（6）：837-852.

[10]YEN Lihsing，CHENG Yangmin.Range-based sleep scheduling（RBSS）for wireless sensor networks[J].Wireless Personal Communications，2009，48（3）：411-423.

[11]赵仕俊，张朝晖.无线传感器网络正六边形节点覆盖模型研究[J].计算机工程，2010，36（20）：113-115，118.

[12]王玺.无线传感监测网节点调度算法研究及应用[D].天津：天津工业大学，2015.

Distributed recruit scheduling algorithm in water environment wireless sensor network

LIN Zhi-gui1，2，CHENG Xiao-wei1，LIU Ying-ping3，4，WANG Peng2，WANG Xi1
（1.School of Electronics and Information Engineering，Tianjin Polytechnic University，Tianjin 300387，China；2.Laboratory of Marine Environment Observation and Monitoring Technology of Offshore，National Ocean Technology Center，Tianjin 300112，China；3.School of Mechanical Engineering，Tianjin Polytechnic University，Tianjin 300387，China；4.Tianjin City Key Laboratory of Modern Mechatronics Equipment Technology，Tianjin Polytechnic University，Tianjin 300387，China）

Aiming at the problem of the range-based sleep scheduling algorithm（RBSS），which the energy consumption of recruit node is too large and affects the network life cycle，on the basis of the regular coverage model in water environment wireless sensor network，combined with the distributed thinking，a Range Based Distributed Recruit Scheduling（RBDRS）is proposed.The RBDRS algorithm adopts method of distributed recruitment，which transferrs recruited task of cooperating nodes to new-recruitment cooperative nodes in order to balance network energy consumption.Recruitment nodes recruit its farthest neighbor nodes as collaborative nodes by their distance，collaborative nodes recruit new collaborative nodes for recruitment nodes in turn until they are unable to recruit new collaborative nodes.Simulation results show that compared with the RBSS algorithm，the RBDRS algorithm can effectively balance network energy consumption and prolong the network lifetime.

node scheduling；range based distributed recruit scheduling（RBDRS）；distributed recruitment；water environment wireless sensor networks

TN929.3

A

1671－024X（2015）06－0061－06

10.3969/j.issn.1671-024x.2015.06.013

2015-07-16

国家自然科学基金资助项目（61372011）

林志贵（1974—），男，副教授，硕士生导师，主要研究方向为无线传感网络及智能信息处理.E-mail：linzhigui@tjpu.edu.cn