2. 天津工业大学天津市光电检测技术与系统重点实验室, 天津 300387;
3. 国家海洋技术中心近海海洋环境观测与监测技术研究室, 天津 300112
2. Tianjin Key Laboratory of Optoelectronic Detection Technology and Systems, Tianjin Polytechnic University, Tianjin 300387, China;
3. Laboratory of Marine Environment Observation and Monitoring Technology of Offshore, National Ocean Technology Center, Tianjin 300112, China
1 引言
无线传感器网络中，高密度、高冗余度的节点部署，保证网络的全覆盖、稳定性.如果这些高密度、高冗余度的节点没有好的调度，节点可能发送相同的信息，造成节点能量的浪费及网络拥堵.有学者采用节点调度方法解决这些问题[1-6].节点调度通过一定的方法对网络中的节点进行分组，在不影响区域覆盖、通信质量、任务等前提下，使一部分节点处于活跃状态而另一部分节点进入休眠状态，节省节点能量，延长网络的生命周期.
节点调度算法可分为与位置相关的节点调度算法和与位置无关的节点调度算法两大类.基于地理位置的节点调度算法通过获取节点精确的地理位置信息计算节点的覆盖区域和冗余度，实现节点调度，如启发式的基于最大化互斥集合个数的算法(MCMCC)[7]、最优地理密度控制算法(OGDC)[8]等.此类算法通常采用全球定位系统GPS或其它定位机制获取节点的精确位置信息，节点成本高，定位消耗能量.
与位置无关的节点调度算法中，节点位置信息无需作为已知条件，节点通过与邻居节点交换信息，获取邻居节点数、距离等信息判断节点是否为冗余节点.Kumar等[9]通过研究k度覆盖、网络区域面积、节点感知半径、网络生命周期和初始部署节点数量、节点休眠概率之间的关系，提出一种随机独立休眠调度算法，可实现k度覆盖，实现简单，但所需初始节点数量较大.Wu等[10]研究邻居节点数目与网络覆盖率之间的关系，提出一种轻量级节点调度算法.根据需求覆盖率计算所需邻居节点数目，去除多余邻居节点实现减少冗余工作节点的目的.该算法在执行过程中，节点间需要频繁交换邻居节点信息，易造成能量消耗和网络拥堵.Yen等[11]提出一种与地理位置无关的基于测距的睡眠调度算法(RBSS)，假设网络区域中的节点均匀随机部署，节点通信半径为感知半径的3倍，RBSS算法可以通过测距在已部署节点中寻找和逼近正六边形覆盖模型，保证网络的覆盖率和连通性，但是RBSS算法未考虑节点调度过程中招募节点能耗过大，导致招募节点过早死亡，影响网络生命周期情况.
针对RBSS算法中总是由招募节点发布协作节点招募消息，节点频繁发送和接收数据，导致能量消耗过快及网络过快失效，本文基于能量均衡思想，提出基于测距的均衡式招募调度算法(RBDRS).RBDRS通过节点间距离，选择合适协作节点，将协作节点招募的任务转移到新招募的协作节点上，均衡网络能耗.
2 假设条件及问题描述 2.1 相关假设本文对无线传感器网络做出如下假设： 网络区域为一个二维平面的正方形区域； 网络中节点同构，节点具有相同的感知半径RS和通信半径Rt； 节点采用布尔感知模型(0-1模型)，即感知半径RS内发生的事件以概率1感知，RS外发生的事件不能感知，概率为0； 节点可实现时间同步，利用节点间的无线信号强度来计算邻近节点间的距离信息，节点不具备获取位置信息及移动能力； 网络内的节点采用随机分布，存在大量冗余节点，不存在孤立节点.
2.2 问题描述文[12]已证明二维区域正六边形覆盖模型且节点通信半径大于或等于$\sqrt{3}$倍感知半径，可获得最小全覆盖且连通.对于节点调度来说，实现正六边形覆盖问题转化为当${{R}_{\text{t}}}\text{=}\sqrt{3}{{R}_{\text{S}}}$时，如何选择中心工作节点S及如何围绕节点S寻找6个相距Rt的邻居工作节点C1~C6的问题.中心工作节点S称为招募节点、6个邻居工作节点称为协作节点，如图 1所示.
|
| 图 1 正六边形部署示意图 Figure 1 Sketch map of hexagonal deployment |
RBDRS算法将网络生命周期划分为长度相同的若干轮，每轮开始时执行节点调度策略，如图 2所示.假设节点通信半径等于$\sqrt{3}$倍感知半径，节点S1竞争成为招募节点，其余节点等待被招募节点招募为协作节点或满足睡眠条件进入睡眠状态.S1发出协作节点招募消息，S1的邻居节点判断其与S1的距离，如果距离小于Dm(Dm=Rt/2，两个工作节点间的最小距离)，节点在本轮进入睡眠状态； 如果距离大于Dm，则节点发送协作节点响应.招募节点S1收到协作节点响应消息后，选择距其最远的节点C11作为协作节点.C11发送协作节点请求消息，为S1招募新的协作节点.只有S1的邻居节点响应C11的请求消息，收到请求消息的节点睡眠规则与节点S1相同.依次类推，招募C12~C16为协作节点.节点S1及对应的6个协作节点依据文[12]实现该区域的正六边形覆盖.如果C16无法招募到协作节点，则由C11发送协作节点招募消息.如果C11也无法招募到协作节点，则由招募节点S1发送协作节点招募消息.如果S1也无法再招募到协作节点，则本轮招募结束，招募节点和协作节点都进入工作状态.
|
| 图 2 RBDRS调度策略示意图 Figure 2 Sketch figure of RBDRS scheduling policy |
RBDRS算法将网络时间划分为相同时长的轮，如图 3所示.每轮开始为招募节点竞争阶段，任意节点都可通过竞争成为招募节点，招募节点间不互为邻居节点，即每个招募节点的传输范围内不存在其它招募节点.其后，进入招募协作节点阶段，招募节点按照招募协议招募协作节点.最后，招募节点和协作节点作为工作节点执行任务，其余节点进入睡眠状态，直至本轮结束.网络中每个节点拥有自己独立的ID号及邻居节点表和工作节点表.邻居节点表用来保存当前已知邻居节点的ID号和节点距离.工作节点表用来保存当前已知招募节点和协作节点的ID号和节点距离.节点依据不同条件，其状态可以相互转换，如图 4所示.
|
| 图 3 节点调度时间结构图 Figure 3 Time structure chart of node scheduling |
|
| 图 4 节点状态转换图 Figure 4 Transition diagram of nodes status |
每轮开始时，每个节点都进入招募节点竞争阶段，经过一段随机延时后，节点以周期Tf发送招募节点请求消息，直至节点竞争成功或失败.假如节点在招募节点竞争阶段没有收到来自其它节点的招募节点请求消息，则该节点竞争成功，成为招募节点.否则，竞争失败，退出招募节点竞争阶段，进入等待状态.
(1) 协作节点请求消息处理.协作节点请求阶段示意图如图 5所示.假设节点S1为招募节点或协作节点，节点C1竞争招募节点失败，进入等待状态，等待被招募为协作节点或满足睡眠条件进入睡眠状态，dS1，C1为节点S1与节点C1之间的距离.节点S1发送协作节点请求消息，节点C1收到此消息后，如果dS1，C1≤Dm，则节点S1进入睡眠状态.若dS1，C1>Dm，判断节点S1是否属于节点S1的招募节点的邻居节点，如果不是，丢弃该消息； 否则延时Tr后，节点C1向节点S1发送协作节点响应消息.
|
| 图 5 协作节点请求阶段示意图 Figure 5 Sketch figure of cooperating nodes request phase |
Tr用于避免在发送协作节点响应时，各节点之间的消息竞争.假设S1为招募节点，C1为S1的协作节点，C2为S1的邻居节点，节点位置示意图如图 6所示.节点C2收到节点C1的协作节点请求消息后，计算Tr如式(1)所示：
|
(1) |
|
| 图 6 节点位置示意图 Figure 6 Sketch figure of nodes position |
其中，函数D(x)定义如式(2)所示：
|
(2) |
D(x)与x成反比例关系.当x趋近于Rt时，D(x)趋近于0； 当x趋近于0时，D(x)取得最大值.当节点C2分别距离节点C1和节点S1距离最远时，Tr取得最小值，节点C2最早发出协作节点响应消息.因此，在协作节点选择过程中，优先选择距离招募节点距离更远的节点.
(2) 协作节点响应消息待发送处理.协作节点响应阶段如图 7所示.节点C2为节点S1的邻居节点，节点S2也为招募节点(不同于节点S1).节点C1进入Tr延时后，协作节点响应消息进入待发送状态；Tr延时结束后，节点C1将向节点S1发送协作节点响应消息.如果在Tr延时结束前，节点C1侦听到节点C2发送给节点S1的协作节点响应消息，则节点C1比较其与节点C2的距离信息，如果dC1，S1+dC1，C2>dC2，S1+dC2，C1，则节点C1继续执行Tr延时，延时结束后发送协作节点响应； 否则，说明节点C2比节点C1更适合作为节点S1的协作节点，因此节点C1停止Tr延时，退出协作节点响应消息待发送状态，更新其邻居节点表，将节点C2的ID号添加到其邻居节点表，重新进入等待状态.
|
| 图 7 协作节点响应阶段示意图 Figure 7 Sketch figure of collaboration nodes response phase |
节点C1在协作节点响应消息待发送状态，也有可能接收到来自其它节点的协作节点请求消息.如图 7所示，如果节点C1接收到来自节点S2的协作节点请求消息，节点C1首先停止Tr延时，退出协作节点响应消息待发送状态，避免节点C1向节点S1发送协作节点响应消息.然后节点C1重新从等待状态处理节点S2的协作节点请求消息，决定节点C1进入睡眠状态，或者更新延迟时间Tr，节点C1进入节点S2的协作节点响应待发送状态.为了避免增加冗余协作节点和算法复杂度，节点不同时响应多个节点的协作节点请求，只处理最新的协作节点请求消息.显然，节点处于协作节点响应消息待发送状态的时间更长，让节点有可能接收到更多的协作节点请求消息，使节点有更多机会进入睡眠状态.
(3) 协作节点响应消息处理.招募节点或协作节点S1接收到协作节点响应消息后，将响应消息中的距离信息与接收到的最大距离信息进行比较.如果新响应节点的距离大于之前响应节点的最大距离，则更新最大节点距离和最大距离节点ID号，否则丢弃新接收的响应消息.同时启动延时Tw，它可以保证节点接收到所有的协作节点响应消息.如果在Tw延时结束前，节点S1没有接收到新的协作节点响应消息，则节点S1确认当前最大距离节点为其招募节点的协作节点，发送协作节点确认消息.
(4) 协作节点确认消息处理.节点收到协作节点确认消息后，将消息中的节点ID号与自身节点ID比较； 如果匹配，则节点作为协作节点帮助招募节点招募下一个协作节点，发送新的协作节点请求消息.
(5) 节点招募方向问题处理.在协作节点招募过程中，节点将按照顺时针或逆时针方向进行招募.节点招募顺序如图 8所示.招募节点S1首先招募C1为协作节点，招募C2为协作节点，但是C2无法招募到新的协作节点，说明在其招募方向(逆时针方向)上已经不存在合适的协作节点，需要从协作节点起始位置(节点C1)更改招募方向，从相反方向(顺时针方向)重新招募协作节点C3，然后再由C3依次招募C4、C5为协作节点.如果更改招募方向后，再次出现无法招募到新的协作节点情况，则由招募节点发布协作节点请求消息，招募新的协作节点.如果招募节点无法招募到新的协作节点，说明该招募节点的邻居节点范围内已经不存在处于等待状态的节点，则招募节点完成协作节点招募工作，进入工作状态.
|
| 图 8 节点招募顺序图 Figure 8 Diagram of nodes recruitment sequence |
假设网络中有n个节点，1个招募节点，k个协作节点，节点发送招募信息消耗的能量为JD，接收节点响应消耗的能量为JR，JD和JR都是距离的函数，相应的招募节点消耗的能量JRe如式(3)所示：
|
(3) |
其中，Dm=Rt/2，Rt为节点通信半径.
协作节点i消耗能量JCo(i)如式(4)所示：
|
(4) |
其中，dji为节点j与协作节点i间距离.
寻找招募节点及协作节点过程的总能耗J如式(5)所示：
|
(5) |
RBSS算法将寻找招募节点及协作节点过程由某个节点完成，需消耗J能量；RBDRS算法将其分配到k+1个节点中，不至于出现RBSS算法中节点过早死亡，延迟网络生存周期.
4 仿真与分析 4.1 仿真环境网络规模分为50 m×50 m和100 m×100 m两种方形区域，节点采用随机部署方式，节点数量从100至1 000不等，节点感知半径Rs为10 m，通信半径Rt为17 m.节点感知模型为圆形，节点具备测距能力，节点初始能量为1 J，节点发送数据功耗为16 mW，接收数据功耗为4 mW，空闲状态功耗为4 mW，睡眠状态功耗为0.01 mW，所有节点起始时均为唤醒状态.为了便于计算网络覆盖率，将网络划分为1 m×1 m的方格，如果方格的中心被某个节点感知到，则认为方格区域被覆盖.覆盖率为被覆盖方格数与划分的方格总数比值.如果网络是分割的，则只计算拥有最多连通节点(最大覆盖率)的区域.
4.2 仿真结果分析(1) 工作节点数随节点总数变化情况.50 m×50 m网络规模下，工作节点数目随节点总数变化曲线如图 9(a)所示，节点数为100时，RBDRS算法比RBSS算法工作节点数减少3.98%； 节点数为200时，RBDRS算法增加1.39%； 节点数为300~900时，RBDRS算法减少0.82%~7%； 节点数为1 000时，RBDRS算法增加0.4%.RBDRS算法比RBSS算法工作节点数平均减少2.94%.100 m×100 m网络规模下，工作节点数目随节点总数变化曲线如图 9(b)所示.RBDRS算法比RBSS算法工作节点数减少1.87%~6.76%，平均减少4.11%.
|
| 图 9 工作节点数目随节点总数变化曲线 Figure 9 Curves of work nodes numbers with total number of nodes |
从图 9(b)可以看出，在部署相同节点数情况下，RBDRS算法比RBSS算法所需工作节点数少.对于网络规模为50 m×50 m，节点总数为200时，网络节点密度小且节点随机部署，在协作节点招募过程中，为实现逼近正六边形网络覆盖模型，RBDRS算法比RBSS算法工作节点数增加1.39%.
(2) 网络覆盖率随节点总数变化情况.网络规模为50 m×50 m下，网络覆盖率随节点总数变化曲线如图 10(a)所示，节点数为100时，RBDRS算法比RBSS算法网络覆盖率减少0.21%； 节点数为200~400时，RBDRS算法增加0.08%~0.2%； 节点数为500时，RBDRS算法减少0.06%； 节点数为600~1 000时，RBDRS算法增加0.04%~0.1%； RBDRS算法比RBSS算法网络覆盖率平均增加0.05%.
|
| 图 10 网络覆盖率随节点总数变化曲线 Figure 10 Curves of network coverage with the total number of nodes |
网络规模为100 m×100 m下，网络覆盖率随节点总数变化曲线如图 10(b)所示，节点数为100时，RBDRS算法比RBSS算法网络覆盖率减少0.59%； 节点数为200时，RBDRS算法增加0.65%； 节点数为300时，RBDRS算法减少0.11%； 节点数为400~1 000时，RBDRS算法增加0.06%~0.75%.RBDRS算法比RBSS算法网络覆盖率平均增加0.13%.
不同的网络规模，不同节点数目，RBDRS算法的网络覆盖率略高于RBSS算法.当节点总数为100时，两种网络规模下，网络节点密度较小，RBDRS算法在协作节点招募过程中无法招募到足够的工作节点，从而产生覆盖漏洞，所以RBDRS算法的网络覆盖率较RBSS算法有所降低，但均高于90%.
(3) 网络生命周期.工作节点数和网络覆盖率随节点总数变化主要集中在空间比较，即所有仿真数据都是基于节点被部署后第一次执行调度算法的结果.随着时间延长，网络中的部分节点将因能量的耗尽而死亡，需要进一步对网络生命周期进行分析.假定网络规模为50 m×50 m，初始部署节点总数为300，所有节点时间同步，每100 s(轮)存活节点同时唤醒，执行节点调度算法，决定节点在本轮的工作状态(睡眠或工作).
基于RBSS算法和RBDRS算法的工作节点数随着时间变化的曲线分别如图 11所示.图 11(a)中，基于RBSS算法，在6 070 s时工作节点数小于1，即所有节点死亡.图 11(b)中，基于RBDRS算法，所有节点死亡时间为16 870 s.在算法执行过程中，节点即使处于空闲状态，每100 s也会消耗0.4 J能量，导致部分工作节点死亡，使工作节点数呈现周期性波动.通过图 11分析比较发现，RBDRS算法比RBSS算法的波动性小.与RBSS算法相比，RBDRS算法的网络生命周期延长了178%.
|
| 图 11 工作节点数随时间变化曲线 Figure 11 Curves of work nodes numbers with time |
RBSS算法和RBDRS算法的网络覆盖率随时间变化曲线分别如图 12所示.当网络覆盖率小于50%时，认为网络失效.从图 12分析发现，当时间超过3 040 s时，RBSS算法的网络覆盖率小于50%，而RBDRS算法需要时间超过6 420 s.与RBSS算法相比，RBDRS算法的网络有效时间延长了111%.
|
| 图 12 网络覆盖率随时间变化曲线 Figure 12 Curves of network coverage with time |
基于测距的睡眠调度算法(RBSS)通过招募节点进行节点调度，招募节点能耗过大，造成其过早死亡，影响网络的生命周期.针对这个问题，本文基于能量均衡思想，提出基于测距的均衡式招募调度算法(RBDRS)，给出了该算法的适用的假设条件以及解决的问题.RBDRS算法基于正六边形节点覆盖模型，考虑到招募节点在算法执行过程中能量消耗过高而导致节点快速死亡的情况，将协同节点招募的任务转移到每个新招募的协作节点上，从而使网络的能量消耗更加均衡； 在协作节点选择过程中，综合考虑节点与招募节点、协作招募节点间的距离，选择最合适节点作为协作节点，使网络覆盖模型更趋近于正六边形，减少工作节点个数的同时维持了网络覆盖率.RBDRS算法受正六边形限制以及将网络生命周期划分为长度相同的若干轮，过于理想化.
从工作节点数、网络覆盖率分别随节点总数以及时间变化方面做仿真实验.仿真实验结果表明，与RBSS算法相比，在不增加额外开销的条件下，RBDRS算法能够有效减少工作节点数目，提高网络覆盖率，相应地均衡网络能耗，延长网络生命周期.在算法执行过程中，RBSS算法总是由招募节点发布协作节点招募消息，节点频繁发送和接收数据，导致能量消耗过快.RBDRS算法的协作节点招募消息由每次新招募的协作节点发布，将数据发送所消耗的能量均衡地分给每个协作节点，使整个网络的节点能量消耗更加均衡，有效地延长网络生命周期.
| [1] | Xue W L, Chi Z X. 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. DOI:10.1080/17445760.2011.574630 |
| [2] | Khosravi H. Optimal node scheduling for desired percentage of coverage in wireless sensor networks[J]. Wireless Sensor Network, 2012, 4 (5): 127–132. DOI:10.4236/wsn.2012.45018 |
| [3] | 胡湘华, 杨学军. 传感网节点调度方法综述[J]. 计算机工程与科学, 2008, 30 (3): 93–96. Hu X H, Yang X J. A survey of node scheduling schemes for sensor networks[J]. Computer Engineering & Science, 2008, 30 (3): 93–96. |
| [4] | 王力立, 黄成, 徐志良, 等. 基于闭合包围方法的传感器网络节点调度[J]. 信息与控制, 2013, 42 (1): 117–124. Wang L L, Huang C, Xu Z L, et al. Node scheduling based on closed embracing approach for sensor networks[J]. Information and Control, 2013, 42 (1): 117–124. |
| [5] | Wang L, Wei R Z, Lin Y P, et al. A clique base node scheduling method for wireless sensor networks[J]. Journal of Network and Computer Applications, 2010, 33 (4): 383–396. DOI:10.1016/j.jnca.2010.03.002 |
| [6] | 张乾, 沈顺. 基于无线传感器网络的物流自保护环型路由协议[J]. 信息与控制, 2014, 43 (2): 186–192. Zhang Q, Shen S. Ring protocol of self-protection in logistics based on wireless sensor networks[J]. Information and Control, 2014, 43 (2): 186–192. |
| [7] | Slijepcevic S, Potkonjak M. Power efficient organization of wireless sensor networks[C]//IEEE International Conference on Communication(ICC). Piscataway, NJ, USA:IEEE, 2001:472-476. |
| [8] | Zhang H H, Hou J C. Maintaining sensing coverage and connectivity in large sensor networks[J]. Ad Hoc & Sensor Wireless Networks, 2005, 1 (1): 89–124. |
| [9] | Kumar S, Lai T H, Balogh J. On k coverage in a mostly sleeping sensor network[J]. Wireless Networks, 2003, 14 (3): 277–294. |
| [10] | Wu K, Gao Y, L i, et al. Lightweight deployment-aware scheduling for wireless sensor networks[J]. Mobile Networks and Applications, 2005, 10 (6): 837–852. DOI:10.1007/s11036-005-4442-8 |
| [11] | Yen L H, Cheng Y M. Range-based sleep scheduling (RBSS) for wireless sensor networks[J]. Wireless Personal Communications, 2009, 48 (3): 411–423. DOI:10.1007/s11277-008-9530-1 |
| [12] | 赵仕俊, 张朝晖. 无线传感器网络正六边形节点覆盖模型研究[J]. 计算机工程, 2010, 36 (20): 113–115. Zhao S J, Zhang Z H. Study regular hexagonal node coverage model of wireless sensor networks[J]. Computer Engineering, 2010, 36 (20): 113–115. |