好文档就是一把金锄头!
欢迎来到金锄头文库![会员中心]
电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

传感器网络邻居发现协议综述.pdf

20页
  • 卖家[上传人]:ldj****22
  • 文档编号:44666655
  • 上传时间:2018-06-14
  • 文档格式:PDF
  • 文档大小:1.16MB
  • / 20 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 书书书第3 9卷 第5期2 0 1 6年5月计  算  机  学  报CH I N E S EJ OUR NA LO FC OMP UT E R SV o l . 3 9 N o . 5M a y2 0 1 6 收稿日期:2 0 1 5  0 5  3 0; 出版日期:2 0 1 5  1 0  2 6 .本课题得到国家科技重大专项(2 0 1 2 Z X 0 3 0 0 5 0 0 7) 、 国家科技支撑计划(2 0 1 4 B AH 1 4 F 0 1)资助.裘 莹, 男,1 9 8 7年生, 博士研究生, 主要研究方向为传感器网络协议设计. E  m a i l:q i u y i n g@m a i l . n w p u. e d u. c n .李士宁, 男,1 9 6 7年生, 教授, 博士生导师, 主要研究领域为传感器网络与移动计算.徐相森, 男,1 9 9 1年生, 硕士研究生, 主要研究方向为传感器网络.李志刚, 男,1 9 7 5年生, 博士, 副教授, 主要研究方向为网络化嵌入式技术、 传感器网络与移动计算.传感器网络邻居发现协议综述裘莹 李士宁 徐相森 李志刚( 西北工业大学计算机学院 西安 7 1 0 0 7 2)摘 要 邻居发现协议是传感器网络协议族的重要组成部分, 用于快速高效地发现通信范围内的邻居节点, 为其他协议和应用提供邻居信息.文中根据近年来的相关研究成果, 介绍传感器网络邻居发现的问题定义, 提出了形式化的问题模型以及简化的时隙模型, 并指出了协议设计面临的挑战: (1) 在电池供电的前提下保证能量有效性;(2) 保证实时性以满足应用的延迟约束; (3) 适应网络拓扑的动态性, 尤其是近年来基于位置移动应用的出现对邻居发现协议的性能提出了更高的要求.文中根据各类邻居发现协议的对称性、 确定性、 协作性、 是否使用多信道和按需发现等特点分类, 选定了发现延迟、 能耗和最优近似比作为协议的性能评价标准, 并针对各类具有代表性邻居发现协议分析研究其主要设计思想, 剖析了相似协议间存在的关联性和演进过程, 论述各自的优缺点及适用范围,归纳协议设计方法并通过理论分析比较协议性能.最后, 通过真实环境中的实验比较了各类协议的实际性能, 并总结和展望了邻居发现技术的未来发展趋势.关键词 无线传感器网络; 物联网; 邻居发现; 能量有效; 移动感知中图法分类号T P 3 1 1   犇 犗 犐号1 0. 1 1 8 9 7/S P. J . 1 0 1 6. 2 0 1 6. 0 0 9 7 3犛 狌 狉 狏 犲 狔狅 狀犖 犲 犻 犵 犺 犫 狅 狉犇 犻 狊 犮 狅 狏 犲 狉 狔犘 狉 狅 狋 狅 犮 狅 犾 犳 狅 狉犛 犲 狀 狊 狅 狉犖 犲 狋 狑 狅 狉 犽 狊Q I U Y i n g  L IS h i  N i n g  XUX i a n g  S e n L IZ h i  G a n g(犛 犮 犺 狅 狅 犾 狅 犳犆 狅 犿 狆 狌 狋 犲 狉犛 犮 犻 犲 狀 犮 犲,犖 狅 狉 狋 犺 狑 犲 狊 狋 犲 狉 狀犘 狅 犾 狔 狋 犲 犮 犺 狀 犻 犮 犪 犾犝 狀 犻 狏 犲 狉 狊 犻 狋 狔,犡 犻’犪 狀 7 1 0 0 7 2)犃 犫 狊 狋 狉 犪 犮 狋   N e i g h b o rd i s c o v e r yp r o t o c o l i sa ni m p o r t a n tc o m p o n e n ti nw i r e l e s ss e n s o rn e t w o r kp r o t o c o l s,w h i c hf o c u s e so nf i n d i n go u tn e i g h b o r sw i t h i nn o d e’sc o mm u n i c a t i o nr a n g ef a s ta n de f f i c i e n t l y,a n dp r o v i d e sn e i g h b o r i n f o r m a t i o nf o ro t h e rp r o t o c o l sa n da p p l i c a t i o n s .W i t hs u r v e y i n gn e i g h b o rd i s c o v e r yp r o t o c o l sd e v e l o p e di nr e c e n ty e a r s,w ei n t r o d u c et h ed e f i n i t i o no fn e i g h b o rd i s c o v e r y i ns e n s o rn e t w o r k sa n dp r e s e n t t h e f o r m a lm o d e l o f t h ep r o b l e ma sw e l l a sas i m p l i f i e ds l o tm o d e l . T h ed e s i g no fn e i g h b o rd i s c o v e r yp r o t o c o l i sf a c i n gt h r e ec h a l l e n g e s:(1)e n s u r i n ge n e r g y  e f f i c i e n c y i nb a t t e r y  p o w e r e dn o d e s;(2)s a t i s f y i n gt h e l o w  l a t e n c yr e q u i r e m e n t i nd i v e r s ea p p l i c a t i o n s;(3)a d a p t i n gn e t w o r kt o p o l o g yd y n a m i c s,e s p e c i a l l yi ne m e r g i n gl o c a t i o n  b a s e dm o b i l ea p p l i c a t i o n sw h i c h m a k eh i g h e rd e m a n do nt h en e i g h b o rd i s c o v e r yp r o t o c o lp e r f o r m a n c e .N e i g h b o rd i s c o v e r yp r o t o c o l sa r ed i v i d e di n t os e v e r a lc a t e g o r i e sb ys y mm e t r y,d e t e r m i n a c y,c o l l a b o r a t i o n,w h e t h e rm u l t i  c h a n n e l i s i n v o l v e da n dw h e t h e r t h ed i s c o v e r y r e q u e s t i so n  d e m a n d .M o r e o v e r,w ep r o p o s ed i s c o v e r yl a t e n c y,e n e r g yc o n s u m p t i o na n da p p r o x i m a t i o nt oo p t i m a la st h em e t r i c so f p r o t o c o l p e r f o r m a n c e .W e r e s e a r c ht h ep r i m a r yd e s i g np r i n c i p a l o f r e p r e s e n t a t i o n a ld i s c o v e r yp r o t o c o l sa n da n a l y z et h e i rr e l a t i o n s h i pw i t ht h o s ei nt h es a m ep r o t o c o l f a m i l y .W i t hd i s c u s s i n gt h e i ra d v a n t a g e sa n dd r a w b a c k s,w el i s tt h ea p p l i c a t i o ns c e n a r i o so fd i f f e r e n tp r o t o c o l s .M e a n w h i l e,w e s u mm a r i z e t h ev a r i o u sd e s i g np r i n c i p a l s a n dc o m p a r e t h ep r o t o c o l p e r f o r m a n c eb y t h e o r e t i c a l a n a l y s i s . F i n a l l y,w ec o m p a r e t h e i rp e r f o r m a n c e sw i t hr e a l  w o r l de x p e r i m e n t s a n d t r yt op r e d i c t t h e f u t u r er e s e a r c ht r e n d so f t h en e i g h b o rd i s c o v e r yt e c h n o l o g y .犓 犲 狔 狑 狅 狉 犱 狊   w i r e l e s ss e n s o rn e t w o r k s;I n t e r n e to fT h i n g s;n e i g h b o rd i s c o v e r y;e n e r g y  e f f i c i e n t;m o b i l es e n s i n g1 引 言传感器网络使用大量低成本、 小体积、 低能耗的传感器节点通过无线通信自组织形成网络, 用于感知和传输各类感兴趣的信息.传感器网络已在环境监测[1]、 数据采集[2]、 结构健康检测[3]、 目标追踪[4]、应急救援[5]、 动物习性监测[6  9]等领域得到了广泛的应用.在传感器网络应用部署中, 传感器节点的地理位置分布往往不确定, 并且没有基础通信设备的支持, 节点间需要通过互相发现才能自组织形成网络.因此, 邻居发现协议是传感网网络协议族中不可或缺的一个重要组成部分, 合理地利用邻居信息可以有效地提高MA C协议、 路由协议、 拓扑控制协议等网络协议的性能.例如,MA C协议中通常会利用邻居的唤醒调度信息优化睡眠等待时间以节省能耗[1 0  1 1].路由协议使用邻居信息( 如邻居节点的接收信号强度) 作为选择下一跳路由的参考因素[1 2], 以提高路由选择的准确性.拓扑控制协议[1 3]更需要准确的邻居信息以筛选部分链路作为可用的通信链路.这些协议的性能往往都与邻居信息的实时性和准确性有密切的关联[1 4].由于各类网络协议和具体应用中都需要使用邻居信息, 因此传感器网络操作系统通常将它作为一个独立公用的基础服务[1 5  1 6].近年来, 随着智能终端的普及, 移动传感器网络已成为学术界研究的热点[1 7].这类网络在居民生活环境监测[1 8  1 9]、 用户行为记录与分析[2 0  2 2]、 交通运输[2 3  2 4]、 社交网络[2 5  2 9]等方面得到了初步应用.许多移动应用通常都需要快速地收集邻近设备的信息以便高效地与它们合作来完成既定的任务[3 0  3 1].相比传统的传感器网络应用, 此类应用中的节点移动性更大, 对实时性的要求也更高, 从而对邻居发现协议的设计提出了更高的要求.本文只考虑在不借助额外辅助设备( 如定位设备[6,3 2]、 定向天线[3 3  3 5]、 天线阵列[3 6]等) 的前提下进行邻居发现, 即邻居发现的过程中仅使用无线数据包通信作为互相发现的基础.通过这方面的研究主要来解决以下问题:(1) 如何能量有效地快速发现邻居?邻居发现协议期望能在最短的时间内发现所有通信范围内的邻居.然而, 传感器网络中的节点通常受能量的制约, 发送或监听邻居发现消息的频率过高会减少节点的生存时间.如何权衡能耗和邻居发现延迟是绝大多数邻居发现协议研究的关键点.(2) 是否可以在有限的时间内发现所有邻居?传感器网络中的节点通常采用睡眠唤醒调度周期地打开和关闭无线收发机以减少能耗, 无线收发机大多数时间处于关闭状态, 此时节点并不能接收和发送消息.那么邻居发现协议应当以何种形式的睡眠唤醒调度控制无线收发机的状态, 以保证它能在有限的时间内发现所有邻居?这需要对邻居发现过程建立模型, 并构造合适的发现模式确保在理论上节点可以互相发现.(3) 如何度量邻居发现协议的性能?目前学术界已提出了多种邻居发现协议, 其发现模式存在差异, 如何以统一的标准对它们进行系统地评价以客观地反映协议设计的优劣, 这也是邻居发现协议研究必须解决的问题.本文综述传感器网络邻居发现技术的研究进展, 第2节概述传感器网络邻居发现协议设计面临的挑战, 并提出邻居发现问题的定义、 模型以及协议的分类; 第3、4、5、6、7节分别介绍确定性邻居发现、随机邻居发现、 协作式邻居发现、 按需邻居发现和多信道邻居发现; 第8节综合比较各类协议的特点和适用场景; 第9节展望未来的研究方向; 第1 0节总结全文.2 问题与挑战在无线网络中, 单跳通信范围内无线信号可达的节点称为邻居.然而, 在物理上互为邻居的两个节点并不能立即知道对方在通信范围内, 必须通过信息交换才可以了解彼此的存在, 该过程就称为邻居发现.发送邻居通告消息( 也称为H e l l o消息、 信标消息) 是节点间互相发现的必要手段, 旨在向邻居通479计  算  机  学  报2 0 1 6年 告自身的存在.邻居通告消息通常包含自身的链路地址、 唤醒调度模式等信息, 以便接收方根据这些信息构建邻居表, 从而为本地的上层协议或应用提供邻居信息.2  1 面临的挑战在传统的无线网络( 如WL AN、 蜂窝网络等)中, 每个节点都具有充足的电源供给, 无线收发机可以时刻保持监听状态, 待发现节点只需要周期性地广播邻居通告消息就可以保证周围的邻居节点可以发现它.与传统无线网络相比, 传感器网络的以下特点使邻居发现协议的设计更具有挑战性:(1) 能量有效性传感器网络本身固有的特性决定了传感器节点只能使用电池供电.电池容量往往受到传感器节点体积的限制, 所以节点应尽可能减少电量的使用以延长生存时间.已有研究[1 9]表明, 开启节点的无线收发机处于发送或空闲监听状态的时间主导了节点的能量消耗.因此, 传感器网络邻居发现协议应尽量减少无线收发机处于开启状态的时间.(2) 实时性传感器网络应用通常对邻居发现的延迟有一定的要求[3 0], 确保在给定的时间内发现所有的邻居节点.尤其是在移动传感器网络应用中, 过长的发现延迟会大大降低用户体验.(3) 网络动态性网络动态性包括节点的加入、 退出和位置移动等动态事件.由于网络动态性, 已发现的邻居随时可能会失效, 因此传感器网络邻居发现必须是一个持续的过程.目前大多数应用中只是简单地使用现有的MA C协议( 如BMA C[3 7]、X  MA C[3 8]、A  MA C[3 9  4 0])广播邻居通告消息以互相发现, 这类基于信道采样的协议都需要采用发送长度为一个周期的前导码( 或监听一个周期的探测包) 的方式进行广播, 能量开销较大, 并不适合持续更新邻居信息.2  2 问题定义第2 . 1节中所描述的特性使得传感器网络的邻居发现问题显著区别于传统无线网络, 因此传统无线网络的邻居发现协议并不能直接应用于传感器网络中.这就需要根据传感器网络的特性重新定义邻居发现问题, 并根据新的问题模型提出合适的解决方案.2 . 2 . 1 问题模型为了减少能耗, 传感器网络中的节点一般都采用睡眠唤醒调度的模式周期性地打开和关闭无线收发机.一个周期内唤醒调度模式是随时间变化对应的无线收发机状态序列.由于只有睡眠和唤醒两个状态, 因此唤醒调度模式可以形式化表述为如下的二值函数:Ψ(犿,狋)=0, 节点处于睡眠状态1,{节点处于唤醒状态(1)其中,Ψ(犿,狋) 为0表示节点犿在狋时刻处于睡眠状态, 此时无法发现邻居节点, 也无法被邻居节点发现.Ψ(犿,狋) 为1表示节点犿在狋时刻处于唤醒状态,可以发现邻居节点, 同时也可以被邻居节点发现.在确定了唤醒调度模式的基础上, 如果一对邻居节点犿1,犿2在某个时刻狋同时处于唤醒状态, 则认为两者互相发现, 即狋→Ψ(犿1,狋)=Ψ(犿2,狋)=1(2)邻居发现协议的目的就是寻找满足该定义的唤醒调度模式Ψ(犿,狋) , 使邻居发现延迟和能耗综合最优化.2 . 2 . 2 时隙模型时隙模型将连续的时间轴分为等长的间隔称为时隙, 并且所有节点的时隙互相对齐.每个时隙中节点处于睡眠或唤醒两个状态之一, 唤醒时隙用于发送和接收邻居通告消息, 时隙的长度应当大于发送或接收邻居通告消息的时间以确保邻居发现.分时隙唤醒调度模式本质上是将调度模式Ψ(犿,狋) 离散化, 下文中用记号ψ(犿,狋) 表示.时隙对齐的时隙模型具有便于理论分析的优点, 因而为绝大多数邻居发现协议所采用.然而, 在实践中实现时隙对齐的难度较大, 不仅需要对全网作时钟同步, 并且需要充分考虑时钟漂移和软件处理延迟的不确定性所带来的影响.幸运的是时隙并不需要严格对齐, 只要相邻节点时隙的偏差不超过一个时隙, 那么在这一时隙内仍会有重叠的唤醒时间, 足以保证发现邻居.因此根据时隙对齐原则设计的邻居发现协议仍然适用于时隙未对齐的情况, 从而显著降低了实现的难度.在唤醒时隙中, 节点首先发送邻居通告消息, 随后切换到监听模式以接收邻近节点的邻居通告消息.当时隙未对齐时, 这种模式只能单向发现邻居,如图1中左半部分所示,犅节点无法接收到犃的邻居通告消息, 从而无法知道犃节点的存在.文献[4 1]中提出在时隙的结尾再发一次邻居通告消息, 就可以让一对邻居节点双向发现.如图1中右半部分所示, 即使时隙未对齐, 无论犃和犅之间的时间差是多少, 仍然可以保证双向发现.5795期裘莹等:传感器网络邻居发现协议综述 图1 时隙未对齐时需发送两次邻居通告消息当时隙严格对齐时, 实践中存在着恰好错过邻居通知消息的问题, 文献[4 2] 中提出的将唤醒时隙适当延长, 同时将相邻的睡眠时隙缩短以保证总周期长度不变的方法, 可以妥善地解决该问题.此外,文献[4 24 3] 都利用了该方法将唤醒时隙数量减半,从而缩短了邻居发现延迟, 极大地提高了协议的能量有效性.2  3 评价标准为了比较不同传感网邻居发现协议的性能, 学术界提出了多种评价标准以便对不同的协议进行统一比较.常用的评价标准为发现延迟、 能耗和最优近似比.2 . 3 . 1 发现延迟邻居发现延迟是指从两个节点进入彼此通信范围内的时刻起, 到彼此接收到对方的邻居通告消息的时刻为止的时间间隔长度.发现延迟通常由应用指定, 实时性要求较高的应用倾向于指定较小的发现延迟, 以保证在指定时间内发现所有邻居.大部分研究将发现延迟进一步细分为最坏发现延迟和平均发现延迟.最坏发现延迟是指发现最后一个邻居所需的时间, 用于评价算法的理论边界.平均发现延迟是所有邻居发现时间的期望, 用于评价算法的实际性能.图2 发现延迟累积分布图在最坏发现延迟相同的情况下, 两种不同的邻居发现协议在不同的时间段发现的邻居数量也存在着差异.一般认为在初始阶段能更快地发现邻居的协议较优, 这在发现延迟累积分布图中得以体现.如图2所示, 横坐标为时间轴, 纵坐标为已发现邻居数占总邻居数的比率, 可以看到虽然犃、犅两种协议发现所有邻居所需要的时间相同, 但是协议犃的发现速度明显快于协议犅, 因此协议犃的平均发现延迟小于协议犅.2 . 3 . 2 能 耗传感器网络中能耗决定了节点的生存时间[4 4],邻居发现协议应尽可能减少能耗以延长节点的寿命.节点的实际能耗往往难以直接计算, 由于无线收发机唤醒时的能耗远高于节点的其他能耗[4 5], 因此一般使用无线收发机的唤醒时间与总时间的比值( 即D u t y  C y c l e, 占空比) 作为评价节点能耗的标准,占空比越小, 说明节点处于唤醒状态的时间越短, 能耗越低.2 . 3 . 3 最优近似比能耗和发现延迟是邻居发现协议设计中一对互相制约的因素.一般而言, 发现延迟越短则这种邻居发现协议的效率越高, 但往往它的能耗也越大, 反之亦然.邻居发现协议设计的难点在于权衡这两个因素, 在发现延迟能满足应用需求的前提下保证能耗尽可能低.为了综合分析发现延迟和能耗这两方面因素以比较不同邻居发现协议的优劣, 文献[4 6] 提出了将两者的乘积作为综合衡量邻居发现协议性能的评价标准.设邻居发现调度模式的周期为犜, 最坏发现延迟为犔, 一个周期内的平均能耗为犘, 即犘=1犜∫犜0Ψ(犿,狋)d狋(3)从而能耗与发现延迟的犘 犔乘积Λ为Λ=犘 犔=犔犜∫犜0Ψ(犿,狋)d狋(4)若协议使用时隙模型, 那么该乘积可以使用离散化的ψ(犿,狋) 表示为Λ=犔犜∑犜- 1狋=0ψ(犿,狋)(5)文献[4 6] 进一步使用最优近似比作为对称邻居发现评价的标准.若存在最优邻居发现协议的犘 犔乘积为Λ狅 狆(犔) , 则最优近似比为l i m犔→ +∞Λ(犔)Λ狅 狆(犔)(6)根据该评价标准可以量化地比较不同邻居发现协议的优劣.2  4 邻居发现协议分类现存的邻居发现协议可以根据不同的正交特性分类, 每种协议可以分别属于不同的多个分类.根据唤醒调度模式的确定性, 邻居发现协议可以分为确定性邻居发现和随机邻居发现.在确定性679计  算  机  学  报2 0 1 6年 邻居发现中, 节点采用固定的唤醒调度模式, 保证在指定的发现延迟内发现所有的邻居; 而随机邻居发现协议采用了随机唤醒的调度模式, 能在给定的发现延迟内以一定的概率发现邻居.根据节点唤醒调度模式是否相同, 邻居发现协议可以分为对称邻居发现协议和非对称邻居发现协议.对称邻居发现协议中每个节点的唤醒调度模式相同, 仅因为节点的启动时间不同或时钟漂移而使各个节点的调度模式间存在一定的时间相位差.而非对称协议中每个节点采用不同的唤醒调度模式,以满足不同类型节点占空比不同的需求.根据协议是否与相邻节点协作以完成发现过程, 可以分为非协作式邻居发现和协作式邻居发现.非协作式邻居发现仅使用本地信息独立发现邻居节点, 而协作式邻居发现利用已发现邻居提供的信息,共同发现附近未发现的邻居.根据邻居发现过程的持续时间, 可以分为按需邻居发现和长期邻居发现.按需邻居发现只在上层协议或应用提出邻居发现请求时才启动邻居发现过程, 而长期邻居发现将邻居发现过程作为一项持续运行的服务, 连续不断地发现潜在的邻居.根据邻居发现过程是否使用多个信道, 可以分为单信道邻居发现和多信道邻居发现.单信道邻居发现始终仅使用一个固定的信道发现邻居, 而多信道邻居发现可以在邻居发现过程中切换到不同信道以发现邻居.此外, 根据全局时钟是否同步, 可以分为同步邻居发现和异步邻居发现.同步邻居发现要求网络中的每个节点具有完全相同的唤醒调度模式, 这样就保证了节点在唤醒状态发送邻居发现消息时, 所有邻居节点都可以收到该消息; 异步邻居发现不需要网络中所有节点时间同步就可以发现邻居.然而, 实现全网准确时钟同步在实际中难度较大, 各个节点的启动时间不同且硬件时钟往往存在一定程度的漂移, 因此在多跳网络环境中要求所有节点时间同步的条件并不容易满足.同步邻居发现协议的有效性取决于时间同步的准确性, 这并不是邻居发现协议重点关注的内容, 而是同步MA C协议( 如SMA C[4 7]、R T  L i n k[4 8]) 或时间同步协议[4 95 0]所需要解决的问题, 因此本文仅综述不需要时钟同步的异步邻居发现协议, 对同步邻居发现协议不作详细讨论.现有的邻居发现协议可按表1所示分类, 每个协议可以分别属于多个不同的类别.表1 传感器网络邻居发现协议分类确定随机对称非对称多信道协作按需5 1%[1 4]Q u o r u m[5 1]U  C o n n e c t[4 6]S e a r c h L i g h t[5 2]C  T o r u s[5 3]H e l l o[5 4]B l i n d D a t e[4 3]T o d i s[5 5]H e d i s[5 5]组合设计[5 6]D i s c o[4 1]B i r t h d a y[5 7]P S B A[5 8]W i F l o c k[5 9]C o h e n[6 0]A c c[6 1]E a s i N D[6 2]B L E[6 3]3 确定性邻居发现确定性邻居发现采用特定的唤醒调度模式, 从理论上保证在指定的时间内可以发现所有邻居.3  1 对称邻居发现在对称邻居发现中, 每个节点采用的唤醒调度模式相同, 但由于各个节点的启动时间不同或受时钟漂移的影响, 节点间存在时间相位差.在实际应用中, 使用对称邻居发现的前提是网络中所有节点的能耗需求比较类似, 因此可以采用相同的唤醒调度模式.对称邻居发现的调度模式可以表述为: 对于任意邻居节点对(犿犻,犿犼) , 存在时刻狋使得Ψ(犿犻,狋)=Ψ(犿犼,狋)+Φ犻,犼成立, 其中1犻,犼狀,Φ犻,犼为节点对(犿犻,犿犼) 的时间相位差.本节中介绍的邻居发现协议都满足该条件.3 . 1 . 1 基于鸽巢原理的对称邻居发现保证邻居可以互相发现最简单的方法是让节点在一个周期内唤醒的时间稍长于半个周期, 即在狀个时隙中, 让 (狀+1) /2个连续时隙处于唤醒状态, 并在每个时隙中作邻居发现, 其余时间睡眠.根据鸽巢原理[6 5], 这种情况下任意两个节点间至少有一个唤醒时隙重叠.文献[1 4,6 5] 将该方法称为5 1 %协议.如图3所示,犃、犅节点的调度周期为1 2个时隙, 每个周期中连续唤醒7个周期作邻居发现, 至少有一个时隙犃、犅同时处于唤醒状态( 图中的第5、6个时隙) , 从而保证了犃、犅必定能互相发现.7795期裘莹等:传感器网络邻居发现协议综述 图3 5 1%协议然而这种方法存在显著的缺陷, 空闲监听时间至少为5 0%的周期长度, 能量消耗过高, 在实际应用中一般难以接受.3 . 1 . 2 基于Q u o r u m的邻居发现协议为了克服5 1%协议能量过高且占空比不可调的缺点,T s e n g等人[5 1]提出了Q u o r u m协议, 使占空比可根据需求调整, 同时保证邻居发现的确定性.Q u o r u m机制是分布式系统中常用于保证冗余数据一致性 的 算 法[6 66 8], 为 读 写 操 作 分 配 权 限.两 个Q u o r u m集合总是存在非空交集以保证事务的原子性. Q u o r u m协议利用了Q u o r u m机制的特点, 将狀2个时隙以二维方阵形式排列.如图4所示( 此处狀=5) ,犃、犅节点都分别在方阵中任选一行一列作为唤醒时隙, 无论相对时隙偏移是多少, 行列之间至少存在两个重叠的唤醒时隙,从而保证了邻居发现的确定性.图4 Q u o r u m协议Q u o r u m协议的唤醒调度周期为狀2, 需要处于唤醒状态的时间为2狀-1个时隙, 相应的占空比为(2狀-1) /狀2.当占空比的需求为1 %时, 发现延迟的最坏情况约为狀2=4 0 0 0 0个时隙.若每个时隙为1 0m s, 则节点发现所有邻居的时间至多需要4 0 0 s .Q u o r u m协议虽然在保证邻居发现确定性的同时达到了降低占空比的目的, 但是它的第2次唤醒时隙重叠是多余的( 图4中的第1 8个时隙) , 这意味着Q u o r u m协议并不是最优的对称邻居发现协议,理论分析证明其最优近似比为2, 它仍存在可以进一步优化的可能.为了得到相同发现延迟要求下比Q u o r u m协议更低的占空比,K a n d h a l u等人[4 6]提出了U  C o n n e c t协议.每个节点根据占空比的要求选取一个正整数狆( 一般为质数, 在3 . 2 . 1节中进一步讨论) , 以狆为周期进行唤醒调度. U  C o n n e c t选取狆2个时隙中第1个周期的前狆/2个时隙作为唤醒时隙, 并且在每个周期的第1个时隙唤醒.如图5所示, 当狆取值为5时, 第1个周期的第0,1,2个时隙都处于唤醒状态, 而后续4个周期中节点只需在每个周期的第1个时隙唤醒.由于每个周期第1个时隙唤醒相当于节点以狆为周期对信道进行扫描, 且第1个周期中狆/2个唤醒时隙覆盖了至少半个周期, 从而保证了至少有一个唤醒时隙可以重叠.当狆值较大时,狆2个周期中的第1个周期的唤醒时间几乎可以忽略, 因此与Q u o r u m协议相比, 在同样的发现延迟要求下,U  C o n n e c t的占空比更小.这一点也在最优近似比(1 . 5) 上得以体现.图5 U  C o n n e c t协议为了得到比U  C o n n e c t协议更佳的最优近似比,B a k h t等人[4 2,5 2]进一步提出了S e a r c h L i g h t协议. S e a r c h L i g h t将时隙以狋×狋/2的矩阵形式排列, 选取每一列的第1个时隙作为锚点时隙, 并选取第犻列的第犻+1个时隙为探测时隙, 其中1犻狋/2 .当狋=1 0时, 唤醒调度模式如图6所示, 第1列0、1 0、2 0、3 0、4 0个时隙为锚点时隙犃,1、2、2 3、3 4、4 5个时隙为探测时隙犘.图6 S e a r c h L i g h t协议与U  C o n n e c t协议类似,S e a r c h L i g h t邻居间的锚点时隙和探测时隙必然会有一次重叠. S e a r c h L i g h t在理论上有比U  C o n n e c t更小的近似比为槡2, 这意味着它在占空比相同的前提下所需的邻居发现时间比U  C o n n e c t更短.S e a r c h L i g h t协议将唤醒调度模式矩阵的长宽比固定为2∶1, 一定程度上制约了调度模式的灵活性.为了研究长宽比可调整的更通用情形,C h e n等879计  算  机  学  报2 0 1 6年 人[5 3]提出了一种基于C o n t i n u o u sT o r u sQ u o r u m( 简称C  T o r u sQ u o r u m) 的邻居发现协议.如图7所示, 在高度为犺和宽度为狑的时隙矩阵中选取任意一列和其后的任意一行的连续狑/2个时隙作为唤醒时隙, 同样可以确保邻居发现的确定性.作者证明了犺=狑/2是最优的Q u o r u m比例, 实质上此时的唤醒调度与S e a r c h L i g h t协议等价, 其最优近似比同样为槡2.图7 C  T o r u sQ u o r u m协议为了追求更优的最优近似比,W a n g等人[4 3,6 9]提出了B l i n d D a t e协议在S e a r c h L i g h t的基础上通过精心安排探测时隙的位置, 进一步提高了邻居发现的效率, 使最优近似比达到了更低的1 . 3 4. B l i n d D a t e将由狊个时隙组成的时间段称为块, 每个周期中包含犿个块, 每个周期的最后一个时隙作为静态时隙犛, 其作用类似于S e a r c h L i g h t中的锚点时隙.B l i n d D a t e从犿个块中选出犽个块作为动态块犇,其作用类似于S e a r c h L i g h t中的探测时隙.每经过一个周期, 不同块中的动态时隙犇向不同方向移动一个时隙, 直至到达块的边界时折回块中的第1个时隙.例如, 图8中左边的犇一直向右移动, 而右边的犇一直向左移动, 经过狊个周期后, 该模式就会重复出现, 这段时间称为超周期犜.作者论证了在占空比相同的情况下, 每个周期中块的个数犿=5, 动态块个数犽=2时, 可以得到最小的发现延迟, 同时保证邻居发现的确定性.当狊取值较大时, 动态块实际上覆盖了图中约2/5的区域, 相对于S e a r c h L i g h t( 覆盖了约1/2的区域) 更优.因此, 在发现延迟相同的情 况 下,B l i n d D a t e的 占 空 比 要 略 低 于S e a r c h L i g h t, 其最优近似比仅为9/槡5≈1 . 3 4, 是现存对称邻居发现协议中最接近理论最优值的方法.图8 B l i n d D a t e协议3 . 1 . 3 基于Q u o r u m协议的通用框架本节上文提到的邻居发现协议都将唤醒调度模式以矩阵的形式表达, 并以固定的模式选择唤醒时隙以保证邻居发现. J i a n g等人[7 07 1]对Q u o r u m协议进行了推广, 将这些模式具有非空交集的特征归结为Q u o r u m系 统 的 旋 转 闭 包 特 性 (R o t a t i o nC l o s u r eP r o p e r t y) , 提出了三类典型的Q u o r u m系统:G r i dQ u o r u m系统、T o r u sQ u o r u m系统和C y c l i cQ u o r u m系统, 并证明了各类Q u o r u m系统相应的最优近似比为2、槡2和1.为了进一步抽象各类基于Q u o r u m协议的调度模式和协议参数,S u n等人[5 4]提出的H e l l o协议将各类协议以统一的通用框架描述.在H e l l o协议中, 唤醒调度周期表示为一个犮×狀的矩阵, 其中犮为一个周期的长度,狀为周期个数.如图9所示, 图中的犌和犘分别表示守卫(G u a r d i a n) 时隙和巡查(P a t r o l) 时隙, 每个周期的第0个时隙为守卫时隙,每狀个周期中第1个周期的[1. .犮/2] 部分时隙为巡查时隙.由于守卫时隙和巡查时隙覆盖了超过一半的周期长度, 从而保证了守卫时隙和巡查时隙必然会在犮×狀的时间段内重叠.图9 H e l l o协议图1 0 H e l l o协议作为通用框架通过调整犮和狀的参数值, 不同的确定性邻居发现协议可以统一变换为H e l l o协议( 允许存在冗余的唤醒时隙).如图1 0(a) 所示, 将Q u o r u m协议选取的行列分别平移到第1行第1列就可以覆盖H e l l o协议的唤醒时隙, 此时第1个周期存在犮/29795期裘莹等:传感器网络邻居发现协议综述 的冗余时隙.如图1 0(b) 所示, 当参数犮=狀且为质数时,U  C o n n e c t就是H e l l o协议的一种特殊情况.如图1 0(c) 所示, 当参数狀=犮/2且将探测时隙移至第1个周期,S e a r c h L i g h t可以变换为H e l l o协议的一种特殊情况.如图1 0(d) 所示,C  T o r u s协议使用了与H e l l o协议唤醒调度方式基本相同, 然而H e l l o协议侧重于灵活的参数选取以满足对称和非对称情况下的占空比和发现延迟的平衡.3 . 1 . 4 组合设计协议上文中提及的邻居发现协议逐步减小了在相同发现延迟要求下所需的占空比.然而, 它们都没有达到理论上最优的边界. Z h e n g等人[5 6]研究了邻居发现协议的最优化问题, 明确提出了对称邻居发现唤醒调度模式的理论边界, 并提供了一种构造最优唤醒调度模式的方法.文中证明了对称邻居发现协议在犜个时隙内至少有犿次重叠时, 所需唤醒的时隙个数下界为槡犿犜.作者认为对称邻居发现问题本质上等同于集合的移位自相交问题, 根据组合设计理论中的差集和乘子定理[7 2]提供了一种可行的最优唤醒调度模式.设犜为唤醒调度周期,犽为一个周期内的唤醒次数,犿为重叠的唤醒时隙个数, 作者称这种调度模式为(犜,犽,犿)设计.依据乘子定理, 当唤醒次数犽为质数的幂次时, 必然存在一种(犽2+犽+1,犽+1,1)设计.图1 1展示了一种满足最优设计条件的(7,3,1)设计.在一个调度周期内, 无论该模式的时隙偏移是多少, 它总是与任意邻居有至少一个重叠的唤醒时隙.图1 1 组合设计协议组合设计协议达到了最优化唤醒调度的目的,其占空比为(犽+1) / (犽2+犽+1).当占空比需求为1%时, 组合设计协议的邻居发现延迟约为1 0 0 0 0个时隙, 与Q u o r u m协议相比快了4倍.然而, 从软件实现角度考虑, 组合设计协议唤醒调度模式需要预先计算, 并以调度表的形式写入节点存储空间.若占空比要求为0 . 1%, 则每个调度值需要用3 2位无符号整型数表示, 那么调度表所占用的空间约为4K字节.若需要更小的占空比则调度表所占用的空间将更大.因此, 实际中需要综合考虑占空比和传感器节点的存储空间以决定使用哪种邻居发现算法.表2比较了本节中涉及的确定性对称邻居发现协议的参数和评价标准的理论值.表2 确定性对称邻居发现协议参数和评价标准理论值协议参数占空比发现延迟犘 犔乘积最优近似比5 1%[1 4]犜稍大于5 0%犜犔/2∞Q u o r u m[5 1]狀∈?+2狀-1狀2狀22槡犔-12U  C o n n e c t[4 6]质数狆狆+12+()狆狆2狆23槡犔+121 . 5S e a r c h L i g h t[5 2]狋∈?+2/狋狋2/22槡犔槡2C  T o r u sQ u o r u m[5 3]狑,犺∈?+(犺+狑/2) /狑 犺狑 犺犺+犔2犺槡2H e l l o[5 4]犮,狀∈?+(犮/2 +狀) /犮 狀犮 狀犮/2 +犔/犮槡2B l i n d D a t e[4 3]狊∈?+35狊5狊29犔/槡59/槡5组合设计[5 6]犽=狆狇,狆为质数,狇∈?+犽+1犽2+犽+1犽2+犽+1犔-3槡4+1213  2 非对称邻居发现在实际应用中, 不同角色的节点往往具有不同的唤醒调度占空比需求.例如, 电源供应充足的节点会设置较大的占空比以迅速发现邻居, 这是对称邻居发现协议所无法处理的.非对称邻居发现协议对这类问题提出了有效的解决方法, 它并不要求每个节点有相同的唤醒调度模式, 每个节点的占空比可以根据需求调节.值得注意的是, 对称邻居发现可以视为非对称邻居发现的一种特殊情况, 运用互质方法或倍数方089计  算  机  学  报2 0 1 6年 法等手段改造对称邻居发现协议, 可以将其应用于非对称邻居发现.3 . 2 . 1 互质方法非对称邻居发现中, 如何选取不同长度的唤醒调度周期以保证有重叠的唤醒时隙是一个难题.利用孙子定理( 又称为中国剩余定理)[7 3]可以有效地解决该问题, 当一对节点唤醒调度周期互质时, 根据孙子定理可以保证在若干个周期后唤醒时隙会有重叠.D u t t a等人[4 1]提出的D i s c o协议率先根据孙子定理设计了一种非对称邻居发现协议.节点犃、犅的唤醒调度周期分别为正整数犿犃、犿犅, 且节点只在每个周期的第0个时隙唤醒.当犿犃,犿犅互质时, 根据孙子定理可以保证犃、犅必定会在犿犃犿犅的时间内有一次重叠的唤醒时隙.如图1 2所示, 当犿犃=3,犿犅=5时, 无论犅的启动时间相对于犃的偏移是多少, 在1 5个时隙内必定会出现一次重叠.图1 2 D i s c o协议由于需要保证网络中任意一对节点选取的犿都互质, 因此上述方法的难点在于如何合理选取唤醒调度周期犿的值.理论上可以采用预分配或集中式统一分配的方式, 但这会增加传感器网络部署的难度.为了保证互质,D i s c o协议规定犿必须为质数以保证邻居间犿的互质性.由于互质性约束, 邻居节点不能选取相同的犿值.这就导致了该方法在对称的特殊情况下无法使用.为解决这一问题,D i s c o要求每个节点选取一对互不相同的质数狆1、狆2为周期进行唤醒调度, 即使邻居节点选取了相同的质数对(狆1,狆2) , 也可以保证在狆1狆2的时间内会有重叠, 此时的占空比为两个独立的调度模式占空比之和1/狆1+1/狆2.D i s c o协议进一步探讨了狆1、狆2的选取对占空比的影响.在对称的情况下, 假设应用的占空比要求为2%, 那么狆1、狆2可以有多种选取方式, 例如, 选择(9 7,1 0 3) 或者(5 3,8 8 3) 都可以使占空比为2%.然而(9 7,1 0 3) 的选取方式仅需9 7×1 0 3=9 9 9 1个时隙的发现延迟, 而(5 3,8 8 3) 需要4 6 7 9 9个时隙的发现延迟.因此, 在满足占空比要求的前提下, 应选取使狆1狆2尽可能小的质数对以使邻居发现延迟最小化.在非对称的情况下,D i s c o认为选择接近占空比倒数的质数作为狆1可以最小化邻居发现延迟.例如, 占空比要求仍然为2%, 两个相邻的节点分别选择(5 3,8 8 3) , (5 7,4 0 9) 时 发 现 延 迟 为5 3×5 7=3 0 2 1, 远小于选择(9 7,1 0 3) 作为参数时的发现延迟.D i s c o需要根据网络的对称性分别设定协议参数, 增加了实际应用的部署难度.为了能够灵活地根据应用特性指定合适的参数,H e l l o协议[5 4]提出只需调整参数犮就可以针对网络的对称程度作出相应的优化.如图1 3所示,犇 犆为所需的占空比, 当犮接近于1/犇 犆时, 可以达到非对称情况下最优的发现延迟; 当犮接近于2/犇 犆时, 可以达到对称情况下最优的发现延迟.图1 3 H e l l o协议周期长度犮的参数空间D i s c o协议为邻居发现协议的设计提供了一种新颖的思路, 但是它为了解决对称的特殊情况付出了较大的代价, 采用两个质数作为唤醒调度周期的方法使占空比增大了约一倍.在对称的情况下,D i s c o相对于最优调度的近似比仅为2, 还存在进一步改良的空间. U  C o n n e c t,S e a r c h L i g h t等协议也考虑了对非对称邻居发现情况的处理, 并提出了比D i s c o更简便的方法.相对于D i s c o, 由于以上方法都选取时隙矩阵中的一列作为锚点时隙, 因此只需要将唤醒调度的周期设为质数狆就可以处理非对称的情况, 同时保留了在对称情况下必定有重叠时隙的特性.1895期裘莹等:传感器网络邻居发现协议综述 D i s c o等协议都使用质数以保证互质性.然而,1 0 0 0以内仅有不到2%的整数是质数, 使参数的选择范围受到了较大的限制. C h e n等人[5 5]提出T o d i s协议, 选取3个连续的奇数三元组(狀-2,狀,狀+2) 作为唤醒调度的参数就可以保证互质性, 同时显著增加了可选的参数空间.虽然该三元组的互质性并不对所有的奇数狀成立, 但作者论证了最小的非互质三元组为(1 6 0 0 0 2 3,1 6 0 0 0 2 5,1 6 0 0 0 2 7) 和(2 0 4 6 9 1 5,2 0 4 6 9 1 7,2 0 4 6 9 1 9) , 这两组三元组对应的占空比远远小于实际应用中可能采用的占空比, 因此可以认为任意两组由3个连续奇数组成的三元组所确定的唤醒调度模式必定存在互相重叠的时隙.由于T o d i s协议仅需要参数狀为奇数, 在给定占空比需求时,T o d i s可以得到比D i s c o更好的占空比粒度.3 . 2 . 2 倍数方法互质方法虽然为大多数邻居发现协议所用, 然而它并不是唯一可以解决非对称邻居发现问题的方法. S e a r c h L i g h t协议[4 2]提出了倍数方法, 邻居节点间的唤醒调度周期具有倍数关系.假设节点犃、犅的周期分别为犜、狀 犜, 其中狀为正整数, 那么唤醒调度周期较短的节点犃重复狀次调度周期后便与节点犅的唤醒调度周期等长.如图1 4所示, 只需要保证在狀 犜的时间内犃和犅有重叠的唤醒时隙, 就可以确保两者互相发现.此外, 作者提出周期长度应从正整数狀的幂次集合{狀,狀2,狀3, …} 中按占空比需求选取, 以保证所有节点的唤醒调度周期都是倍数关系.倍数方法本质上是将非对称问题转化为对称问题进行解决, 周期较长的唤醒调度中必须连续覆盖长度为犜的时隙以保证邻居发现的确定性.图1 4 倍数方法3 . 2 . 3 Q u o r u m方法3 . 1 . 2节中提到的Q u o r u m协议[5 1]仅能处理对称邻居发现,C h a o等人[7 4]将Q u o r u m协议扩展至非对称情况, 提出了AQ E C(A d a p t i v eQ u o r u m B a s e dE n e r g yC o n s e r v i n g) 协议,Q u o r u m的大小可以根据节点对能耗需求的不同来进行设置, 但仍然采用选取时隙矩阵中一行一列的方法决定调度周期的唤醒时隙.作者证明了该方法仍然可以保证邻居发现的确定性, 确保了非对称情况下的唤醒时隙有重叠.C h e n等人[5 5]提出了H e d i s协议, 将调度周期设置为狀(狀-1) 的矩阵, 其唤醒调度定义如下:ψ(狋)=0,其他情况1,狋=狀 犻, (狀+1)犻+1(犻=0,1, …,狀- 2{)(7)例如, 当狀=5和狀=7时,H e d i s协议的调度方式如图1 5所示.图1 5 H e d i s协议若一对节点具有不同的参数狀,犿, 作者证明了只要狀,犿具有相同的奇偶性就可以保证互相发现,并且平均发现延迟为犗(狀 犿).3 . 2 . 4 组合设计方法组合设计方法可以得到最优的调度模式, 因此研究非对称发现的最优组合设计具有一定的理论指导意义. Z h e n g等人[5 6]认为, 在非对称的情况下, 设计最优唤醒调度问题可以归结为图的顶点覆盖问题.然而, 寻找图的最优顶点覆盖问题是N P完全问题, 目前还没有相应的算法可以在多项式时间内解决该问题.此外, 该算法为集中式算法, 需要知道全网的拓扑信息, 通信代价较高, 这在实际的网络中通常难以实现.L a i等人[7 57 6]将对称组合设计方法加以扩展,使其可以应用到仅有两种不同占空比需求的非对称情况中.作者将文献[5 6] 中提出的(犖,犽,λ) 差集扩展为适用于非对称情况下的(犖,犽,犕,犾) 差集, 增加的参数犕为非对称节点对中占空比较高的节点在一个周期内唤醒的时隙个数.满足(犖,犽,犕,犾) 差集的设计可以确保异构旋转闭包特性, 即在非对称的情况下不同调度模式的节点可以互相发现.文中提出了两种满足异构旋转闭包特性的非对称邻居发现唤醒调度模式, 分别为栅格Q u o r u m模式和循环289计  算  机  学  报2 0 1 6年 Q u o r u m模式.栅格Q u o r u m模式与文献[7 4] 中提出的AQ E C协议基本相同.与栅格Q u o r u m模式相比, 循环Q u o r u m模式可以用更少的唤醒时隙保证异构旋转闭包特性, 从而使节点的占空比更低.在循环Q u o r u m模式中, 两个节点各自的调度模式需要满足旋转闭包特性, 即对于任意的相对偏移它们的调度模式都会有非空交集.根据对称组合设计[5 6]中提出的方法, 两个节点可以分别得到满足(狀,犽,λ) 差集的多种调度模式, 作者将两者的调度模式进行组合, 并扩展较短的周期使之与较长的周期等长, 随后验证扩展后的两个调度周期是否存在重叠, 以筛选出符合异构旋转闭包特性的调度周期.该方法可以达到理论上的最优解, 但由于筛选算法时间复杂度和空间复杂度较高, 并不适用于实际计算和存储资源受限的传感器节点.4 随机邻居发现随机邻居发现协议[3 4,5 7,7 77 8]使用随机广播邻居通告消息的方式发现邻居.随机邻居发现的性能问题值得关注.从直觉上看, 采用随机发送的盲目性较大, 其发现邻居的效率未必比确定性邻居发现高.然而, 根据生日悖论(B i r t h d a yP a r a d o x)[7 9], 随机邻居发现的效果远比想象中好.生日悖论表述如下: 如果一个房间里有2 3个或2 3个以上的人, 那么至少有两个人生日相同的概率大于5 0%; 在5 0个人中有相同生日的概率高 达9 7%.这两个概率之高出乎绝大多数人的意料, 但可以论证它完全是正确的.当房间里有狀个人时, 至少有两个人生日相同的概率为狆(狀)=1-狆-(狀)=1-3 6 5!3 6 5狀(3 6 5-狀)(8)其函数如图1 6所示, 横轴表示房间中的人数, 纵轴表示至少有两人生日相同的概率.图1 6 生日悖论中至少有两人生日相同的概率M c G l y n n等人[5 7]将生日悖论的特性应用于邻居发现中, 提出了B i r t h d a y协议.假设一段时间可以分为狀个时隙, 两个邻居节点随机选择犽个时隙醒来, 那么在这狀个时隙中至少有一次在同一个时隙醒来的概率为犙(狀,犽)=1-狀-犽()()犽狀犽(9)例如, 在1 0 0个时隙内有1 6个时隙为唤醒时隙, 每对邻居间互现发现的概率为犙(1 0 0,1 6)≈0 . 9 5, 而此时占空比仅为1 6%.为了避免两个节点在同一个时隙内发送消息而产生冲突,B i r t h d a y协议进一步将每个时隙分为3种状态: 发送状态、 监听状态和节能状态, 每个状态所对应的概率为狆狋,狆犾,1-狆狋-狆犾.对于网络中的任意一对节点犃、犅, 当且仅当犃处于发送状态且犅处于监听状态时, 才可以称为“犃发现了犅”.因此, 每个时隙内犃发现犅的概率为狆犾狆狋,狀个时隙内犃至少发现一次犅的概率为犘(犃发现犅)=1-(1-狆犾狆狋)狀(1 0)B i r t h d a y协议在初始阶段可以快速地发现大部分邻居, 相比确定性协议能获得更低的平均发现延迟, 文献[3 4,8 0] 对此进行了更深入的分析.然而,B i r t h d a y协议在多个邻居发现消息竞争发送时, 产生冲突的节点仍然采用完全随机的方式继续进行邻居发现. V a z q u e z  G a l l e g o等人[8 1]使用反馈机制通知产生冲突的节点在下一个竞争窗口中重复随机邻居发现, 而没有产生冲突的节点被认为已发现, 不必在后续时隙中再次发送邻居发现消息, 从而减少了冲突发生的概率, 同时降低了发现延迟和通信能耗.C h e n等人[5 8]提出了基于质数集的邻居发现协议P S B A, 减少了B i r t h d a y协议的平均发现延迟.P S B A根据应用需要的占空比选取质数集犐, 并随机地从犐中选取一个质数作为当前的唤醒周期.在重复以该质数为周期调度α次后, 再次在犐中随机地选取另一个质数作为下一个唤醒周期, 如此循环进行. P S B A利用质数间隔以提高节点唤醒时隙相遇的可能性, 当占空比需求为1%时,P S B A理论上可以在1 0 1 0 4个时隙内发现8 0 . 7%的邻居, 而在相同的条件下,B i r t h d a y仅能发现6 3 . 9%的邻居.随机发现协议的优点是原理简单易实现, 网络中的节点可以根据自身的能力自由地选择合适的占3895期裘莹等:传感器网络邻居发现协议综述 空比, 并且不需要考虑节点的唤醒调度是否对称.同时, 它的平均发现延迟一般优于确定性邻居发现协议.然而, 随机发现协议的发现延迟没有理论边界.从图1 6中可以看到当邻居发现概率到达9 5%以上时, 出现了增长速度十分缓慢的长尾现象, 为发现最后仅存的少数邻居花费了大量时间. S e a r c h L i g h t协议[4 2]结合了两者的优点, 将探测时隙随机化以减少平均发现延迟, 同时保证最坏发现延迟有确定的边界.5 协作式邻居发现前文中提及的邻居发现协议都独立地发现邻居节点, 并不需要与其他节点协作.然而, 邻居关系往往存在一定的传递性: 若犃是犅的邻居且犅是犆的邻居, 那么犃有很大的可能也是犆的邻居.这一点在稠密网络中尤其显著, 由于节点间距离较近, 在节点的通信范围内会有较多的节点可以互相通信,也就有更大的可能性满足邻居传递性.协作式邻居发现协议利用这个特性提高邻居发现的效率, 利用已知邻居发现潜在邻居. C h e n等人[8 28 3]提出了一种基于组的协作式邻居发现算法,通信范围内已互相发现的节点称为组.当组中的任意节点发现了新的邻居时, 该节点主动将本地存储的邻居信息发送给新节点.新节点利用得到的邻居唤醒调度信息准确地预测邻居节点唤醒的时刻, 并在该时刻唤醒以便接收邻居通告消息, 从而大大减少了发现延迟.采用组协作式发现时, 节点犻发现所有组内狀个节点所需的最大时间狋犵为狋犵犈犵(狋)+2犜(1 1)其中犈犵(狋) 为节点犻发现至少一个组内节点的期望时间, 定义如下:犈犵(狋)=∫犜m i n,犻0狋∑狀- 1犼=0犘犻 犼(狋)∏犽=0,犽≠犼(1-犘犻 犽(狋[]) )d狋(1 2)其中犜m i n,犻=m i n(犜犻,0,犜犻,1, …,犜犻,狀-1) , 而犘犻 犼(狋) 为组内节点犻,犼在狋时刻前互相发现的概率.然而, 由于组内节点本地邻居表中的邻居并不一定都是新节点的邻居, 因此, 对于那些不是新节点邻居的节点信息, 一方面导致发送方浪费一部分额外的通信能量, 另一方面也会造成新节点不必要的唤醒.针对该问题, 作者进一步利用时空因素对本地邻居信息进行筛选, 仅选取空间上位置接近或时间上近期活跃的节点作为新节点可能的邻居, 从而提高了新节点发现邻居的效率, 并减少了传输邻居信息的开销. A c c[6 1]和E Q S[8 4]协议也使用了类似的协作式方法, 在邻居通告消息中加入自身和已知邻居的唤醒调度信息以加快发现间接邻居的速度.C o h e n等人[6 0]提出将已互相发现的邻居通过直接或间接相连的方式组成为一个段(S e g m e n t) ,只要段中的任意节点发现了新的邻居, 那么它就会通知段中其他节点启动邻居发现过程, 以确定它是否为自己的直接邻居.在这种方法中, 段中的节点应当以多大的时间间隔发现新邻居是设计的难点.若间隔过小, 那么在稀疏网络中节点很可能在空闲监听上浪费过多的时间; 反之, 在稠密网络中发现邻居的延迟可能会过于漫长.作者提出了3种方法估计待发现节点的邻居密度: (1) 使用段中节点的平均邻居数作为待发现节点的邻居密度; (2) 使用当前正在作邻居发现的节点其自身邻居数作为待发现节点的邻居密度; (3) 综合以上两种方式, 分别计算出密度并赋予恰当的权重, 相加后得出的值作为待发现节点的邻居密度.作者使用最小均方差方法以比较3种方法的准确性.在节点均匀分布的情况下,3种方法的最小均方差分别为: (1)犕犛 犈1=犞 犪 狉(犡) ;(2)犕 犛 犈2≈0 . 8 4犞 犪 狉(犡) ; (3)犕 犛 犈3≈0 . 6 6犞 犪 狉(犡).其中犡为节点邻居数的随机变量.由此可见, 第3种方法在均匀分布的情况下可以得到最好的准确性.本节前文所述的协作式发现协议都需要通过对邻居发现消息作出响应以达到双向邻居发现, 然而,响应包会增加通信开销, 并且增加了与邻居通告消息冲突的可能性.此外, 由于存在节点间仅具有单向通信链路的可能性[8 5], 所以邻居通告响应消息在这种情况下是无效的. P u r o h i t等人[5 9]提出了W i F l o c k协议认为不需要邻居发现响应消息也可以达到类似的邻居发现的效果, 从而避免了传输响应消息的开销. W i F l o c k以单向发现作为基本操作, 将邻居发现和组维护过程相结合, 在信标消息中加了邻居组信息, 并使用协作式同步侦听和空间均分传输机制实现了更小的发现延迟和更快的组信息维护.6 按需邻居发现前文提及的邻居发现协议自节点启动后一直使用固定的模式发现邻居, 而决定发现模式的相关全局参数已经在网络部署前根据发现延迟和占空比需489计  算  机  学  报2 0 1 6年 求确定, 在网络运行过程中始终保持不变.然而, 这类协议并不能很好地处理以下两种情形.(1) 上层网络协议对不同阶段邻居信息的实时性要求不同.例如在环境监测应用中, 上层协议通常希望传感器节点在启动阶段邻居发现服务时能尽快提供邻居信息以建立到汇聚节点的通路, 从而及时上报采集到的感知数据.而在网络的稳定期, 由于网络拓扑已经趋于稳定, 上层协议对邻居信息的实时性要求并没有启动阶段那么迫切.(2) 用户参与交互在由智能终端设备组成的移动传感器网络应用中, 通常用户会参与到设备间的交互.当用户提出邻居发现请求时, 邻居发现服务应当尽快返回邻居信息以减少用户等待的时间, 提高用户体验.这两种情形的共同点是需要邻居发现协议能够动态地根据外部请求调整发现模式以提高邻居发现能力.按需邻居发现协议采取了用额外的能量换时间的方法, 在需要快速发现邻居时增加唤醒时隙的数量, 从而具备了按需动态调整邻居发现模式的能力.6  1 分阶段发现为了解决第1种情形中存在的问题,C o h e n等人[6 0]提出将邻居发现过程分为两个不同的阶段: 初始阶段和正常工作阶段.节点启动完成时进入初始阶段.在这个阶段中, 为了尽快让其他节点发现, 该节点以较高的频率广播邻居通告消息, 并在剩余时间处于唤醒状态以接收其他节点的邻居通告消息,以便快速发现所有邻居节点.进入正常工作阶段后,节点可以使 用常规的 邻 居 发 现 协 议 以 持 续 发 现邻居.6  2 增加发现时隙Z h a n g等人提出的A c c[6 1]有效解决了第2种情形中的问题. A c c并不是一种邻居发现协议, 而是按需加速邻居发现的中间件.它利用现存邻居发现协议作为底层协议持续地发现邻居, 并使用第5节中所述的协作方式交换邻居的唤醒调度信息.已知邻居和它们的调度信息有助于按需快速发现潜在邻居.当需要按需发现时,A c c会增加唤醒时隙以提高发现邻居的速度.然而, 新增的时隙应当放置在哪些位置以最大化邻居发现的效率是A c c设计的难点.为了对每个候选的时隙进行量化评估,A c c认为可以从时间差异性和空间相似性两方面分别考虑.时间差异性是指一对节点的调度周期中不是同时唤醒的时隙个数, 可以定义如下:α(犻,犼)狋0→狋=|犿(犻,犻)狋0→狋|-|犿(犻,犼)狋0→狋|狋-狋0(1 3)其中犿(犻,犼)狋0→狋是节点犻,犼从狋0到狋时刻中共同唤醒的时隙数.时间差异值越大, 说明这两个节点的调度模式差异越大, 也就更有可能通过对方发现新的邻居.空间相似性是指两个节点本地邻居表中共有的邻居数, 代表了两个节点在空间上的接近程度, 定义如下:β(犻,犼)狋0=|狀(犻,犼)狋0||狀(犼,犼)狋0|(1 4)其中狀(犻,犼)狋0是节点犻,犼在狋0时刻所共有的邻居集合.空间相似性大的节点发现的新邻居通常也是本节点的邻居.在确定了每个候选时隙的时隙收益后,当按需发现请求到来时, 只需选择时隙收益最高的几个时隙作为额外增加的时隙, 便可以快速地发现邻居.为了综合分析时间差异性和空间相似性对邻居发现的影响,A c c提出了时隙收益(S l o tG a i n) 的评价标准, 定义如下:γ(犛)狋0→狋=∑犻∈狀(犛,犛)狋0α(犻,犛)狋0→狋β(犻,犛)狋0(1 5)选择时隙收益越大的时隙就有越大的可能发现新的邻居.7 多信道邻居发现为减少能耗, 大多数传感器网络应用都选用功耗极低的符合I E E E8 0 2 . 1 5 . 4标准的射频芯片作无线通信的基础硬件. I E E E8 0 2 . 1 5 . 4标准[8 6]定义了1 6个信道用于互不干扰地通信.在邻居发现过程中, 合理地分配和利用这些信道可以有效地减轻来自同类设备或其他工作在2 . 4G频段设备的干扰[8 7].H u a n g等人[6 2]提出了基于组合设计[5 6]的多信道邻居发现协议E a s i N D.作者将网络中的节点分为两类, 被动待发现节点和主动发现节点.被动待发现节点使用固定的信道周期性地唤醒, 而主动发现节点顺序使用多个信道扫描被动待发现节点.主动发现节点将组合设计得出的最优发现模式扩展到每个信道中, 而被动待发现节点也使用相同的唤醒调度5895期裘莹等:传感器网络邻居发现协议综述 模式, 因此, 当主动发现节点扫描至被动待发现节点所在的信道时, 两者必然存在唤醒时隙的交集, 从而互相发现.该方法实质上是组合设计在多信道上的扩展, 其他单信道邻居发现协议也可以通过类似的方法扩展到多信道中使用.除了I E E E8 0 2 . 1 5 . 4标准, 传感器网络也常用蓝牙技术作为无线通信的底层协议.蓝牙技术是一种低功耗、 短距离的无线通信技术, 广泛应用于智能、 可穿戴设备、 无线外围设备等移动设备中, 用于代替传统的线缆连接.由于蓝牙设备通常使用电池供电, 且电池容量往往受到设备体积的约束, 因此节能是其协议设计需要考虑的重要因素, 这一点与传感器网络协议的设计目标相同.蓝牙4 . 0标准中的B L E(B l u e t o o t hL o wE n e r g y)模式工作在频段2 4 0 2~2 4 8 0MH z之间的3个信道上, 每个信道的带宽为4 0MH z, 相应的工作频段为2 4 0 2、2 4 2 6和2 4 8 0MH z,B L E中处于邻居发现阶段的设备可以工作在3个不同的模式下, 通告模式、 扫描模式和初始化模式.通告模式中, 设备周期性地在3个不同的信道上发送邻居通告消息, 随后立即监听邻居设备的响应, 若收到相应邻居的响应, 则双方彼此发现.在扫描或初始化模式中, 设备周期性地唤醒以轮流检测各信道中是否有邻居通告消息.在这种发现模式中, 通告消息的发送周期和扫描间隔对占空比和发现延迟有直接的影响, 如何合理地选取这两个参数决定了设备发现邻居所需的能耗和发现延迟.L i u等人[6 3]为B L E的邻居发现过程进行了建模分析, 以确定通告消息的发送周期和扫描的间隔与邻居发现延迟的关系.文中将扫描模式的周期根据不同的信道分为3个区域, 并根据接收邻居通告消息可能性的不同将每个区域划分为3种不同类型的块, 分别计算通告消息位于该块的概率以及相应的发现延迟, 从而得到邻居发现延迟的期望.根据期望的表达式, 得出当通告消息发送的间隔越小或扫描信道的间隔越大时, 邻居发现延迟越小.8 邻居发现协议比较本文中提及的邻居发现协议各具特点, 但也不可避免地在特定的条件下存在某些缺陷.本节对邻居发现协议进行了全面的比较, 以便为未来的应用提供参考.在实际应用中, 设计者应根据网络环境、应用对占空比与发现延迟的要求和协议开销等各方面选择合适的邻居发现协议.为比较邻居发现协议的性能, 我们选取了本文中具有代表性的协议在真实环境中进行实验.实验在2 0个真实环境中的N P UMO T E节点上运行, 节点的 微 控 制 器 为ATm e g a 1 2 8 R F A 1, 集 成 了 符 合I E E E8 0 2 . 1 5 . 4标准的射频模块, 并通过U S B线缆连接到P C机以收集邻居发现时间数据.节点上运行T i n y O S2. x操作系统, 所有协议的占空比统一设为5%, 时隙长度设为5 0m s .在每个活跃时隙, 邻居通告消息按2 . 2 . 2节中所述在开头和结束时各发一次的方式以保证双向发现.实验结果如图1 7所示, 其中横坐标为经过的时隙数, 纵坐标为到该时隙时所发现的邻居数占所有邻居数的比率.图中的S e a r c h L i g h t +δ和B l i n d D a t e +δ协议使用了2 . 2 . 2节中所述延长唤醒时隙的方法以减少发现延迟, 从而在最坏发现延迟上表现最佳.从邻居发现速度上来看,B i r t h d a y协议超过了所有的确定性协议, 体现出了随机发现协议在平均发现延迟上的优势.然而, 当邻居发现比率高于8 0%时,B i r t h d a y协议不可避免地出现了长尾现象.图1 7 典型邻居发现协议实验比较, 占空比同为5%表3定性地比较了在同等实验场景下, 各类邻居发现协议的性能.其中发现速度以占空比相同且发现一半以上邻居为前提作比较.类似地, 占空比也是在同样的发现延迟且至少发现一半邻居的前提下进行比较.最后, 表4总结了本文中提及的各类传感器网络邻居发现协议的适用网络环境和应用范围.从表中可以看到不同的协议在不同的评价标准中各有高下, 并不存在各方面都最优的协议.因此, 在实际工程实践中通常需要根据应用的占空比与发现延迟需求、 网络的对称性等方面作权衡, 选择最适合实际网络环境的邻居发现协议.689计  算  机  学  报2 0 1 6年 表3 传感器网络邻居发现协议特点比较协议发现速度长尾现象延迟有界计算开销存储开销控制开销占空比占空比粒度Q u o r u m[5 1]中等中等是低低低高中等S e a r c h L i g h t[5 2]快轻是低低低较低低U  C o n n e c t[4 6]较慢较轻是低低低中等较低C  T o r u s[5 3]较快较轻是低低低较低较低H e l l o[5 4]较快较轻是低低低较低较低B l i n d D a t e[4 3]快轻是较低较低低较低低T o d i s[5 5]快较轻是低低低较低较高H e d i s[5 5]快较轻是低低低较低高组合设计[5 6]快较轻是高高低低中等D i s c o[4 1]中等中等是低低低高中等B i r t h d a y[5 7]极快严重否低低低中等高P S B A[5 8]极快严重否较低低较低较低中等W i F l o c k[5 9]较快较轻是低中等中等较低中等C o h e n[6 0]较快较轻是中等中等高较低中等A c c[6 1]快较轻是中等中等中等较低中等E a s i N D[6 2]快较轻是高高低低中等B L E[6 3]中等中等是低低低中等中等表4 传感器网络邻居发现协议应用范围比较协议 应用范围 Q u o r u m[5 1]调度模式简单易构造, 适用于对称邻居发现.但存在一次多余的发现, 能耗相对较高U  C o n n e c t[4 6]调度模式简单且同时支持对称和非对称发现S e a r c h L i g h t[5 2]将探测时隙随机化后平均发现延迟较小, 适用于大多数邻居发现场景C  T o r u s[5 3]调度模式简单, 同时支持对称和非对称发现, 且能耗较低B l i n d D a t e[4 3]能耗低, 适用于对网络生存时间要求较高的场景D i s c o[4 1]适用于非对称发现场景, 可支持对称应用场景, 但需要增加能耗H e l l o[5 4]在对称或非对称的场景下可以达到较好的平衡, 适用于有不同能量预算的设备同时存在的网络H e d i s[5 5]适用于非对称发现中对占空比粒度要求高的场景T o d i s[5 5]适用于非对称发现中对占空比粒度要求高的场景组合设计[5 6]调度模式占用存储空间大, 且构造调度模式的难度较大, 适用于理论分析, 但实用价值有限B i r t h d a y[5 7]适用于只需快速发现大部分邻居的场景, 对发现延迟的边界没有要求P S B A[5 8]与B i r t h d a y协议类似, 适用于快速发现大部分邻居的场景, 但需要额外存储一定量的质数W i F l o c k[5 9]适用于需要对网络中的节点作分组维护的场景C o h e n[6 0]适用于可以容忍增加一部分控制开销用于减少发现延迟的场景A c c[6 1]适用于节点移动性较高的网络, 可按需减少现有邻居发现协议的发现延迟E a s i N D[6 2]适用于使用了多个信道的无线网络B L E[6 3]适用于蓝牙网络或与此类似的无线网络, 需要发现存在于多个不同信道内的邻居9 未来研究方向传感器网络邻居发现技术经历了由粗粒度向细粒度发展的过程, 从5 1%协议、Q u o r u m协议到D i s c o协 议、U  C o n n e c t协 议、S e a r c h L i g h t协 议 和B l i n d D a t e协议, 它们对调度模式的控制逐步精细,相对于最优调度的近似比也日益减小.另一个发展趋势是邻居发现协议都同时考虑了唤醒调度对称和非对称的情况, 使协议能满足不同的能耗需求.然而, 尽管这一领域已获得了一系列研究成果, 但仍存在不少问题值得进一步研究和完善.(1) 构造最优近似比更小的唤醒调度模式虽然对称邻居发现的下界已经确定并且组合设计协议已提出了一种构造最优解的方法, 但是这种解法实用性欠佳, 构造算法复杂且占用的存储空间过大.目前最优近似比最小的B l i n d D a t e协议仍与最优调度存在着一定的差距.因此构造近似比更小的邻居发现协议仍然具有较高的理论和应用价值.(2) 非对称邻居发现评价标准现存邻居发现的理论研究主要集中于对称邻居发现, 对非对称邻居发现的关注仍显不足, 目前并没有统一的标准以比较不同的非对称邻居发现算法.评价标准的缺失也导致非对称邻居发现的理论边界无法确定, 也就无法公平地量化比较各类非对称邻居发现技术.因此, 寻找非对称邻居发现评价标准并建立相应的理论是下一步研究需要关注的重点.(3) 随机邻居发现的理论分析和评价标准随机邻居发现具有平均发现延迟小的优点, 但目前并没有得到充分的研究.由于随机邻居发现的7895期裘莹等:传感器网络邻居发现协议综述 发现延迟没有边界, 因此还没有统一的标准以比较不同随机邻居发现算法的优劣.例如,P S B A协议仅通过实验说明其优于B i r t h d a y协议, 但并没有从理论上分析原因. S e a r c h L i g h t协议提出将探测时隙随机化以减少平均发现延迟, 但同样没有对此作形式化证明.由此可见, 提出统一的随机邻居发现评价标准对于研究和比较现有的协议有重要意义, 并对研究更优的随机邻居发现协议具有显著的指导作用.(4) 考虑信道占用S e a r c h L i g h t协议和B l i n d D a t e协议证实了可以通过增加邻居发现消息减少发现延迟, 理论上可以运用到所有确定性发现协议中以使发现延迟减半.该方法本质上是以增加信道占用为代价换取更快速的发现, 然而, 目前并没有相关工作揭示该方法背后所蕴藏的原理, 未来的工作可以进一步研究如何合理地增加邻居通告消息以提高发现效率.(5) 与MA C协议的整合目前邻居发现协议是建立在直接控制无线收发机睡眠唤醒的基础上.然而从网络分层的角度考虑,控制无线收发机的睡眠状态应由MA C协议负责.因此, 如何协调邻居发现协议与MA C协议的分工,使两者可以有效地整合仍然存在一系列亟待解决的问题.(6) 安全隐私机制研究网络协议需要在设计时就考虑它的安全性和隐私性, 以避免恶意攻击和窃听对系统带来的不良影响.然而, 目前邻居发现协议的安全隐私机制相关研究十分有限[8 8  8 9].如何在资源受限的节点上实现邻居发现过程的认证和加密, 以及如何避免洪泛攻击、欺骗性确认攻击、S y b i l攻击等恶意攻击是保证邻居发现协议的安全性所必须要解决的问题.(7) 在I P v 6传感网中的应用下一代互联网协议— — —I P v 6协议使用邻居发现协议代替了AR P和R A R P协议以实现地址解析, 此外还用于路由发现、 前缀发现、 参数发现和地址自动配置.其中邻居发现通过周期性发送I CMP v 6邻居通告报文完成.现有工作[9 0  9 1]认为I P v 6协议适用于传感器网络, 然而各层协议都需要根据传感器网络的特性作适当地调整和简化.目前并没有符合I P v 6架构且适用于传感器网络的邻居发现协议, 如何在该架构下适配并优化邻居发现的性能也是实现传感网I P v 6化的重要环节.1 0 结束语研究作为传感器网络基础协议之一的邻居发现协议具有重要的理论意义和应用价值.本文综合学术界近年来的相关研究成果, 总结了传感器网络邻居发现的问题定义、 评价标准, 并分类介绍了各项技术的研究进展.然而, 各类新型传感器网络应用的相继出现对邻居发现协议的性能提出了更高的要求,因此仍需要进一步完善邻居发现的理论和应用技术, 为传感器网络和物联网的发展打下坚实的基础.致 谢 衷心感谢审稿人提出的宝贵修改意见!参考文献[1]M a oX,M i a oX,H eY,e ta l . C i t y S e e:U r b a nC O2m o n i t o r i n gw i t hs e n s o r s/ /P r o c e e d i n g s o f t h e 3 1 s tA n n u a l J o i n tC o n f e r e n c eo f t h eC o m p u t e r a n dC o mm u n i c a t i o n s S o c i e t i e s(I N F O C OM’1 2).O r l a n d o,U S A,2 0 1 2:1 6 1 1  1 6 1 9[2]W uX,B r o w n K N,S r e e n a nCJ .S N I P:As e n s o rn o d ei n i t i a t e dp r o b i n gm e c h a n i s mf o ro p p o r t u n i s t i cd a t ac o l l e c t i o ni ns p a r s ew i r e l e s ss e n s o rn e t w o r k s/ /P r o c e e d i n g so f t h e2 0 1 1I E E EC o n f e r e n c eo nC o m p u t e rC o mm u n i c a t i o n s W o r k s h o p s(I N F O C OM WK S H P S’1 1). S h a n g h a i,C h i n a,2 0 1 1:7 2 6  7 3 1[3]C h e b r o l uK,R a m a nB,M i s h r aN,e ta l . B r i m o n:As e n s o rn e t w o r ks y s t e mf o rr a i l w a yb r i d g em o n i t o r i n g/ /P r o c e e d i n g so ft h e6 t hI n t e r n a t i o n a l C o n f e r e n c e o n M o b i l e S y s t e m s,A p p l i c a t i o n s,a n d S e r v i c e s(M o b i S y s’0 8).B r e c k e n r i d g e,U S A,2 0 0 8:2  1 4[4]K u sB,Am u n d s o nI,S a l l a i J,e t a l . R Fd o p p l e r s h i f t  b a s e dm o b i l es e n s o r t r a c k i n ga n dn a v i g a t i o n . A CMT r a n s a c t i o n s o nS e n s o rN e t w o r k s,2 0 1 0,7(1) :1  3 2[5]H eT,K r i s h n a m u r t h yS,S t a n k o v i cJ A,e ta l .E n e r g y e f f i c i e n t s u r v e i l l a n c es y s t e mu s i n gw i r e l e s ss e n s o rn e t w o r k s/ /P r o c e e d i n g so ft h e2 n dI n t e r n a t i o n a lC o n f e r e n c eo n M o b i l eS y s t e m s,A p p l i c a t i o n s,a n dS e r v i c e s(M o b i S y s’0 4). B o s t o n,U S A,2 0 0 4:2 7 0  2 8 3[6]L i uT,S a d l e rC M,Z h a n gP,e ta l . I m p l e m e n t i n gs o f t w a r eo nr e s o u r c ec o n s t r a i n e d m o b i l es e n s o r s:E x p e r i e n c e s w i t hI m p a l aa n dZ e b r a n e t/ /P r o c e e d i n g so ft h e2 n dI n t e r n a t i o n a lC o n f e r e n c eo n M o b i l eS y s t e m s,A p p l i c a t i o n s,a n dS e r v i c e s(M o b i S y s’0 4). B o s t o n,U S A,2 0 0 4:2 5 6  2 6 9[7]Z h a n gP,S a d l e rC M,L y o nSA,e ta l .H a r d w a r ed e s i g ne x p e r i e n c e s i nz e b r a n e t/ /P r o c e e d i n g so f t h e2 n dA CMI n t e r n a t i o n a lC o n f e r e n c eo nE m b e d d e dN e t w o r k e dS e n s o rS y s t e m s(S e n S y s’0 4). B a l t i m o r e,U S A,2 0 0 4:2 2 7  2 3 8889计  算  机  学  报2 0 1 6年 [8]M a i n w a r i n gA,C u l l e rD,P o l a s t r eJ,e ta l .W i r e l e s ss e n s o rn e t w o r k sf o r h a b i t a t m o n i t o r i n g/ /P r o c e e d i n g s o ft h e 1 s tA CMI n t e r n a t i o n a lW o r k s h o po n W i r e l e s sS e n s o rN e t w o r k sa n dA p p l i c a t i o n s(WS NA’0 2).A t l a n t a,U S A,2 0 0 2:8 8  9 7[9]S z e w c z y kR,M a i n w a r i n gA,P o l a s t r e J,e t a l . A na n a l y s i s o fa l a r g es c a l eh a b i t a tm o n i t o r i n ga p p l i c a t i o n/ /P r o c e e d i n g so ft h e2 n dI n t e r n a t i o n a lC o n f e r e n c eo nE m b e d d e d N e t w o r k e dS e n s o rS y s t e m s(S e n S y s’0 4).B a l t i m o r e,U S A,2 0 0 4:2 1 4 2 2 6[1 0]E l  H o i y d iA,D e c o t i g n i eJD.W i s e MA C:A nu l t r a l o wp o w e rMA C p r o t o c o lf o r m u l t i  h o p w i r e l e s ss e n s o r n e t w o r k s/ /N i k o l e t s e a sSE,R o l i mJDPe d s .A l g o r i t h m i cA s p e c t so fW i r e l e s sS e n s o r N e t w o r k s .B e r l i n H e i d e l b e r g:S p r i n g e r,2 0 0 4:1 8  3 1[1 1]D u n k e l sA.T h ec o n t i k i MA Cr a d i od u t yc y c l i n gp r o t o c o l .S w e d e n:S I C S,T e c h n i c a lR e p o r t:T 2 0 1 1:1 3,2 0 1 1[1 2]G n a w a l iO,F o n s e c aR,J a m i e s o nK,e ta l .C o l l e c t i o nt r e ep r o t o c o l/ /P r o c e e d i n g s o f t h e 7 t h A CM C o n f e r e n c e o nE m b e d d e dN e t w o r k e dS e n s o rS y s t e m s(S e n S y s’0 9). B e r k e l e y,U S A,2 0 0 9:1  1 4[1 3]L i uY,Z h a n gQ,N i LM,e t a l . O p p o r t u n i t y  b a s e d t o p o l o g yc o n t r o l i nw i r e l e s ss e n s o rn e t w o r k s . I E E E T r a n s a c t i o n so nP a r a l l e l a n dD i s t r i b u t e dS y s t e m s,2 0 1 0,2 1(3) :4 0 5  4 1 6[1 4]G a l l u z z iV,H e r m a nT. S u r v e y:D i s c o v e r y i nw i r e l e s s s e n s o rn e t w o r k s . I n t e r n a t i o n a l J o u r n a l o f D i s t r i b u t e d S e n s o rN e t w o r k s,2 0 1 2,2 0 1 2(2 7 1 8 6 0) :1  1 2[1 5]L e v i sP. E x p e r i e n c e sf r o mad e c a d eo fT i n y O Sd e v e l o p m e n t/ /P r o c e e d i n g so f t h e1 0 t hU S E N I XC o n f e r e n c eo nO p e r a t i n gS y s t e m sD e s i g na n d I m p l e m e n t a t i o n(O S D I’1 2).H o l l y w o o d,U S A,2 0 1 2:2 0 7  2 2 0[1 6]D u n k e l sA,G r y n v a l lB,V o i g tT.C o n t i k i:Al i g h t w e i g h ta n df l e x i b l eo p e r a t i n gs y s t e mf o rt i n yn e t w o r k e ds e n s o r s/ /P r o c e e d i n g so f t h e2 9 t hA n n u a l I E E EI n t e r n a t i o n a lC o n f e r e n c eo nL o c a lC o m p u t e r N e t w o r k s(L C N’0 4).T a m p a,U S A,2 0 0 4:4 5 5  4 6 2[1 7]L a n eN D,M i l u z z oE,L u H,e ta l .As u r v e yo fm o b i l ep h o n es e n s i n g . I E E EC o mm u n i c a t i o n sM a g a z i n e,2 0 1 0,4 8(9) :1 4 0  1 5 0[1 8]D u t t aP,A o k iP M,K u m a r N,e ta l .C o mm o ns e n s e:P a r t i c i p a t o r yu r b a ns e n s i n gu s i n gan e t w o r ko fh a n d h e l da i rq u a l i t ym o n i t o r s/ /P r o c e e d i n g s o f t h e 7 t hA CMC o n f e r e n c eo nE m b e d d e dN e t w o r k e dS e n s o rS y s t e m s(S e n S y s’0 9). B e r k e l e y,U S A,2 0 0 9:3 4 9  3 5 0[1 9]D u t t aP,C u l l e rD,S h e n k e rS . P r o c r a s t i n a t i o nm i g h t l e a dt oa l o n g e ra n dm o r eu s e f u l l i f e/ /P r o c e e d i n g so ft h e6 t hA CMW o r k s h o po n H o tT o p i c si n N e t w o r k s(H o t N e t s  V I’0 7).A t l a n t a,U S A,2 0 0 7:1  7[2 0]E i s e n m a nSB,M i l u z z oE,L a n eN D,e ta l .T h eB i k e N e tm o b i l es e n s i n g s y s t e m f o r c y c l i s t e x p e r i e n c e m a p p i n g/ /P r o c e e d i n g so f t h e 5 t h I n t e r n a t i o n a lC o n f e r e n c eo nE m b e d d e dN e t w o r k e dS e n s o r S y s t e m s(S e n S y s’0 7). S y d n e y,A u s t r a l i a,2 0 0 7:8 7  1 0 1[2 1]Y a nT,M a r z i l l iM,H o l m e sR,G a n e s a nD,e t a l . m C r o w d:Ap l a t f o r mf o rm o b i l e c r o w d s o u r c i n g/ /P r o c e e d i n g so f t h e 7 t hA CM C o n f e r e n c eo nE m b e d d e d N e t w o r k e dS e n s o rS y s t e m s(S e n S y s’0 9). B e r k e l e y,U S A,2 0 0 9:3 4 7  3 4 8[2 2]Y a nT,K u m a r V,G a n e s a n D.C r o w d S e a r c h:E x p l o i t i n gc r o w d s f o r a c c u r a t e r e a l  t i m e i m a g e s e a r c h o n m o b i l ep h o n e s/ /P r o c e e d i n g so ft h e8 t hI n t e r n a t i o n a lC o n f e r e n c eo nM o b i l eS y s t e m s,A p p l i c a t i o n s,a n dS e r v i c e s(M o b i S y s’1 0).S a nF r a n c i s c o,U S A,2 0 1 0:7 7  9 0[2 3]B i a g i o n iJ,G e r l i c h T,M e r r i f i e l d T,e ta l .E a s y T r a c k e r:A u t o m a t i c t r a n s i t t r a c k i n g,m a p p i n g,a n da r r i v a l t i m ep r e d i c t i o nu s i n gs m a r t p h o n e s/ /P r o c e e d i n g so f t h e9 t hA CMC o n f e r e n c eo n E m b e d d e d N e t w o r k e d S e n s o r S y s t e m s(S e n S y s’1 1).S e a t t l e,U S A,2 0 1 1:6 8  8 1[2 4]T h i a g a r a j a nA,B i a g i o n iJ,G e r l i c h T,e ta l .C o o p e r a t i v et r a n s i t t r a c k i n gu s i n gs m a r t  p h o n e s/ /P r o c e e d i n g so ft h e8 t hA CM C o n f e r e n c eo nE m b e d d e d N e t w o r k e dS e n s o rS y s t e m s(S e n S y s’1 0). Z ü r i c h,S w i t z e r l a n d,2 0 1 0:8 5  9 8[2 5]P i e t i l  i n e nA K,O l i v e rE,L e B r u nJ,e ta l .M o b i C l i q u e:M i d d l e w a r e f o rm o b i l e s o c i a l n e t w o r k i n g/ /P r o c e e d i n g so f t h e2 n dA CM W o r k s h o po nO n l i n eS o c i a lN e t w o r k s(WO S N’0 9).B a r c e l o n a,S p a i n,2 0 0 9:4 9  5 4[2 6]M a t u s z e w s k iM,B e i j a rN,L e h t i n e nJ,e t a l .U n d e r s t a n d i n ga t t i t u d e s t o w a r d sm o b i l ep e e r  t o  p e e r c o n t e n t s h a r i n gs e r v i c e s/ /P r o c e e d i n g so f t h e2 0 0 7I E E EI n t e r n a t i o n a lC o n f e r e n c eo nP o r t a b l eI n f o r m a t i o nD e v i c e s(P O R TA B L E’0 7).O r l a n d o,U S A,2 0 0 7:1  5[2 7]Z h a n gL,D i n gX,W a nZ,e t a l .W i F a c e:As e c u r eG e o s o c i a ln e t w o r k i n gs y s t e m u s i n g W i F i  b a s e d m u l t i  h o p MAN E T/ /P r o c e e d i n g so ft h e1 s t A CM W o r k s h o po n M o b i l e C l o u dC o m p u t i n g&S e r v i c e s:S o c i a lN e t w o r k s a n dB e y o n d(M C S’1 0).S a nF r a n c i s c o,U S A,2 0 1 0:3:1  3:8[2 8]M i l u z z oE,L a n eND,F o d o rK,e t a l . S e n s i n gm e e t sm o b i l es o c i a l n e t w o r k s:T h ed e s i g n,i m p l e m e n t a t i o na n de v a l u a t i o no ft h eC e n c e M ea p p l i c a t i o n/ /P r o c e e d i n g so ft h e6 t h A CMC o n f e r e n c eo nE m b e d d e dN e t w o r kS e n s o rS y s t e m s(S e n S y s’0 8).R a l e i g h,U S A,2 0 0 8:3 3 7  3 5 0[2 9]M i l u z z oE,P a p a n d r e aM,L a n eND,e t a l . T a p p i n g i n t o t h ev i b eo f t h ec i t yu s i n gv i b n,ac o n t i n u o u ss e n s i n ga p p l i c a t i o nf o r s m a r t p h o n e s/ /P r o c e e d i n g s o f t h e 1 s t I n t e r n a t i o n a lS y m p o s i u mo nF r o mD i g i t a l F o o t p r i n t s t oS o c i a l a n dC o mm u n i t yI n t e l l i g e n c e(S C I’1 1). B e i j i n g,C h i n a,2 0 1 1:1 3  1 8[3 0]L i uH,L i J,X i eZ,e t a l . A u t o m a t i c a n dr o b u s t b r e a d c r u m bs y s t e m d e p l o y m e n t f o r i n d o o r f i r e f i g h t e r a p p l i c a t i o n s/ /P r o c e e d i n g so ft h e8 t hI n t e r n a t i o n a lC o n f e r e n c eo n M o b i l eS y s t e m s,A p p l i c a t i o n s,a n d S e r v i c e s(M o b i S y s’1 0).S a nF r a n c i s c o,U S A,2 0 1 0:2 1  3 4[3 1]H u a n gJH,Am j a dS,M i s h r aS.C e n w i t s:As e n s o r  b a s e dl o o s e l yc o u p l e ds e a r c ha n dr e s c u es y s t e mu s i n gw i t n e s s e s/ /P r o c e e d i n g so f t h e 3 r d I n t e r n a t i o n a lC o n f e r e n c eo nE m b e d d e dN e t w o r k e dS e n s o rS y s t e m s(S e n S y s’0 5). S a nD i e g o,U S A,2 0 0 5:1 8 0  1 9 19895期裘莹等:传感器网络邻居发现协议综述 [3 2]P a e kJ,K i mJ,G o v i n d a nR.E n e r g y  e f f i c i e n tr a t ea d a p t i v eG P Sb a s e dp o s i t i o n i n gf o rs m a r t p h o n e s/ /P r o c e e d i n g so ft h e8 t h I n t e r n a t i o n a l C o n f e r e n c e o nM o b i l eS y s t e m s,A p p l i c a t i o n s,a n dS e r v i c e s(M o b i S y s’1 0).S a nF r a n c i s c o,U S A,2 0 1 0:2 9 9  3 1 4[3 3]J a k l l a r iG,L u o W,K r i s h n a m u r t h y S V.A ni n t e g r a t e dn e i g h b o rd i s c o v e r ya n d MA Cp r o t o c o lf o ra dh o cn e t w o r k su s i n gd i r e c t i o n a la n t e n n a s . I E E E T r a n s a c t i o n so n W i r e l e s sC o mm u n i c a t i o n s,2 0 0 7,6(3) :1 1 1 4  1 0 2 4[3 4]V a s u d e v a nS,T o w s l e y D,G o e c k e l D,e ta l .N e i g h b o rd i s c o v e r yi n w i r e l e s sn e t w o r k sa n dt h ec o u p o nc o l l e c t o r’sp r o b l e m/ /P r o c e e d i n g s o f t h e 1 5 t h A n n u a l I n t e r n a t i o n a lC o n f e r e n c eo n M o b i l e C o m p u t i n ga n d N e t w o r k i n g(M o b i C o m’0 9). B e i j i n g,C h i n a,2 0 0 9:1 8 1  1 9 2[3 5]C a iH,W o l fT.O n2  w a yn e i g h b o rd i s c o v e r yi n w i r e l e s sn e t w o r k sw i t hd i r e c t i o n a l a n t e n n a s/ /P r o c e e d i n g so f t h e2 0 1 5I E E EI n t e r n a t i o n a lC o n f e r e n c eo nC o m p u t e rC o mm u n i c a t i o n s(I N F O C OM’1 5).H o n gK o n g,C h i n a,2 0 1 5:7 0 2  7 1 0[3 6]M a d a nR,L a l lS .A ne n e r g y  o p t i m a l a l g o r i t h mf o rn e i g h b o rd i s c o v e r y i nw i r e l e s ss e n s o rn e t w o r k s .M o b i l eN e t w o r k sa n dA p p l i c a t i o n s,2 0 0 6,1 1(3) :3 1 7  3 2 6[3 7]P o l a s t r eJ,H i l lJ,C u l l e rD.V e r s a t i l el o w p o w e r m e d i aa c c e s s f o rw i r e l e s ss e n s o rn e t w o r k s/ /P r o c e e d i n g so f t h e2 n dI n t e r n a t i o n a lC o n f e r e n c eo n E m b e d d e d N e t w o r k e d S e n s o rS y s t e m s(S e n S y s’0 4). B a l t i m o r e,U S A,2 0 0 4:9 5  1 0 7[3 8]B u e t t n e rM,Y e eGV,A n d e r s o nE,e t a l . X  MA C:As h o r tp r e a m b l e MA C p r o t o c o lf o r d u t y  c y c l e d w i r e l e s s s e n s o rn e t w o r k s/ /P r o c e e d i n g so ft h e4 t hI n t e r n a t i o n a lC o n f e r e n c eo n E m b e d d e d N e t w o r k e d S e n s o r S y s t e m s(S e n S y s’0 6).C o l o r a d o,U S A,2 0 0 6:3 0 7  3 2 0[3 9]D u t t aP,D a w s o n  H a g g e r t yS,C h e nY,e ta l .D e s i g na n de v a l u a t i o no fav e r s a t i l ea n de f f i c i e n tr e c e i v e r  i n i t i a t e dl i n kl a y e rf o rl o w p o w e rw i r e l e s s/ /P r o c e e d i n g so ft h e8 t h A CMC o n f e r e n c e o n E m b e d d e d N e t w o r k e d S e n s o r S y s t e m s(S e n S y s’1 0). Z ü r i c h,S w i t z e r l a n d,2 0 1 0:1  1 4[4 0]D u t t aP,D a w s o n  H a g g e r t yS,C h e nY,e ta l .A  MA C:Av e r s a t i l e a n d e f f i c i e n t r e c e i v e r  i n i t i a t e d l i n k l a y e r f o rl o w  p o w e rw i r e l e s s .A CM T r a n s a c t i o n so nS e n s o rN e t w o r k s,2 0 1 2,8(4) :3 0:1  3 0:2 9[4 1]D u t t aP,C u l l e rD.P r a c t i c a l a s y n c h r o n o u sn e i g h b o rd i s c o v e r ya n dr e n d e z v o u s f o rm o b i l es e n s i n ga p p l i c a t i o n s/ /P r o c e e d i n g so f t h e6 t h A CM C o n f e r e n c eo nE m b e d d e d N e t w o r kS e n s o rS y s t e m s(S e n S y s’0 8). R a l e i g h,U S A,2 0 0 8:7 1  8 4[4 2]B a k h tM,T r o w e rM,K r a v e t sRH. S e a r c h l i g h t:W o n’t y o ub em yn e i g h b o r? / /P r o c e e d i n g so ft h e1 8 t hA n n u a lI n t e r n a t i o n a lC o n f e r e n c e o n M o b i l e C o m p u t i n g a n d N e t w o r k i n g(M o b i c o m’1 2). I s t a n b u l,T u r k e y,2 0 1 2:1 8 5  1 9 6[4 3]W a n gK,M a oX,L i uY.B l i n d D a t e:An e i g h b o rd i s c o v e r yp r o t o c o l .I E E E T r a n s a c t i o n s o n P a r a l l e la n d D i s t r i b u t e dS y s t e m s,2 0 1 5,2 6(4) :9 4 9  9 5 9[4 4]D i e t r i c hI,D r e s s l e rF.O nt h el i f e t i m eo fw i r e l e s ss e n s o rn e t w o r k s .A CM T r a n s a c t i o n so nS e n s o rN e t w o r k s,2 0 0 9,5(1) :5:1  5:3 9[4 5]F o n s e c aR,D u t t aP,L e v i sP,e t a l . Q u a n t o:T r a c k i n ge n e r g yi n n e t w o r k e d e m b e d d e ds y s t e m s/ /P r o c e e d i n g so ft h e8 t hU S E N I X C o n f e r e n c e o n O p e r a t i n g S y s t e m s D e s i g n a n dI m p l e m e n t a t i o n(O S D I’0 8). S a nD i e g o,U S A,2 0 0 8:3 2 3  3 3 8[4 6]K a n d h a l uA,L a k s h m a n a n K,R a j k u m a rR.U  c o n n e c t:Al o w  l a t e n c ye n e r g y  e f f i c i e n ta s y n c h r o n o u sn e i g h b o rd i s c o v e r yp r o t o c o l/ /P r o c e e d i n g so f t h e9 t hI n t e r n a t i o n a lC o n f e r e n c eo nI n f o r m a t i o n P r o c e s s i n g i n S e n s o r N e t w o r k s(I P S N’1 0).S t o c k h o l m,W s e d e n,2 0 1 0:3 5 0  3 6 1[4 7]Y eW,H e i d e m a n nJ,E s t r i nD.A ne n e r g ye f f i c i e n t MA Cp r o t o c o lf o r w i r e l e s ss e n s o rn e t w o r k s/ /P r o c e e d i n g so ft h e2 1 s tA n n u a l J o i n tC o n f e r e n c eo f t h eC o m p u t e r a n dC o mm u n i c a t i o n sS o c i e t i e s(I N F O C OM’0 2).N e w Y o r k,U S A,2 0 0 2:1 5 6 7  1 5 7 6[4 8]R o w e A,M a n g h a r a m R,R a j k u m a rR.R T  L i n k:At i m es y n c h r o n i z e dl i n kp r o t o c o lf o re n e r g y  c o n s t r a i n e d m u l t i  h o pw i r e l e s sn e t w o r k s/ /P r o c e e d i n g s o f t h e 3 r dA n n u a l C o mm u n i c a t i o n sS o c i e t yo nS e n s o ra n dA d H o cC o mm u n i c a t i o n sa n dN e t w o r k s(S E C ON’0 6). R e s t o n,U S A,2 0 0 6:4 0 2  4 1 1[4 9]E l s o nJ,R  m e rK.W i r e l e s s s e n s o rn e t w o r k s:An e wr e g i m ef o r t i m e s y n c h r o n i z a t i o n . S I G C OMMC o m p u t e rC o mm u n i c a t i o nR e v i e w,2 0 0 3,3 3(1) :1 4 9  1 5 4[5 0]M a r ó t i M,K u s y B,S i m o n G,e ta l .T h ef l o o d i n gt i m es y n c h r o n i z a t i o n p r o t o c o l/ /P r o c e e d i n g s o f t h e 2 n d A CMI n t e r n a t i o n a lC o n f e r e n c eo n E m b e d d e d N e t w o r k e d S e n s o rS y s t e m s(S e n S y s’0 4). B a l t i m o r e,U S A,2 0 0 4:3 9  4 9[5 1]T s e n gY,H s uC,H s i e hT. P o w e r  s a v i n gp r o t o c o l s f o r I E E E8 0 2 . 1 1  b a s e dm u l t i  h o pa dh o c n e t w o r k s . C o m p u t e rN e t w o r k s,2 0 0 3,4 3(3) :3 1 7  3 3 7[5 2]B a k h tM,K r a v e t sR. S e a r c h L i g h t:A s y n c h r o n o u sn e i g h b o rd i s c o v e r y u s i n g s y s t e m a t i c p r o b i n g . A CM S I GMO B I L EM o b i l e C o m p u t i n g a n d C o mm u n i c a t i o n s R e v i e w,2 0 1 1,1 4(4) :3 1  3 3[5 3]C h e n L,Y a n B,Z h a n g J,e t a l . N e i g h b o r d i s c o v e r ya l g o r i t h mi nm o b i l e l o wd u t yc y c l ew s n s . J o u r n a l o f S o f t w a r e,2 0 1 4,2 5(6) :1 3 5 2  1 3 6 8[5 4]S u nW,Y a n gZ,W a n gK,e ta l .H e l l o:Ag e n e r i cf l e x i b l ep r o t o c o lf o rn e i g h b o rd i s c o v e r y/ /P r o c e e d i n g so ft h e2 0 1 4I E E EI n t e r n a t i o n a lC o n f e r e n c eo nC o m p u t e rC o mm u n i c a t i o n s(I N F O C OM’1 4). T o r o n t o,C a n a d a,2 0 1 4:5 4 0  5 4 8[5 5]C h e nL,F a nR,B i a nK,e ta l .O nh e t e r o g e n e o u sn e i g h b o rd i s c o v e r yi n w i r e l e s ss e n s o r n e t w o r k s/ /P r o c e e d i n g s o ft h e2 0 1 5I E E EI n t e r n a t i o n a lC o n f e r e n c eo nC o m p u t e rC o mm u n i c a t i o n s(I N F O C OM’1 5).H o n gK o n g,C h i n a,2 0 1 5:1  9[5 6]Z h e n gR,H o uJC,S h aL. A s y n c h r o n o u sw a k e u p f o r a dh o cn e t w o r k s/ /P r o c e e d i n g s o f t h e 4 t h A CM I n t e r n a t i o n a lS y m p o s i u m o n M o b i l e A d H o c N e t w o r k i n g & C o m p u t i n g(M o b i H o c’0 3).A n n a p o l i s,U S A,2 0 0 3:3 5  4 5[5 7]M c G l y n n M J,B o r b a s hS A.B i r t h d a yp r o t o c o l sf o rl o we n e r g yd e p l o y m e n ta n df l e x i b l en e i g h b o rd i s c o v e r yi na d  h o cw i r e l e s sn e t w o r k s/ /P r o c e e d i n g so f t h e2 n dA CMI n t e r n a t i o n a lS y m p o s i u m o n M o b i l e A d H o c N e t w o r k i n g & C o m p u t i n g(M o b i H o c’0 1). L o n gB e a c h,U S A,2 0 0 1:1 3 7  1 4 5099计  算  机  学  报2 0 1 6年 [5 8]C h e nL,L iY,C h e n Y,e ta l .P r i m es e t  b a s e dn e i g h b o rd i s c o v e r y a l g o r i t h m f o rl o w d u t y  c y c l e d y n a m i c WS N s .E l e c t r o n i c sL e t t e r s,2 0 1 5,5 1(6) :5 3 4  5 3 6[5 9]P u r o h i t A,P r i y a n t h a B,L i u J . W i F l o c k:C o l l a b o r a t i v eg r o u pd i s c o v e r ya n dm a i n t e n a n c ei nm o b i l es e n s o rn e t w o r k s/ /P r o c e e d i n g so f t h e1 0 t hI n t e r n a t i o n a lC o n f e r e n c eo nI n f o r m a t i o nP r o c e s s i n g i nS e n s o rN e t w o r k s(I P S N’1 1). C h i c a g o,U S A,2 0 1 1:3 7  4 8[6 0]C o h e n R,K a p c h i t s B.C o n t i n u o u sn e i g h b o rd i s c o v e r yi na s y n c h r o n o u ss e n s o rn e t w o r k s . I E E E/A CM T r a n s a c t i o n so nN e t w o r k i n g,2 0 1 1,1 9(1) :6 9  7 9[6 1]Z h a n g D,H eT,L i u Y,e ta l .A c c:G e n e r i co n  d e m a n da c c e l e r a t i o n s f o rn e i g h b o rd i s c o v e r yi nm o b i l ea p p l i c a t i o n s/ /P r o c e e d i n g so ft h e 1 0 t h A CM C o n f e r e n c e o n E m b e d d e dN e t w o r kS e n s o rS y s t e m s(S e n S y s’1 2).T o r o n t o,C a n a d a,2 0 1 2:1 6 9  1 8 2[6 2]H u a n gT,C h e nH,C u i L,e t a l . E a s i N D:N e i g h b o r d i s c o v e r yi n d u t y  c y c l e d a s y n c h r o n o u s m u l t i c h a n n e l m o b i l e WS N s .I n t e r n a t i o n a l J o u r n a l o fD i s t r i b u t e dS e n s o rN e t w o r k s,2 0 1 3,2 0 1 3(4 0 3 1 6 5)[6 3]L i uJ,C h e n C,M a Y. M o d e l i n g n e i g h b o rd i s c o v e r yi nb l u e t o o t h l o w e n e r g y n e t w o r k s .I E E E C o mm u n i c a t i o n sL e t t e r s,2 0 1 2,1 6(9) :1 4 3 9  1 4 4 1[6 4]R o s e nK.D i s c r e t e M a t h e m a t i c sa n dI t s A p p l i c a t i o n s .7 t hE d i t i o n . C o l u m b u s,U S A:M c G r a w  H i l lE d u c a t i o n,2 0 1 1[6 5]S u nW,Y a n gZ,Z h a n gX,e ta l .E n e r g ye f f i c i e n tn e i g h b o rd i s c o v e r y i nm o b i l ea dh o ca n dw i r e l e s ss e n s o rn e t w o r k s:As u r v e y .I E E E C o mm u n i c a t i o n s S u r v e y s T u t o r i a l s,2 0 1 4,1 6(3) :1 4 4 8  1 4 5 9[6 6]G a r c i a  M o l i n a H,B a r b a r a D.H o w t oa s s i g nv o t e si nad i s t r i b u t e ds y s t e m.J o u r n a lo ft h e A CM,1 9 8 5,3 2(4) :8 4 1  8 6 0[6 7]A g r a w a lD,A b b a d iA E.A ne f f i c i e n ta n df a u l tt o l e r a n ts o l u t i o nf o rd i s t r i b u t e dm u t u a l e x c l u s i o n . A CM T r a n s a c t i o n so nC o m p u t e rS y s t e m s,1 9 9 1,9(1) :1  2 0[6 8]K u m a rA.H i e r a r c h i c a l q u o r u mc o n s e n s u s:An e wa l g o r i t h mf o rm a n a g i n g r e p l i c a t e dd a t a . I E E ET r a n s a c t i o n so nC o m p u t e r s,1 9 9 1,4 0(9) :9 9 6  1 0 0 4[6 9]W a n g K,M a o X,L i u Y u n h a o .B l i n d D a t e:A n e i g h b o rd i s c o v e r yp r o t o c o l/ /P r o c e e d i n g so ft h e4 2 n dI n t e r n a t i o n a lC o n f e r e n c eo nP a r a l l e l P r o c e s s i n g(I C P P’1 3). L y o n,F r a n c e,2 0 1 3:1 2 0  1 2 9[7 0]J i a n gJ,T s e n gY,H s uC,e t a l . Q u o r u m  b a s e da s y n c h r o n o u sp o w e r  s a v i n gp r o t o c o l sf o rI E E E8 0 2 . 1 1a dh o cn e t w o r k s/ /P r o c e e d i n g so f t h e2 0 0 3I n t e r n a t i o n a lC o n f e r e n c eo nP a r a l l e lP r o c e s s i n g(I C P P’0 3).K a o h s i u n g,T a i w a n,C h i n a,2 0 0 3:2 5 7  2 6 4[7 1]J i a n gJ,T s e n gY,H s uC,e t a l . Q u o r u m  b a s e da s y n c h r o n o u sp o w e r  s a v i n gp r o t o c o l sf o rI E E E8 0 2 . 1 1a dh o cn e t w o r k s .M o b i l eN e t w o r k sa n dA p p l i c a t i o n s,2 0 0 5,1 0(1  2) :1 6 9  1 8 1[7 2]A n d e r s o n I . C o m b i n a t o r i a lD e s i g n s a n dT o u r n a m e n t s . L o n d o n,UK:O x f o r dU n i v e r s i t yP r e s s,1 9 9 7[7 3]N i v e nI,Z u c k e r m a nHS,M o n t g o m e r yHL.A n i n t r o d u c t i o nt ot h et h e o r yo fn u m b e r s .H o b o k e n,U S A:J o h n W i l e y &S o n s,2 0 0 8[7 4]C h a oC,S h e uJ,C h o uI .A na d a p t i v eq u o r u m  b a s e de n e r g yc o n s e r v i n gp r o t o c o l f o r I E E E8 0 2 . 1 1a dh o cn e t w o r k s . I E E ET r a n s a c t i o n so nM o b i l eC o m p u t i n g,2 0 0 6,5(5) :5 6 0  5 7 0[7 5]L a iS,R a v i n d r a nB,C h o H.H e t e r o g e n o u sq u o r u m  b a s e dw a k eu p s c h e d u l i n g i n w i r e l e s s s e n s o r n e t w o r k s .I E E ET r a n s a c t i o n so nC o m p u t e r s,2 0 1 0,5 9(1 1) :1 5 6 2  1 5 7 5[7 6]L a i S,Z h a n gB,R a v i n d r a nB,e t a l . C Q Sp a i r:C y c l i cq u o r u ms y s t e mp a i r f o rw a k e u ps c h e d u l i n g i nw i r e l e s ss e n s o rn e t w o r k s/ /B a k e rTP,B u iA,T i x e u i l Se d s . P r i n c i p l e so fD i s t r i b u t e dS y s t e m s .L e c t u r eN o t e si nC o m p u t e rS c i e n c e5 4 0 1.2 0 0 8:2 9 5  3 1 0[7 7]B o r b a s hSA,E p h r e m i d e sA,M c G l y n nMJ . A na s y n c h r o n o u sn e i g h b o rd i s c o v e r ya l g o r i t h mf o rw i r e l e s ss e n s o rn e t w o r k s .A dH o cN e t w o r k s,2 0 0 7,5(7) :9 9 8  1 0 1 6[7 8]K h a l i l iR,G o e c k e l DL,T o w s l e yD,e t a l . N e i g h b o r d i s c o v e r yw i t hr e c e p t i o ns t a t u sf e e d b a c kt ot r a n s m i t t e r s/ /P r o c e e d i n g so f t h e2 9 t h A n n u a lJ o i n tC o n f e r e n c eo ft h eC o m p u t e ra n dC o mm u n i c a t i o n sS o c i e t i e s(I N F O C OM’1 0). S a nD i e g o,U S A,2 0 1 0:1  9[7 9]K n u t hD E.T h e A r to fC o m p u t e rP r o g r a mm i n g V o l . 3:S o r t i n g a n d S e a r c h i n g . B o s t o n,U S A:A d d i s o n  W e s l e yS e r i e s i nC o m p u t e rS c i e n c e,1 9 7 3[8 0]F a n gS,B e r b e rS M,S w a i n A K.A n a l y s i so fn e i g h b o rd i s c o v e r yp r o t o c o l sf o re n e r g y d i s t r i b u t i o n e s t i m a t i o n si nw i r e l e s ss e n s o rn e t w o r k s/ /P r o c e e d i n g so ft h e2 0 0 8I E E EI n t e r n a t i o n a lC o n f e r e n c eo nC o mm u n i c a t i o n s(I C C’0 8). B e i j i n g,C h i n a,2 0 0 8:4 3 8 6  4 3 9 0[8 1]V a z q u e z  G a l l e g o F,A l o n s o  Z a r a t e J,A l o n s o L,e t a l .A n a l y s i so fe n e r g ye f f i c i e n td i s t r i b u t e dn e i g h b o u rd i s c o v e r ym e c h a n i s m s f o r m a c h i n et o  m a c h i n e n e t w o r k s . A d H o cN e t w o r k s,2 0 1 4,1 8:4 0  5 4[8 2]C h e nL,G uY,G u oS,H eT,e ta l . G r o u p  b a s e dd i s c o v e r yi nl o w  d u t y c y c l em o b i l es e n s o rn e t w o r k s/ /P r o c e e d i n g so f t h e9 t hA n n u a lC o mm u n i c a t i o n sS o c i e t yo nS e n s o ra n dA dH o cC o mm u n i c a t i o n sa n dN e t w o r k s(S E C ON’1 2). S e o u l,K o r e a,2 0 1 2:5 4 2  5 5 0[8 3]C h e nL,G u oS,S h uY,e t a l . S e l e c t i v e r e f e r e n c em e c h a n i s mf o rn e i g h b o r d i s c o v e r yi n l o w  d u t y  c y c l e w i r e l e s s s e n s o rn e t w o r k s/ /P r o c e e d i n g s o f t h e 9 t h A CM C o n f e r e n c e o nE m b e d d e dN e t w o r k e dS e n s o rS y s t e m s(S e n S y s’1 1). S e a t t l e,U S A,2 0 1 1:3 6 7  3 6 8[8 4]Z h a n gD,H eT,Y eF,e ta l . E Q S:N e i g h b o rd i s c o v e r ya n dr e n d e z v o u sm a i n t e n a n c e w i t he x t e n d e dq u o r u m s y s t e m f o rm o b i l es e n s i n ga p p l i c a t i o n s/ /P r o c e e d i n g so ft h e2 0 1 2I E E E3 2 n d I n t e r n a t i o n a l C o n f e r e n c e o n D i s t r i b u t e d C o m p u t i n gS y s t e m s(I C D C S’1 2).M a c a u,C h i n a,2 0 1 2:7 2  8 1[8 5]S r i n i v a s a nK,D u t t aP,T a v a k o l iA,e ta l .A ne m p i r i c a ls t u d yo fl o w  p o w e rw i r e l e s s .A CM T r a n s a c t i o n so nS e n s o rN e t w o r k s,2 0 1 0,6(2) :1 6:1  1 6:4 91995期裘莹等:传感器网络邻居发现协议综述 [8 6]G u t i e r r e zJA,C a l l a w a yE H,B a r r e t tR. I E E E8 0 2 . 1 5 . 4L o w  R a t eW i r e l e s sP e r s o n a lA r e aN e t w o r k s:E n a b l i n gW i r e l e s sS e n s o rN e t w o r k s .U S A,I E E ES t a n d a r d sO f f i c e,2 0 0 3[8 7]K a r o w s k iN,V i a n aAC,W o l i s zA. O p t i m i z e da s y n c h r o n o u sm u l t i  c h a n n e ln e i g h b o rd i s c o v e r y/ /P r o c e e d i n g so ft h e3 0 t hI E E EI n t e r n a t i o n a lC o n f e r e n c eo nC o m p u t e rC o mm u n i c a t i o n s(I N F O C OM’1 1). S h a n g h a i,C h i n a,2 0 1 1:5 3 6  5 4 0[8 8]G a r c í a  O t e r o M,P o b l a c i ó n  H e r n  n d e zA.S e c u r en e i g h b o rd i s c o v e r y i nw i r e l e s s s e n s o rn e t w o r k su s i n gr a n g ef r e e l o c a l i z a t i o nt e c h n i q u e s . I n t e r n a t i o n a l J o u r n a l o fD i s t r i b u t e dS e n s o rN e t w o r k s,2 0 1 2,2 0 1 2(7 6 3 1 8 7) :1  1 2[8 9]S t o l e r uR,Wu H,C h e n j iH. S e c u r en e i g h b o rd i s c o v e r yi nm o b i l ea dh o cn e t w o r k s/ /P r o c e e d i n g so f t h e8 t hI E E EI n t e r n a t i o n a lC o n f e r e n c eo n M o b i l e A d h o ca n dS e n s o rS y s t e m s(MA S S’1 1).V a l e n c i a,S p a i n,2 0 1 1:3 5  4 2[9 0]H u i JW,C u l l e rDE. I Pi sd e a d,l o n gl i v eI Pf o rw i r e l e s ss e n s o r n e t w o r k s/ /P r o c e e d i n g s o f t h e 6 t hA CMC o n f e r e n c e o nE m b e d d e dN e t w o r kS e n s o rS y s t e m s(S e n S y s’0 8).R a l e i g h,U S A,2 0 0 8:1 5  2 8[9 1]H u i JW,C u l l e rDE. I p v 6 i n l o w  p o w e rw i r e l e s sn e t w o r k s .P r o c e e d i n g so f t h e I E E E,2 0 1 0,9 8(1 1) :1 8 6 5  1 8 7 8犙 犐 犝 犢 犻 狀 犵,b o r ni n1 9 8 7,P h . D.c a n d i d a t e .H i s r e s e a r c h i n t e r e s t s i n c l u d en e t w o r k p r o t o c o l s d e s i g n f o r w i r e l e s ss e n s o rn e t w o r k s .犔 犐 犛 犺 犻  犖 犻 狀 犵,b o r n i n1 9 6 7,p r o f e s s o r,P h . D. s u p e r v i s o r .H i sr e s e a r c hi n t e r e s t si n c l u d ew i r e l e s ss e n s o rn e t w o r k sa n dm o b i l ec o m p u t i n g .犡 犝 犡 犻 犪 狀 犵  犛 犲 狀,b o r ni n1 9 9 1,M. S.c a n d i d a t e .H i sr e s e a r c h i n t e r e s t s f o c u so nw i r e l e s ss e n s o rn e t w o r k s .犔 犐犣 犺 犻  犌 犪 狀 犵,b o r n i n1 9 7 5,P h . D.,a s s o c i a t ep r o f e s s o r .H i s r e s e a r c h i n t e r e s t s i n c l u d en e t w o r k e de m b e d d e dc o m p u t i n g,s e n s o rn e t w o r k sa n dm o b i l ec o m p u t i n g .犅 犪 犮 犽 犵 狉 狅 狌 狀 犱S e n s o rn e t w o r k i s t h em o s tp o t e n t i a l t e c h n o l o g yf o r l o wp o w e rw i r e l e s sn e t w o r k st of u l f i l lI n t e r n e to fT h i n g s . I ti sw i d e l yu s e df o rr e m o t ee n v i r o n m e n t a lm o n i t o r i n ga n dt a r g e tt r a c k i n gw i t ht i n yw i r e l e s ss e n s o r ss a m p l i n gv a r i o u sp h y s i c a lp h e n o m e n a. S e n s o r s a r e e q u i p p e dw i t hw i r e l e s s r a d i o t o c o m m u n i c a t ew i t he a c ho t h e ra n df o r mn e t w o r k ss p o n t a n e o u s l y .T h e f i r s t s t e p i nt h ep r o g r e s s i s t o f i n dn e i g h b o r s i no n eh o pc o mm u n i c a t i o nr a n g e,w h i c hi sd o n eb yn e i g h b o rd i s c o v e r yp r o t o c o l s s u r v e y e d i n t h i sp a p e r . A c c u r a t en e i g h b o r i n f o r m a t i o ng r e a t l y i m p r o v e s t h ep e r f o r m a n c eo f u p p e rp r o t o c o l s,s u c ha sMA Cp r o t o c o l a n dr o u t i n gp r o t o c o l .O nr e s o u r c ec o n s t r a i n e da n db a t t e r y  p o w e r e ds e n s o r s,r a p i dn e i g h b o rd i s c o v e r y i saf a c t o r t h a t c o n f l i c t sw i t he n e r g y e f f i c i e n c y . T h ea r to fn e i g h b o r sd i s c o v e r yp r o t o c o ld e s i g ni st ob a l a n c ee n e r g yc o n s u m p t i o na n dd i s c o v e rd e l a y .R e l a t e dr e s e a r c h e sm e n t i o n e di nt h i sp a p e rm a k eg r e a tp r o g r e s si ne i t h e rp u s h i n gt h eb o u n d a r yo ft h e o r e t i c a lp e r f o r m a n c eo rp r o p o s ep r a c t i c a lp r o t o t y p e s .T h i sw o r k i s s u p p o r t e db y t h eN a t i o n a lK e yT e c h n o l o g i e sR e s e a r c ha n d D e v e l o p m e n tP r o g r a m o fC h i n au n d e rG r a n tN o . 2 0 1 4 B AH 1 4 F 0 1,t h eN a t i o n a lS c i e n c ea n d T e c h n o l o g yM a j o rP r o j e c to fC h i n au n d e rG r a n tN o . 2 0 1 2 Z X 0 3 0 0 5 0 0 7.T h e s ep r o j e c t sa i m t o u n c o v e rt h e k e yt e c h n o l o g i e sa n dp r i n c i p l e so f s e n s o rn e t w o r k s i np r a c t i c e . T h e s u b j e c t d i s c u s s e di nt h i sp a p e ri so n eo ft h em o s t i m p o r t a n tp a r t st h a tr e v e a lt h e f u n d a m e n t a l p r i n c i p l e s i ns e n s o rn e t w o r k sa n d I n t e r n e t o fT h i n g s .299计  算  机  学  报2 0 1 6年 。

      点击阅读更多内容
      关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
      手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
      ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.