Complete optimal deployment patterns for full-coverage and k-connectivity (k ≤ 6) wireless sensor networks

Xiaole Bai; Dong Xuan; Ziqiu Yun; Ten H. Lai; WeiJia Jia

doi:10.1145/1374618.1374672

Complete optimal deployment patterns for full-coverage and k-connectivity (k ≤ 6) wireless sensor networks

Xiaole Bai
, Dong Xuan
, Ziqiu Yun
, Ten H. Lai
, WeiJia Jia

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

127 Citations (Scopus)

Abstract

In this paper, we propose deployment patterns to achieve full coverage and three-connectivity, and full coverage and five-connectivity under different ratios of sensor communication range (denoted by R_c) over sensing range (denoted by R_s ) for wireless sensor networks (WSNs). We also discover that there exists a hexagon-based universally elemental pattern which can generate all known optimal patterns. The previously proposed Voronoi-based approach can not be applied to prove the optimality of the new patterns due to their special features. We propose a new deployment-polygon based methodology, and prove their optimality among regular patterns when R_c/R_s ≥ 1. We conjecture that our patterns are globally optimal to achieve full coverage and three-connectivity, and full coverage and five-connectivity, under all ranges of R_c/R_s . With these new results, the set of optimal patterns to achieve full coverage and k-connectivity (k ≤ 6) is complete, for the first time. © 2008 ACM.

Original language	English
Title of host publication	MobiHoc '08: Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing
Publisher	Association for Computing Machinery
Pages	401-410
ISBN (Print)	9781605580739
DOIs	https://doi.org/10.1145/1374618.1374672
Publication status	Published - May 2008
Event	9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2008) - Hong Kong, China Duration: 26 May 2008 → 30 May 2008

Conference

Conference	9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2008)
Place	China
City	Hong Kong
Period	26/05/08 → 30/05/08

Research Keywords

Wireless sensor network topology
Optimal deployment pattern
Coverage
Connectivity

Access Output

10.1145/1374618.1374672

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{76bb52f842a7446d81a7547e4e3ca482,

title = "Complete optimal deployment patterns for full-coverage and k-connectivity (k ≤ 6) wireless sensor networks",

abstract = "In this paper, we propose deployment patterns to achieve full coverage and three-connectivity, and full coverage and five-connectivity under different ratios of sensor communication range (denoted by Rc) over sensing range (denoted by Rs ) for wireless sensor networks (WSNs). We also discover that there exists a hexagon-based universally elemental pattern which can generate all known optimal patterns. The previously proposed Voronoi-based approach can not be applied to prove the optimality of the new patterns due to their special features. We propose a new deployment-polygon based methodology, and prove their optimality among regular patterns when Rc/Rs ≥ 1. We conjecture that our patterns are globally optimal to achieve full coverage and three-connectivity, and full coverage and five-connectivity, under all ranges of Rc/Rs . With these new results, the set of optimal patterns to achieve full coverage and k-connectivity (k ≤ 6) is complete, for the first time. {\textcopyright} 2008 ACM.",

keywords = "Wireless sensor network topology, Optimal deployment pattern, Coverage, Connectivity",

author = "Xiaole Bai and Dong Xuan and Ziqiu Yun and Lai, \{Ten H.\} and WeiJia Jia",

year = "2008",

month = may,

doi = "10.1145/1374618.1374672",

language = "English",

isbn = "9781605580739",

pages = "401--410",

booktitle = "MobiHoc '08: Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing",

publisher = "Association for Computing Machinery",

address = "United States",

note = "9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2008) ; Conference date: 26-05-2008 Through 30-05-2008",

}

Bai, X, Xuan, D, Yun, Z, Lai, TH & Jia, W 2008, Complete optimal deployment patterns for full-coverage and k-connectivity (k ≤ 6) wireless sensor networks. in MobiHoc '08: Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing. Association for Computing Machinery, pp. 401-410, 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2008) , Hong Kong, China, 26/05/08. https://doi.org/10.1145/1374618.1374672

Complete optimal deployment patterns for full-coverage and k-connectivity (k ≤ 6) wireless sensor networks. / Bai, Xiaole; Xuan, Dong; Yun, Ziqiu et al.
MobiHoc '08: Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing. Association for Computing Machinery, 2008. p. 401-410.

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Complete optimal deployment patterns for full-coverage and k-connectivity (k ≤ 6) wireless sensor networks

AU - Bai, Xiaole

AU - Xuan, Dong

AU - Yun, Ziqiu

AU - Lai, Ten H.

AU - Jia, WeiJia

PY - 2008/5

Y1 - 2008/5

N2 - In this paper, we propose deployment patterns to achieve full coverage and three-connectivity, and full coverage and five-connectivity under different ratios of sensor communication range (denoted by Rc) over sensing range (denoted by Rs ) for wireless sensor networks (WSNs). We also discover that there exists a hexagon-based universally elemental pattern which can generate all known optimal patterns. The previously proposed Voronoi-based approach can not be applied to prove the optimality of the new patterns due to their special features. We propose a new deployment-polygon based methodology, and prove their optimality among regular patterns when Rc/Rs ≥ 1. We conjecture that our patterns are globally optimal to achieve full coverage and three-connectivity, and full coverage and five-connectivity, under all ranges of Rc/Rs . With these new results, the set of optimal patterns to achieve full coverage and k-connectivity (k ≤ 6) is complete, for the first time. © 2008 ACM.

AB - In this paper, we propose deployment patterns to achieve full coverage and three-connectivity, and full coverage and five-connectivity under different ratios of sensor communication range (denoted by Rc) over sensing range (denoted by Rs ) for wireless sensor networks (WSNs). We also discover that there exists a hexagon-based universally elemental pattern which can generate all known optimal patterns. The previously proposed Voronoi-based approach can not be applied to prove the optimality of the new patterns due to their special features. We propose a new deployment-polygon based methodology, and prove their optimality among regular patterns when Rc/Rs ≥ 1. We conjecture that our patterns are globally optimal to achieve full coverage and three-connectivity, and full coverage and five-connectivity, under all ranges of Rc/Rs . With these new results, the set of optimal patterns to achieve full coverage and k-connectivity (k ≤ 6) is complete, for the first time. © 2008 ACM.

KW - Wireless sensor network topology

KW - Optimal deployment pattern

KW - Coverage

KW - Connectivity

UR - https://www.scopus.com/pages/publications/57349090662

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-57349090662&origin=recordpage

U2 - 10.1145/1374618.1374672

DO - 10.1145/1374618.1374672

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9781605580739

SP - 401

EP - 410

BT - MobiHoc '08: Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing

PB - Association for Computing Machinery

T2 - 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2008)

Y2 - 26 May 2008 through 30 May 2008

ER -