Maintaining coverage by progressive crystal-lattice permutation in mobile wireless sensor networks

Pang Chieh Wang, Ting-Wei Hou, Ruei Hong Yan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Citations (Scopus)

Abstract

A new distributed algorithm, called Crystal-Lattice Permutation (CLP) algorithm, is devised to approach the coverage problem in wireless sensor networks. AU nodes are assumed as mobile and run the same CLP algorithm in . An initial seed triggers six neighboring nodes to move to hexagon permutation positions, which is like the Crystal-Lattice formation process in nature. These chosen nodes then become new seeds to trigger other neighboring nodes. By such a progressive process, with initial and boundary conditions, the coverage is achieved. Comparing to the Virtual Force algorithm (VFA), the CLP algorithm needs fewer nodes and takes shorter average moving distance to achieve 100% coverage in random deployment. In simulation, the CLP algorithm deployed at least 60 nodes to achieve the 100% coverage, while the VFA algorithm required more than 100 nodes, under the same assumptions. The average moving distance for each CLP node was less than a half of the VFA node. In addition, as there are n mobile nodes, the number of CLP messages is proportional to n, while VFA is proportional to n2. The CLP algorithm is robust in fault tolerance when some nodes are error in distribution.

Original languageEnglish
Title of host publicationSecond International Conference on Systems and Networks Communications, ICSNC 2006
DOIs
Publication statusPublished - 2006 Dec 1
Event2nd International Conference on Systems and Networks Communications, ICSNC 2006 - Papeete, French Polynesia
Duration: 2006 Oct 282006 Nov 2

Publication series

NameSecond International Conference on Systems and Networks Communications, ICSNC 2006

Other

Other2nd International Conference on Systems and Networks Communications, ICSNC 2006
CountryFrench Polynesia
CityPapeete
Period06-10-2806-11-02

Fingerprint

Crystal lattices
Wireless sensor networks
Fault tolerance
Parallel algorithms
Seed
Boundary conditions

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Computer Science Applications
  • Electrical and Electronic Engineering

Cite this

Wang, P. C., Hou, T-W., & Yan, R. H. (2006). Maintaining coverage by progressive crystal-lattice permutation in mobile wireless sensor networks. In Second International Conference on Systems and Networks Communications, ICSNC 2006 [4041557] (Second International Conference on Systems and Networks Communications, ICSNC 2006). https://doi.org/10.1109/ICSNC.2006.53
Wang, Pang Chieh ; Hou, Ting-Wei ; Yan, Ruei Hong. / Maintaining coverage by progressive crystal-lattice permutation in mobile wireless sensor networks. Second International Conference on Systems and Networks Communications, ICSNC 2006. 2006. (Second International Conference on Systems and Networks Communications, ICSNC 2006).
@inproceedings{f50eae42932a43a495fbf6ca6fa78056,
title = "Maintaining coverage by progressive crystal-lattice permutation in mobile wireless sensor networks",
abstract = "A new distributed algorithm, called Crystal-Lattice Permutation (CLP) algorithm, is devised to approach the coverage problem in wireless sensor networks. AU nodes are assumed as mobile and run the same CLP algorithm in . An initial seed triggers six neighboring nodes to move to hexagon permutation positions, which is like the Crystal-Lattice formation process in nature. These chosen nodes then become new seeds to trigger other neighboring nodes. By such a progressive process, with initial and boundary conditions, the coverage is achieved. Comparing to the Virtual Force algorithm (VFA), the CLP algorithm needs fewer nodes and takes shorter average moving distance to achieve 100{\%} coverage in random deployment. In simulation, the CLP algorithm deployed at least 60 nodes to achieve the 100{\%} coverage, while the VFA algorithm required more than 100 nodes, under the same assumptions. The average moving distance for each CLP node was less than a half of the VFA node. In addition, as there are n mobile nodes, the number of CLP messages is proportional to n, while VFA is proportional to n2. The CLP algorithm is robust in fault tolerance when some nodes are error in distribution.",
author = "Wang, {Pang Chieh} and Ting-Wei Hou and Yan, {Ruei Hong}",
year = "2006",
month = "12",
day = "1",
doi = "10.1109/ICSNC.2006.53",
language = "English",
isbn = "0769526993",
series = "Second International Conference on Systems and Networks Communications, ICSNC 2006",
booktitle = "Second International Conference on Systems and Networks Communications, ICSNC 2006",

}

Wang, PC, Hou, T-W & Yan, RH 2006, Maintaining coverage by progressive crystal-lattice permutation in mobile wireless sensor networks. in Second International Conference on Systems and Networks Communications, ICSNC 2006., 4041557, Second International Conference on Systems and Networks Communications, ICSNC 2006, 2nd International Conference on Systems and Networks Communications, ICSNC 2006, Papeete, French Polynesia, 06-10-28. https://doi.org/10.1109/ICSNC.2006.53

Maintaining coverage by progressive crystal-lattice permutation in mobile wireless sensor networks. / Wang, Pang Chieh; Hou, Ting-Wei; Yan, Ruei Hong.

Second International Conference on Systems and Networks Communications, ICSNC 2006. 2006. 4041557 (Second International Conference on Systems and Networks Communications, ICSNC 2006).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Maintaining coverage by progressive crystal-lattice permutation in mobile wireless sensor networks

AU - Wang, Pang Chieh

AU - Hou, Ting-Wei

AU - Yan, Ruei Hong

PY - 2006/12/1

Y1 - 2006/12/1

N2 - A new distributed algorithm, called Crystal-Lattice Permutation (CLP) algorithm, is devised to approach the coverage problem in wireless sensor networks. AU nodes are assumed as mobile and run the same CLP algorithm in . An initial seed triggers six neighboring nodes to move to hexagon permutation positions, which is like the Crystal-Lattice formation process in nature. These chosen nodes then become new seeds to trigger other neighboring nodes. By such a progressive process, with initial and boundary conditions, the coverage is achieved. Comparing to the Virtual Force algorithm (VFA), the CLP algorithm needs fewer nodes and takes shorter average moving distance to achieve 100% coverage in random deployment. In simulation, the CLP algorithm deployed at least 60 nodes to achieve the 100% coverage, while the VFA algorithm required more than 100 nodes, under the same assumptions. The average moving distance for each CLP node was less than a half of the VFA node. In addition, as there are n mobile nodes, the number of CLP messages is proportional to n, while VFA is proportional to n2. The CLP algorithm is robust in fault tolerance when some nodes are error in distribution.

AB - A new distributed algorithm, called Crystal-Lattice Permutation (CLP) algorithm, is devised to approach the coverage problem in wireless sensor networks. AU nodes are assumed as mobile and run the same CLP algorithm in . An initial seed triggers six neighboring nodes to move to hexagon permutation positions, which is like the Crystal-Lattice formation process in nature. These chosen nodes then become new seeds to trigger other neighboring nodes. By such a progressive process, with initial and boundary conditions, the coverage is achieved. Comparing to the Virtual Force algorithm (VFA), the CLP algorithm needs fewer nodes and takes shorter average moving distance to achieve 100% coverage in random deployment. In simulation, the CLP algorithm deployed at least 60 nodes to achieve the 100% coverage, while the VFA algorithm required more than 100 nodes, under the same assumptions. The average moving distance for each CLP node was less than a half of the VFA node. In addition, as there are n mobile nodes, the number of CLP messages is proportional to n, while VFA is proportional to n2. The CLP algorithm is robust in fault tolerance when some nodes are error in distribution.

UR - http://www.scopus.com/inward/record.url?scp=40249115090&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=40249115090&partnerID=8YFLogxK

U2 - 10.1109/ICSNC.2006.53

DO - 10.1109/ICSNC.2006.53

M3 - Conference contribution

SN - 0769526993

SN - 9780769526997

T3 - Second International Conference on Systems and Networks Communications, ICSNC 2006

BT - Second International Conference on Systems and Networks Communications, ICSNC 2006

ER -

Wang PC, Hou T-W, Yan RH. Maintaining coverage by progressive crystal-lattice permutation in mobile wireless sensor networks. In Second International Conference on Systems and Networks Communications, ICSNC 2006. 2006. 4041557. (Second International Conference on Systems and Networks Communications, ICSNC 2006). https://doi.org/10.1109/ICSNC.2006.53