与位置无关的节点调度算法比较分析

刘立峰，周轶恒，林志贵，哈　谦，王　玺

（1.天津工业大学电子与信息工程学院，天津　300387；2.国家海洋技术中心近海海洋环境观测与监测技术研究室，天津　300112）



与位置无关的节点调度算法比较分析

刘立峰1，周轶恒1，林志贵1，哈谦2，王玺1

（1.天津工业大学电子与信息工程学院，天津300387；2.国家海洋技术中心近海海洋环境观测与监测技术研究室，天津300112）

摘要：无线传感器网络中，通过对节点的合理调度，可以实现节点能耗均衡、延长网络生命周期的目的.分析与位置无关的节点调度算法发现，随机独立休眠算法（RIS）不需要调度时间同步，未考虑节点死亡对工作概率值p的影响，适应性差；基于部署特征的轻量级节点调度算法（LDAS），考虑覆盖率的影响，但需要频繁交换邻居节点信息；基于测距的睡眠调度算法（RBSS），通过测距寻找正六边形覆盖模型，具有较高的覆盖度，需要时间同步，未考虑能量均衡.从初始节点数、工作节点数和网络覆盖率3方面仿真验证说明其性能，为选择节点调度算法以及后续改进提供指导.

关键词：节点调度；位置无关；算法；无线传感器网络

如何有效降低节点能耗是无线传感器网络设计过程中所需考虑的主要问题之一[1].一些研究者从面向处理器的动态电压调节和面向单个节点的动态功率管理方面研究降低能耗[2]，这2种策略针对单个节点的能耗进行优化，没有从整个无线传感器网络全局的层面进行优化.节点调度是通过对全局网络的节点工作/睡眠等模式合理调度，降低网络能耗.其基本原理是在不影响网络整体性能的前提下，通过一定的方式对网络中的时间或空间进行划分，调度一部分冗余传感器节点进入低功耗模式，剩余节点执行监测任务[3].无线传感器网络中，为了保障区域全覆盖以及网络的稳健性，通常采用大面积、高冗余的部署方式，带来了网络中大量冗余节点.合理调度冗余节点，可有效地降低无线通信信道冲突、网络的吞吐量及网络能耗[4-7].

节点调度算法可分为与位置相关的节点调度算法和与位置无关的节点调度算法两大类.基于地理位置的节点调度算法通过获取节点精确的地理位置信息计算节点的覆盖区域和冗余度，实现节点调度，如启发式的基于最大化互斥集合个数的算法（MCMCC）[8]、最优地理密度控制算法（OGDC）[9]等.此类算法通常采用全球定位系统GPS或其他定位机制获取节点的精确位置信息，节点成本高，定位消耗能量.与位置无关的节点调度算法中，节点的位置信息无需作为已知条件，节点通过与邻居节点交换信息，获取邻居节点个数、距离等信息判断节点是否为冗余节点，如随机独立休眠算法（RIS）[10]、基于部署特征的轻量级节点调度算法（LDAS）[11]、基于测距的睡眠调度算法（RBSS）[12]等.这类无需定位装置，降低了节点成本及能耗，越来越受到研究者的青睐.本文分析与位置无关的节点调度算法，通过Matlab仿真平台，分析其各自节点调度的特点，验证其理论的有效性以及分析其不足之处.

1　与位置无关的节点调度算法

针对k度覆盖无线传感器网络，Kumar等[10]提出一种随机独立休眠算法（RIS）. RIS算法将网络时长划分为多个时间片段，所有节点的时间片长度相等，每个节点开始调度的时间不需要同步.每个时间片段起始时执行调度算法，所有节点各自以独立的概率p进入工作状态或概率（1-p）进入休眠状态，网络生命周期与概率p成反比.因此，已知网络生命周期和每个节点的时间片长度，即可计算出概率p，该算法可以将网络的生命周期延长p倍. RIS算法需部署最少初始节点数量n计算如公式（1）所示.已知监测区域面积、节点感知半径r和网络生命周期的条件下，计算出满足渐近k度覆盖所需要部署的最少初始节点数量n和节点进入工作状态的概率值p.

式中：φ（np）函数定义如公式（2）所示.

Gui等[11]基于RIS，并采用基于预设时间表，即每个时间片分为活跃期和休眠期两部分，其随机性体现在对每个节点开始执行调度算法的时间选择上，增强了网络动态性能，降低通信开销，均衡网络节点能耗，但未考虑节点死亡对工作概率值p的影响，适应性差.

基于节点均匀随机部署假设，Wu等[12]提出一种基于部署特征的轻量级节点调度算法（LDAS）. LDAS算法在网络监测开始时，根据覆盖率P，计算节点所需的邻居节点数目r，r的计算公式如式（3）所示.

各节点交换信息，获取自身的实际邻居节点数n，如果邻居节点数n超过r，节点随机选择（n-r）个邻居节点，发送节点关闭信息.如果节点收到的关闭信息次数超过阈值b（公式（4）），则该节点在一段随机延时后进入睡眠状态.如果在随机延时过程中，节点的部分邻居节点进入睡眠状态，导致节点的邻居节点数目小于r，则该节点不进入睡眠状态. LDAS算法无需节点位置信息和时间同步机制，在一定程度上能同时保证覆盖率和连通性，但只能采取均匀部署，需要频繁交换邻居节点信息.

借鉴OGDC算法思想，Yen等[13]提出一种与地理位置无关的基于测距的睡眠调度算法（RBSS）.假设监测区域中的节点均匀随机部署，节点通信半径为感知半径的倍时，RBSS算法可以在不需要精确地理位置信息的情况下，通过测距在已部署节点中寻找和逼近正六边形覆盖模型[14-15]，保证网络的覆盖率和连通性. RBSS算法将网络生命周期划分为固定时间长度段（轮）.每轮起始时，节点随机竞争成为招募节点.招募节点发布招募消息，其邻居节点接收到招募消息后，首先判断2个节点间的距离，如果节点距离小于传输半径的1/2，则节点进入睡眠状态，否则节点发送响应消息.招募节点接收到响应消息后，选择距其最远的邻居节点作为协作节点，循环招募新的协作节点，直至协作节点数等于6或无法招募到协作节点.招募完成后，招募节点和协作节点执行监测任务，其余节点进入睡眠状态，直至本轮结束. RBSS具有较高的覆盖度，保证网络节点的通信连接，但需要时间同步，未考虑能量均衡.

2　算法仿真分析

2.1仿真环境

采用Matlab仿真平台分别对上述节点调度算法进行仿真.仿真环境设定为网络区域规模为100m×100 m，节点感知半径为10 m，节点通信半径为10～17 m.

2.2仿真结果与分析

2.2.1 RIS算法仿真分析

RIS算法根据网络生命周期、节点感知半径、网络区域面积预测节点睡眠概率p和网络达到k度覆盖所需初始节点数量n.假定每个节点在其生命周期中可执行5次调度，即睡眠概率（1-p）等于0.8.满足k度覆盖的初始节点数量n变化如图1所示；k度覆盖的工作节点数量如图2所示.

从图1和图2看出，RIS算法所需初始节点数量较大，即使当k=1时，也需要部署1 805个节点，每轮工作节点数为368个.

图1　k度覆盖初始节点数量曲线Fig.1 Number curve of nodes on k-coverage

图2　k度覆盖工作节点数量曲线Fig.2 Number curve of working nodes on k-coverage

2.2.2 LDAS算法仿真分析

LDAS算法根据覆盖率P计算出每个节点所需最少邻居节点数r，据此执行节点调度算法.假设初始节点数分别为1 000、1 500、2 000时，需求覆盖率与实际覆盖率的关系如图3所示.需求覆盖率与工作节点数量的关系如图4所示.由图3看出，LDAS算法的实际覆盖率与需求覆盖率的误差在-2%至3%之间，LDAS算法是有效的.由图4看出，不同需求覆盖率下，初始部署节点数量不同，执行LDAS调度算法后，工作节点数不随初始节点数量的增加而增加.需求覆盖率为85%时，工作节点数保持在125至135之间，平均为130个工作节点.需求覆盖率为90%时，工作节点数保持在165～ 168，平均为167个工作节点.需求覆盖率为95%时，工作节点数保持在230～233，平均为232个工作节点. 2.2.3 RBSS算法仿真分析

RBSS算法基于正六边形覆盖模型，节点通过测距获知邻居节点的距离选取最优工作节点，其工作节点数目随节点总数变化曲线如图5所示，网络覆盖率随节点总数变化曲线如图6所示.

从图5和图6看出，RBSS调度算法中，当网络节点数大于200时，网络覆盖率即超过96%，仅需62个工作节点.网络部署节点数达到1 000时，网络覆盖率为99.88%，工作节点数为79个.

图3　需求覆盖率与实际覆盖率关系曲线Fig.3 Curves of actual coverage with requirements coverage

图4　需求覆盖率与工作节点数量关系曲线Fig.4 Curves of working nodes number with different requirements coverage

图5　工作节点数目随节点总数变化曲线Fig.5 Curve of number of working nodes with total number of nodes

图6　网络覆盖率随节点总数变化曲线Fig.6 Curve of Network coverage with total number of nodes

2.2.4 3种算法仿真比较

选取在网络覆盖率接近100%时的初始节点数目和工作节点数目，比较RIS、LDAS、RBSS 3种算法的性能，其结果如表1所示.

表1　3种算法仿真结果比较Tab.1 Comparison of simulation results of three algorithms

由表1可知，RBSS算法与RIS算法网络覆盖率相差仅0.02%时，RBSS算法比RIS算法初始节点数目减少805个（44.6%）、工作节点数目减少289个（78.5%），RBSS算法优于RIS算法.由表1还可得知，RBSS算法与LDAS算法初始节点数目均为1 000时，RBSS算法比LDAS算法工作节点数目减少151个（65.7%）、网络覆盖率增加4.88%，RBSS算法优于LDAS算法.

3　结语

RIS算法只需设定监测区域面积、节点感知半径和网络生命周期即可计算节点休眠概率p和网络初始节点数量n，算法实现简单，各节点只需以概率p进入工作状态，无需与邻居节点交换信息，但是网络满足k度覆盖所需的初始节点数量较大. LDAS算法根据需求覆盖率计算所需邻居节点数目，通过去除多余邻居节点减少冗余工作节点，但是在执行调度过程中，节点间需要频繁交换邻居节点信息，容易造成能量消耗和网络拥堵，且需要工作节点数目较多.与RIS 和LDAS算法相比，RBSS算法具有良好的调度效果，在相同条件下，仅需较少的工作节点即可达到较高的网络覆盖率，但需要测量节点间距离，增加网络成本. RBSS算法在实现过程中，始终由招募节点执行协作节点招募，因此相对其他节点会消耗较多的能量；当网络部署节点密度变大时，6个协作节点可能无法与招募节点形成无漏洞覆盖，形成覆盖漏洞.

参考文献：

[1]陆游，禹素萍.一种能量可计算的星型无线传感器网络协议[J].天津工业大学学报，2013，32（4）：60-65. LU Y，YU S P. An energy star computable wireless sensor network protocol[J]. Journal of Tianjin Polytechnic University，2013，32（4）：60-65（in Chinese）.

[2] WANG Lei，WEI Ruizhong，TIAN Zihong. Cluster based node scheduling method for wireless sensor networks [J]. Science China Information Sciences，2012，55（4）：755-764.

[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. HU X H，YANG X J. Review of sensor network node scheduling methods[J]. Journal of Computer Engineering and Science，2008，30（3）：93-96，129（in Chinese）.

[6]洪锋，褚红伟，金宗科，等.无线传感器网络应用系统最新进展综述[J].计算机研究与发展，2010，47（S2）：81-87. HONG F，ZHU H W，JIN Z K，et al. Review of latest development in wireless sensor network applications [J]. Journal of Computer Research and Development，2010，47（S2）：81-87 （in Chinese）.

[7] WANG Lei，WEI Ruizhong，LIN Yaping，et al. A clique base node scheduling method for wireless sensor networks [J]. Journal of Network and Computer Applications，2010，33（4）：383-396.

[8] SLIJEPCEVIC Sasa，POTKONJAK Miodrag. Power efficient organization of wireless sensor networks[C]//IEEE International Conference on Communication（ICC）. Helsinki：Finland，IEEE，2001：472-476.

[9] ZHANG Honghai，HOU Jennifer C. Maintaining sensing coverage and connectivity in large sensor networks [J]. Ad Hoc & Sensor Wireless Networks，2004，1（2）：89-124.

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

[11] GUI Chao，MOHAPATRA Prasant. Power conservation and quality of surveillancein target tracking sensor networks [C]// Proceedings of the 10th Annual International Conference on Mobile Computing and Networking. Philadelphia：ACM，2004：129-143.

[12] 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.

[13] YENLihsing，CHENGYangmin.Range-basedsleep scheduling （RBSS）for wireless sensor networks [J]. Wireless Personal Communications，2009，48（3）：411-423.

[14]赵仕俊，张朝晖.无线传感器网络正六边形节点覆盖模型研究[J].计算机工程，2010，36（20）：113-115，118. ZHAO S J，ZHANG Z H. Research on wireless sensor networks' hexagonal node coverage model[J]. Journal of Computer Engineering，2010，36（20）：113-115，118（in Chinese）.

[15]赵仕俊，路嘉鑫，张朝晖.无线传感器网络一维区域随机覆盖研究[J].昆明理工大学学报：理工版，2010，35（4）：71-75. ZHAO S J，LU J X，ZHANG Z H. Research on a one-dimensional area randomized covering in wireless sensor networks[J]. Journal of Kunming University of Science And Technology：Natural Science Edition，2010，35（4）：71-75（in Chinese）.

Comparison and analysis of node scheduling algorithms on position-independent in WSNs

LIU Li-feng1，ZHOU Yi-heng1，LIN Zhi-gui1，HA Qian2，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）

Abstract：In wireless sensor networks，by reasonable scheduling of nodes，energy consumption balance and prolonging the

network life cycle are achieved. The position-independent node scheduling algorithms is analyzed，and it is found that a random independent sleep algorithm（RIS）does not require scheduled time synchronization，and does not consider the influences of a node death on its running probability p and has poor adaptability. A lightweight node scheduling algorithm（LDAS）based on the deployment features considers the impact of coverage，and then it needs to exchange the information of neighbor nodes frequently. A range based sleep scheduling algorithm （RBSS）looks for regular hexagon coverage model by measuring distance with high coverage. The RBSS needs time synchronization and does not consider nodes energy balance. By simulation，the performance of the algorithms is compared from the number of the initial nodes and working nodes, and network coverage，which provides guidance for selection of valid node scheduling algorithms and subsequent improvement.

Key words：node scheduling；position-independent；algorithms；wireless sensor network

通信作者：刘立峰（1975—），男，博士，讲师，主要研究方向为智能信息处理. E-mail：liulifeng@tjpu.edu.cn

收稿日期：2015-10-19基金项目：国家自然科学基金资助项目（61372011）

DOI：10.3969/j.issn.1671-024x.2016.01.010

中图分类号：TN921

文献标志码：A

文章编号：1671－024X（2016）01－0050－04