非对称异步移动传感网中低延时邻居发现算法

计算机与现代化 ›› 2022, Vol. 0 ›› Issue (10): 88-94.

非对称异步移动传感网中低延时邻居发现算法

(1.中国石油大学(华东)计算机科学与技术学院，山东青岛266580;2.中国石油大学(华东)海洋与空间信息学院，山东青岛266580)

出版日期:2022-10-20 发布日期:2022-10-21
作者简介:黄庭培(1980—)，女(土家族)，湖北建始人，副教授，硕士生导师，博士，研究方向：物联网，无线传感器网络，移动计算，E-mail: huangtingpei@upc.edu.cn; 通信作者：张亚(1996—)，女，山东临清人，硕士研究生，研究方向：无线传感器网络，邻居发现，E-mail: 867464355@qq.com; 李世宝(1978—)，男，山东潍坊人，副教授，硕士，研究方向：Ad Hoc，移动计算，复杂网络，E-mail: lishibao@upc.edu.cn; 刘建航(1978—)，男，山东潍坊人，副教授，硕士生导师，博士，研究方向：车联网，无线传感器网络，E-mail: liujianhang@upc.edu.cn。
基金资助:
国家自然科学基金资助项目(61872385, 61673396, 61772551, 61801517); 中央高校基本科研业务费专项资金资助项目(18CX02133A, 18CX02134A, 18CX02137A)

Low Latency Neighbor Discovery Algorithm in Asymmetric Asynchronous Mobile Sensor Networks

(1. College of Computer Science and Technology, China University of Petroleum, Qingdao 266580, China;
2. College of Oceanography and Space Informatics, China University of Petroleum, Qingdao 266580, China)

Online:2022-10-20 Published:2022-10-21

摘要/Abstract

摘要： 邻居发现即通过一定的手段快速而有效地去感知与节点能够直接通信的一跳范围内的邻居的问题，是移动传感网（MSN）的重要部分。非对称异步MSN中，已有的算法需要大量的时间和能量去完成相互发现。针对此问题，基于信标与活动时隙分离的邻居发现模型，提出一种适用于异步对称场景的BMCS-A算法，信标在工作周期的不同时隙进行广播以保证邻居发现的确定性。其次，扩展BMCS-A，提出一种持续性广播的BMCS-B算法，节点在第一个子周期内持续性广播信标，接收到该信标的节点将自适应地调整信标的发送时刻以加快邻居发现过程。最后，实现协作式BMCS-B算法，基于已发现邻居的睡眠苏醒调度信息，节点主动发送信标去发现潜在的邻居。仿真实验结果表明，与Searchlight、G-Nihao和Disco相比，协作式BMCS-B将最坏发现时延分别降低了84.62%、85.71%和81.82%。

关键词: 低占空比, 信标消息, 低延时, 主动式邻居发现, 持续性广播

Abstract: Neighbor discovery is an important part of mobile sensor networks, which is to quickly and effectively sense the neighbors in the one hop range that can communicate with nodes directly. In asymmetric asynchronous MSN, the existing neighbor discovery algorithms need a lot of time and energy to complete mutual discovery. To solve this problem, based on the separation model of beacon and active time slot, a BMCS-A algorithm for asynchronous symmetric scene is proposed. The beacon broadcasts in different time slots of the work cycle to ensure the certainty of neighbor discovery. Secondly, BMCS-A is extended and BMCS-B for persistent broadcast is proposed. The node continuously broadcasts the beacon in the first sub cycle, and the node receiving the beacon will adaptively adjust the beacon sending time to speed up the neighbor discovery process. Finally, the cooperative BMCS-B algorithm is implemented. Based on the sleep wake-up scheduling information of the discovered neighbors, the nodes actively send beacons to discover potential neighbors. Simulation results show that, compared with Searchlight, G-Nihao and Disco, collaborative BMCS-B can reduce the worst case discovery delay by 84.62%, 85.71% and 81.82% respectively.

Key words: low duty cycle, beacon message, low latency, proactive neighbor discovery, continuous broadcasting

黄庭培, 张亚, 李世宝, 刘建航. 非对称异步移动传感网中低延时邻居发现算法[J]. 计算机与现代化, 2022, 0(10): 88-94.

HUANG Ting-pei, ZHANG Ya, LI Shi-bao, LIU Jian-hang. Low Latency Neighbor Discovery Algorithm in Asymmetric Asynchronous Mobile Sensor Networks[J]. Computer and Modernization, 2022, 0(10): 88-94.

参考文献

［1］ GUO S T, YANG Y Y, WANG C. DaGCM: A concurrent data uploading framework for mobile data gathering in wireless sensor networks［J］. IEEE Transactions on Mobile Computing, 2016,15(3):610-626.
［2］ SUN W, YANG Z, ZHANG X L, et al. Energy-efficient neighbor discovery in mobile Ad Hoc and wireless sensor networks: A survey［J］. IEEE Communications Surveys & Tutorials, 2014,16(3):1448-1459.
［3］赵太飞,王晶,张杰,等. 蛙人协作中的水下无线光通信邻居发现方法［J］. 光学学报, 2018,38(12):54-61.
［4］王昕羽,张航,孟旭东. 一种使用定向天线的Ad Hoc网络邻居发现算法［J］. 无线电工程, 2014,44(2):9-12.
［5］贺然,张钢,刘春凤,等. 车载网络中基于移动轨迹预测的快速邻居发现算法［J］. 计算机应用研究, 2015,32(9):2737-2741.
［6］ POZZA R, NATI M, GEORGOULAS S, et al. Neighbor discovery for opportunistic networking in Internet of Things scenarios: A survey［J］. IEEE Access, 2015,3:1101-1131.
［7］ CHEN L Y, GU Y, GUO S, et al. Group-based discovery in low-duty-cycle mobile sensor networks［C］// Proceedings of the 2012 9th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON). 2012:542-550.
［8］ YI C, KLIEWER J. Error correction for low power sensors in asynchronous communication［J］. Signal Processing, 2021,182. DOI: 10.1016/j.sigpro.2020.107946.
［9］ COHEN R, KAPCHITS B. Continuous neighbor discovery in asynchronous sensor networks［J］. IEEE/ACM Transactions on Networking, 2011,19(1):69-79.
［10］QIU Y, LI S N, XU X S, et al. Talk more listen less: Energy-efficient neighbor discovery in wireless sensor networks［C］// IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications. 2016. DOI: 10.1109/INFOCOM.2016.7524336.
［11］CHEN H L, LOU W, WANG Z B, et al. On achieving asynchronous energy-efficient neighbor discovery for mobile sensor networks［J］. IEEE Transactions on Emerging Topics in Computing, 2018,6(4):553-565.
［12］梁俊斌,周翔,马方强,等. 移动低占空比传感网中基于多信标消息的低时延邻居发现算法［J］. 通信学报, 2019,40(8):178-188.
［13］张航,李波,闫中江,等. 定向自组织网络中一种基于双令牌的非同步邻居发现协议［J］. 西北工业大学学报, 2021,39(1):62-70.

［14］ZENG W, VASUDEVAN S, CHEN X, et al. Neighbor discovery in wireless networks with multipacket reception［C］// Proceedings of the 12th ACM International Symposium on Mobile Ad Hoc Networking and Computing. 2011. DOI: 10.1145/2107502.2107506.

［15］LUO L Q, CAO Q, HUANG C D, et al. EnviroMic: Towards cooperative storage and retrieval in audio sensor networks［C］// Proceedings of the 27th International Conference on Distributed Computing Systems (ICDCS’07). 2007. DOI: 10.1109/ICDCS.2007.108.
［16］裘莹,李士宁,徐相森,等. 传感器网络邻居发现协议综述［J］. 计算机学报, 2016,39(5):973-992.
［17］NUR F N, SHARMIN S, HABIB M A, et al. Collaborative neighbor discovery in directional wireless sensor networks［C］// TENCON 2016 - 2016 IEEE Region 10 Conference. 2017:1097-1100.
［18］DUTTA P, CULLER D. Practical asynchronous neighbor discovery and rendezvous for mobile sensing applications［C］// Proceedings of the 6th ACM Conference on Embedded Network Sensor Systems. 2008:71-84.
［19］陈良银,颜秉姝,张靖宇,等. 移动低占空比传感网邻居发现算法［J］. 软件学报, 2014,25(6):1352-1368.
［20］KANDHALU A, LAKSHMANAN K, RAJKUMAR R. U-Connect: A low-latency energy-efficient asynchronous neighbor discovery protocol［C］// Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks. 2010:350-361.
［21］梁俊斌,周翔,李陶深. 移动低占空比无线传感网中低能耗的主动邻居发现算法［J］. 通信学报, 2018,39(4):45-55.
［22］CAO Z, GU Z Q, WANG Y X, et al. Panacea: A low-latency, energy-efficient neighbor discovery protocol for wireless sensor networks［C］// Proceedings of the 2018 IEEE Wireless Communications and Networking Conference (WCNC). 2018. DOI: 10.1109/WCNC.2018.8377089.
［23］夏江涛,孙冬娇. Matlab在现代通信原理课程中的应用［J］. 实验技术与管理, 2014,31(1):110-113.
［24］钱月. 基于Matlab的图像形态学处理技术与应用［J］. 内江师范学院学报, 2019,34(10):51-55.
［25］HOU T C, HUANG K C. Accurate analysis on bluetooth low energy neighbor discovery［J］. Journal of Computer and Communications, 2020,8(12):231-250.
［26］CHEN H L, QIN Y T, LIN K, et al. PWEND: Proactive wakeup based energy-efficient neighbor discovery for mobile sensor networks［J］. Ad Hoc Networks, 2020,107. DOI: 10.1016/j.adhoc.2020.102247.
［27］KINDT P H, YUNGE D, REINERTH G, et al. Griassdi: Mutually assisted slotless neighbor discovery［C］// Proceedings of the 16th ACM/IEEE International Conference on Information Processing in Sensor Networks. 2017:93-104.
［28］BAKHT M, KRAVETS R. MobiCom 2010 Poster: Searchlight: Asynchronous neighbor discovery using systematic probing［J］. Mobile Computing and Communications Review, 2010,14(4):31-33.