Connected Coverage of Wireless Networks in Theoretical and Practical Settings

Stay connected



Share on facebook
Share on twitter
Share on linkedin

CIS Colloquium, Feb 03, 2010, 11:00AM – 12:00PM, Wachman 447

Connected Coverage of Wireless Networks in Theoretical and Practical Settings

Dong Xuan, Ohio State University

Coverage and connectivity are two key properties of wireless networks; particularly wireless sensor networks (WSNs). Deploying sensor nodes to simultaneously achieve coverage and connectivity (connected coverage) requirements is a fundamental problem in WSNs. In this talk, we will focus on optimal deployment patterns in WSNs. By optimal deployment patterns, we mean those patterns that can achieve desired coverage and connectivity requirements with the fewest sensor nodes. In theoretical settings, the pure coverage problem has a long history in discrete computational geometry in both 2-dimensional and 3-dimensional spaces. In 2-dimensional space, the triangular lattice pattern was proposed and its optimality was proved in 1939. The pure coverage problem in 3-dimensional space was known to the ancient Greeks. In 1887, Lord Kelvin conjectured the optimality of the 14-sided truncated octahedral pattern. The proof of this conjecture is still open. Moreover, none of the above works considered connectivity. In recent years, we have conducted extensive studies on the connected coverage problem in both theoretical and practical settings. We have proposed a complete set of optimal deployment patterns for WSNs to achieve full coverage and k-connectivity (k <= 6) in 2-dimensional space. We have also proposed a set of optimal patterns in 3-dimensional space. These research results can help establish theoretical foundations and practical deployment guidelines not just for WSNs, but also for other wireless networks such as mesh, cellular, and IEEE 802.15.4 networks. We will discuss these results and future work in this talk.

Dong Xuan is an associate professor in the Department of Computer Science and Engineering at The Ohio State University, USA. He received his B.S. and M.S. degrees in Electronic Engineering from Shanghai Jiao Tong University (SJTU), China, in 1990 and 1993, and his Ph.D. degree in Computer Engineering from Texas A&M University in 2001. His research interests include distributed computing, computer networks, and cyberspace security. He received first prize in Scientific and Technological Achievement from the Electronic Industry Department of China in 1995, the NSF CAREER Award in 2005, and the Lumley Research Award from the College of Engineering at The Ohio State University in 2009.