DocumentCode :
2374208
Title :
An efficient differencing algorithm based on suffix array for reprogramming wireless sensor networks
Author :
Mo, Biyuan ; Dong, Wei ; Chen, Chun ; Bu, Jiajun ; Wang, Qiang
Author_Institution :
Zhejiang Provincial Key Lab. of Service Robot, Zhejiang Univ., Hangzhou, China
fYear :
2012
fDate :
10-15 June 2012
Firstpage :
773
Lastpage :
777
Abstract :
Wireless reprogramming is a crucial technique for managing large-scale wireless sensor networks (WSNs). It is, however, energy intensive to disseminate the code to enable reprogramming. Incremental reprogramming is a promising approach to reduce the dissemination cost. In incremental reprogramming, only the delta between the new code and the old code needs to be disseminated, resulting much less energy consumption. The differencing algorithm plays a key role in incremental reprogramming. It takes inputs of two successive versions of codes and generates a small delta script for dissemination. Existing incremental algorithms have several limitations. First, they do not ensure the smallest delta size for dissemination. Second, some of them may incur a large overhead in terms of execution time and memory consumption. To address these issues, we propose DASA, an efficient differencing algorithm based on suffix array. DASA performs byte-level comparison and ensure the optimal result in terms of the delta size. Moreover, DASA has a low execution overhead. The time complexity and space complexity of DASA are O(n log n) and O(n), respectively. To the best of our knowledge, DASA is the optimal algorithm with the lowest time and space complexity for reprogramming WSNs.
Keywords :
computational complexity; telecommunication network management; wireless sensor networks; DASA; WSN management; delta size; dissemination cost; efficient differencing algorithm; energy consumption; incremental reprogramming; large-scale wireless sensor network management; low execution overhead; memory consumption; space complexity; suffix array; time complexity; wireless sensor network reprogramming; Arrays; Indexes; Memory management; Programming; Wireless sensor networks;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Communications (ICC), 2012 IEEE International Conference on
Conference_Location :
Ottawa, ON
ISSN :
1550-3607
Print_ISBN :
978-1-4577-2052-9
Electronic_ISBN :
1550-3607
Type :
conf
DOI :
10.1109/ICC.2012.6364214
Filename :
6364214
Link To Document :
بازگشت