停留交会应用中减少邻居发现延迟

靳帅召; 王子潇; 董亚波; 鲁东明

doi:10.1631/FITEE.1800412

Your Location：

Home >

Browse articles >

停留交会应用中减少邻居发现延迟

常规文章 | Updated：2022-05-19

- 停留交会应用中减少邻居发现延迟
- Reducing neighbor discovery latency in docking applications
- 信息与电子工程前沿（英文） 2019年20卷第8期页码：1147-1164
- Affiliations：
  
  College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China
  Department of Computer Science, National University of Singapore, Singapore 119077, Singapore
- Author bio：
  
  Shuai-zhao JIN, E-mail: jinszhao@zju.edu.cn
- Funds：
  
  Project supported by the National High-Tech R & D Program of China (No. 2012AA101701), the National Key Technology Support Program of China (Nos. 2013BAK01B00 and 2014BAK16B00), and Grotto Temples Digital Protection of Cultural Relics and Equipment Upgrading of National Cultural Heritage Administration Scientific Research Institutes
- DOI：10.1631/FITEE.1800412
  中图分类号： TN929.5
- 收稿：2018-07-02，
  
  修回：2019-;8-15，
  
  纸质出版：2019-08
- Accepted：
Scan QR Code
靳帅召, 王子潇, 董亚波, 等. 停留交会应用中减少邻居发现延迟[J]. 信息与电子工程前沿（英文）, 2019,20(8):1147-1164.

Shuai-zhao JIN, Zi-xiao WANG, Ya-bo DONG, et al. Reducing neighbor discovery latency in docking applications[J]. Frontiers of Information Technology & Electronic Engineering, 2019, 20(8): 1147-1164.
靳帅召, 王子潇, 董亚波, 等. 停留交会应用中减少邻居发现延迟[J]. 信息与电子工程前沿（英文）, 2019,20(8):1147-1164. DOI： 10.1631/FITEE.1800412.

Shuai-zhao JIN, Zi-xiao WANG, Ya-bo DONG, et al. Reducing neighbor discovery latency in docking applications[J]. Frontiers of Information Technology & Electronic Engineering, 2019, 20(8): 1147-1164. DOI： 10.1631/FITEE.1800412.

摘要

邻居发现在停留交会应用中十分重要。在停留交会应用中移动传感器节点与部署在不同交会点的固定传感器节点进行通信。在现有邻居发现协议中，概率性邻居发现协议在一般情况下表现良好，但存在非周期性、不可预测性和无限发现延迟。确定性邻居发现协议可牺牲平均邻居发现性能以提供最差情况下的邻居发现延迟。本文提出一种基于移动信息辅助的时槽同步技术，通过时槽同步提升确定性邻居发现协议的平均性能，同时不增加额外传感器节点能量开销。针对邻居发现中的信标帧冲突可能导致的邻居发现失败情况，提出一种优化的信标帧发送策略。通过理论分析和基于莫高窟游客追踪系统积累的实际数据，验证该基于移动信息辅助时槽同步技术的性能。实验结果表明，所提时槽同步技术最高可将目前最优的确定性邻居发现协议平均性能提升两个数量级。

Abstract

Neighbor discovery is important for docking applications

where mobile nodes communicate with static nodes situated at various rendezvous points. Among the existing neighbor discovery protocols

the probabilistic methods perform well in average cases but they have aperiodic

unpredictable

and unbounded discovery latency. Yet

deterministic protocols can provide bounded worst-case discovery latency by sacrificing the average-case performance. In this study

we propose a mobility-assisted slot index synchronization (MASS)

which is a new synchronization technique that can improve the average-case performance of deterministic neighbor discovery protocols via slot index synchronization without incurring additional energy consumption. Furthermore

we propose an optimized beacon strategy in MASS to mitigate beaconing collisions

which can lead to discovery failures in situations where multiple neighbors are in the vicinity. We evaluate MASS with theoretical analysis and simulations using real traces from a tourist tracking system deployed at the Mogao Grottoes

which is a famous cultural heritage site in China. We show that MASS can reduce the average discovery latency of state-of-the-art deterministic neighbor discovery protocols by up to two orders of magnitude.

关键词

Keywords

references

M Bakht , , , M Trower , , , RH Kravets . . Searchlight: won't you be my neighbor? . . Proc 18 th Annual Int Conf on Mobile Computing and Networking , , 2012 . . p.185 - - 196 . . DOI: 10.1145/2348543.2348568 http://doi.org/10.1145/2348543.2348568 . .

BJ Choi , , , H Liang , , , XM Shen , , , 等 . . DCS: distributed asynchronous clock synchronization in delay tolerant networks . . IEEE Trans Parall Distrib Syst , , 2012 . . 23 ( ( 3 ): ): 491 - - 504 . . DOI: 10.1109/TPDS.2011.179 http://doi.org/10.1109/TPDS.2011.179 . .

P Dutta , , , D Culler . . Practical asynchronous neighbor discovery and rendezvous for mobile sensing applications . . Proc 6 th ACM Conf on Embedded Network Sensor Systems , , 2008 . . p.71 - - 84 . . DOI: 10.1145/1460412.1460420 http://doi.org/10.1145/1460412.1460420 . .

J Elson , , , L Girod , , , D Estrin . . Fine-grained network time synchronization using reference broadcasts . . ACM SIGOPS Oper Syst Rev , , 2002 . . 36 ( ( SI ): ): 147 - - 163 . . DOI: 10.1145/844128.844143 http://doi.org/10.1145/844128.844143 . .

F Ferrari , , , M Zimmerling , , , L Thiele , , , 等 . . Efficient network flooding and time synchronization with glossy . . Proc 10 th ACM/IEEE Int Conf on Information Processing in Sensor Networks , , 2011 . . p.73 - - 84 . . . .

S Ganeriwal , , , R Kumar , , , MB Srivastava . . Timing-sync protocol for sensor networks . . Proc 1 st Int Conf on Embedded Networked Sensor Systems , , 2003 . . p.138 - - 149 . . DOI: 10.1145/958491.958508 http://doi.org/10.1145/958491.958508 . .

BR Hamilton , , , X Ma , , , Q Zhao , , , 等 . . ACES: adaptive clock estimation and synchronization using Kalman filtering . . Proc 14 th ACM Int Conf on Mobile Computing and Networking , , 2008 . . p.152 - - 162 . . DOI: 10.1145/1409944.1409963 http://doi.org/10.1145/1409944.1409963 . .

JP He , , , P Cheng , , , L Shi , , , 等 . . Clock synchronization for random mobile sensor networks . . Proc 51 st IEEE Conf on Decision and Control , , 2012 . . p.2712 - - 2717 . . DOI: 10.1109/CDC.2012.6426053 http://doi.org/10.1109/CDC.2012.6426053 . .

H Huang , , , J Yun , , , ZG Zhong , , , 等 . . PSR: practical synchronous rendezvous in low-duty-cycle wireless networks . . Proc IEEE INFOCOM , , 2013 . . p.2661 - - 2669 . . DOI: 10.1109/INFCOM.2013.6567074 http://doi.org/10.1109/INFCOM.2013.6567074 . .

JH Huang , , , S Amjad , , , S Mishra . . CenWits: a sensorbased loosely coupled search and rescue system using witnesses . . Proc 3 rd Int Conf on Embedded Networked Sensor Systems , , 2005 . . p.180 - - 191 . . DOI: 10.1145/1098918.1098938 http://doi.org/10.1145/1098918.1098938 . .

SZ Jin , , , ZX Wang , , , WK Leong , , , 等 . . Improving neighbor discovery with slot index synchronization . . IEEE 12 th Int Conf on Mobile Ad Hoc and Sensor Systems , , 2015 . . p.253 - - 261 . . DOI: 10.1109/MASS.2015.14 http://doi.org/10.1109/MASS.2015.14 . .

A Kandhalu , , , K Lakshmanan , , , RR Rajkumar . . UConnect: a low-latency energy-efficient asynchronous neighbor discovery protocol . . Proc 9 th ACM/IEEE Int Conf on Information Processing in Sensor Networks , , 2010 . . p.350 - - 361 . . DOI: 10.1145/1791212.1791253 http://doi.org/10.1145/1791212.1791253 . .

SW Lai , , , B Ravindran , , , H Cho . . Heterogenous quorumbased wake-up scheduling in wireless sensor networks . . IEEE Trans Comput , , 2010 . . 59 ( ( 11 ): ): 1562 - - 1575 . . DOI: 10.1109/TC.2010.20 http://doi.org/10.1109/TC.2010.20 . .

M Li . . Bodhisattva's crown of the early-Tang period in the Dunhuang art of Mogao Grottoes . . Dunhuang Res , , 2004 . . 2004 ( ( 6 ): ): 42 - - 50 . . DOI: 10.3969/j.issn.1000-4106.2004.06.008 http://doi.org/10.3969/j.issn.1000-4106.2004.06.008 . .

Q Li , , , D Rus . . Global clock synchronization in sensor networks . . IEEE Trans Comput , , 2006 . . 55 ( ( 2 ): ): 214 - - 226 . . DOI: 10.1109/TC.2006.25 http://doi.org/10.1109/TC.2006.25 . .

CD Liao , , , P Barooah . . Distributed clock skew and offset estimation from relative measurements in mobile networks with Markovian switching topology . . Automatica , , 2013 . . 49 ( ( 10 ): ): 3015 - - 3022 . . DOI: 10.1016/j.automatica.2013.07.015 http://doi.org/10.1016/j.automatica.2013.07.015 . .

M Malinowski , , , M Moskwa , , , M Feldmeier , , , 等 . . CargoNet: a low-cost micropower sensor node exploiting quasi-passive wakeup for adaptive asychronous monitoring of exceptional events . . Proc 5 th Int Conf on Embedded Networked Sensor Systems , , 2007 . . p.145 - - 159 . . DOI: 10.1145/1322263.1322278 http://doi.org/10.1145/1322263.1322278 . .

M Marti , , , B Kusy , , , G Simon , , , 等 . . The flooding time synchronization protocol . . Proc 2 nd Int Conf on Embedded Networked Sensor Systems , , 2004 . . p.39 - - 49 . . DOI: 10.1145/1031495.1031501 http://doi.org/10.1145/1031495.1031501 . .

MJ McGlynn , , , SA Borbash . . Birthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks . . Proc 2 nd ACM Int Symp on Mobile Ad Hoc Networking & Computing , , 2001 . . p.137 - - 145 . . DOI: 10.1145/501431.501435 http://doi.org/10.1145/501431.501435 . .

I Niven , , , HS Zuckerman , , , HL Montgomery . . An Introduction to the Theory of Numbers , , (5 th Ed.) : : New York John Wiley & Sons , , 1980 . . .

A Purohit , , , B Priyantha , , , J Liu . . WiFlock: collaborative group discovery and maintenance in mobile sensor networks . . Proc 10 th ACM/IEEE Int Conf on Information Processing in Sensor Networks , , 2011 . . p.37 - - 48 . . . .

Y Qiu , , , SN Li , , , XS Xu , , , 等 . . Talk more listen less: energy-efficient neighbor discovery in wireless sensor networks . . Proc 35 th Annual IEEE Int Conf on Computer Communications , , 2016 . . p.1 - - 9 . . DOI: 10.1109/INFOCOM.2016.7524336 http://doi.org/10.1109/INFOCOM.2016.7524336 . .

T Schmid , , , Z Charbiwala , , , R Shea , , , 等 . . Temperature compensated time synchronization . . IEEE Embedd Syst Lett , , 2009 . . 1 ( ( 2 ): ): 37 - - 41 . . DOI: 10.1109/LES.2009.2028103 http://doi.org/10.1109/LES.2009.2028103 . .

JP Sheu , , , CM Chao , , , CW Sun . . A clock synchronization algorithm for multi-hop wireless ad hoc networks . . Proc 24 th Int Conf on Distributed Computing Systems , , 2004 . . p.574 - - 581 . . DOI: 10.1109/icdcs.2004.1281624 http://doi.org/10.1109/icdcs.2004.1281624 . .

P Sommer , , , R Wattenhofer . . Gradient clock synchronization in wireless sensor networks . . Proc Int Conf on Information Processing in Sensor Networks , , 2009 . . p.37 - - 48 . . . .

W Su , , , IF Akyildiz . . Time-diffusion synchronization protocol for wireless sensor networks . . IEEE/ACM Trans Netw , , 2005 . . 13 ( ( 2 ): ): 384 - - 397 . . DOI: 10.1109/TNET.2004.842228 http://doi.org/10.1109/TNET.2004.842228 . .

W Sun , , , Z Yang , , , XL Zhang , , , 等 . . Energy-efficient neighbor discovery in mobile ad hoc and wireless sensor networks: a survey . . IEEE Commun Surv Tutor , , 2014a . . 16 ( ( 3 ): ): 1448 - - 1459 . . DOI: 10.1109/SURV.2013.012414.00164 http://doi.org/10.1109/SURV.2013.012414.00164 . .

W Sun , , , Z Yang , , , KY Wang , , , 等 . . Hello: a generic flexible protocol for neighbor discovery . . Proc IEEE Conf on Computer Communications , , 2014b . . p.540 - - 548 . . DOI: 10.1109/INFOCOM.2014.6847978 http://doi.org/10.1109/INFOCOM.2014.6847978 . .

SW Tseng . . The paradox between conservation and development: can cultural relics of the Dunhuang Mogao Grottoes be preserved through cultural creativity and digital technologies . . Appl Sci Manag Res , , 2015 . . 2 ( ( 1 ): ): 39 - - 47 . . . .

YC Tseng , , , CS Hsu , , , TY Hsieh . . Power-saving protocols for IEEE 802.11-based multi-hop ad hoc networks . . Comput Netw , , 2003 . . 43 ( ( 3 ): ): 317 - - 337 . . DOI: 10.1016/S1389-1286(03)00284-6 http://doi.org/10.1016/S1389-1286(03)00284-6 . .

KY Wang , , , XF Mao , , , YH Liu . . BlindDate: a neighbor discovery protocol . . Proc 42 nd Int Conf on Parallel Processing , , 2013 . . p.120 - - 129 . . DOI: 10.1109/ICPP.2013.21 http://doi.org/10.1109/ICPP.2013.21 . .

T Wark , , , W Hu , , , P Sikka , , , 等 . . A model-based routing protocol for a mobile, delay tolerant network . . Proc 5 th Int Conf on Embedded Networked Sensor Systems , , 2007 . . p.421 - - 422 . . DOI: 10.1145/1322263.1322326 http://doi.org/10.1145/1322263.1322326 . .

M Xia , , , YB Dong , , , DM Lu , , , 等 . . A wireless sensor system for long-term microclimate monitoring in wildland cultural heritage sites . . Proc IEEE Int Symp on Parallel and Distributed Processing with Applications , , 2008 . . p.207 - - 214 . . DOI: 10.1109/ISPA.2008.75 http://doi.org/10.1109/ISPA.2008.75 . .

M Xu , , , WY Xu . . TACO: temperature-aware compensation for time synchronization in wireless sensor networks . . Proc IEEE 10 th Int Conf on Mobile Ad-Hoc and Sensor Systems , , 2013 . . p.122 - - 130 . . DOI: 10.1109/MASS.2013.52 http://doi.org/10.1109/MASS.2013.52 . .

Z Yang , , , J Pan , , , L Cai . . Adaptive clock skew estimation with interactive multi-model Kalman filters for sensor networks . . Proc IEEE Int Conf on Communications , , 2010 . . p.1 - - 5 . . DOI: 10.1109/ICC.2010.5502549 http://doi.org/10.1109/ICC.2010.5502549 . .

Q Ye , , , L Cheng . . DTP: double-pairwise time protocol for disruption tolerant networks . . Proc 28 th Int Conf on Distributed Computing Systems , , 2008 . . p.345 - - 352 . . DOI: 10.1109/ICDCS.2008.73 http://doi.org/10.1109/ICDCS.2008.73 . .

DS Zhang , , , T He , , , YH Liu , , , 等 . . Acc: generic ondemand accelerations for neighbor discovery in mobile applications . . Proc 10 th ACM Conf on Embedded Network Sensor Systems , , 2012 . . p.169 - - 182 . . DOI: 10.1145/2426656.2426674 http://doi.org/10.1145/2426656.2426674 . .

ZG Zhong , , , PP Chen , , , T He . . On-demand time synchronization with predictable accuracy . . Proc IEEE INFOCOM , , 2011 . . p.2480 - - 2488 . . DOI: 10.1109/INFCOM.2011.5935071 http://doi.org/10.1109/INFCOM.2011.5935071 . .

D Zhou , , , TH Lai . . An accurate and scalable clock synchronization protocol for IEEE 802.11-based multihop ad hoc networks . . IEEE Trans Parall Distrib Syst , , 2007 . . 18 ( ( 12 ): ): 1797 - - 1808 . . DOI: 10.1109/TPDS.2007.1116 http://doi.org/10.1109/TPDS.2007.1116 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

Anonymous-address-resolution model