Constructing a self-stabilizing CDS with bounded diameter in wireless networks under SINR
Autor: | Shengling Wang, Yunchuan Sun, Jiguo Yu, Xueli Ning, Yawei Wang |
---|---|
Rok vydání: | 2017 |
Předmět: |
Mathematical optimization
Computer science Topology control Wireless network Signal-to-interference-plus-noise ratio Approximation algorithm 020206 networking & telecommunications 02 engineering and technology Topology Asymptotically optimal algorithm Distributed algorithm 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Algorithm design Wireless sensor network MathematicsofComputing_DISCRETEMATHEMATICS |
Zdroj: | INFOCOM |
Popis: | As a virtual backbone structure, connected dominating sets (CDSs) play an important role in topology control for wireless networks. In this paper, we develop a distributed self-stabilizing CDS construction algorithm under the SINR model (also known as the physical interference model), a more practical yet more challenging interference model for distributed algorithm design. Specifically, we propose a randomized distributed algorithm that can construct a CDS in O (log n) timeslots with a high probability, where n is the total number of nodes in the network. The constructed CDS achieves constant approximation in both density and diameter. To the best of our knowledge, this is the first known asymptotically optimal self-stabilizing result in terms of both density and diameter for distributed CDS construction under the practical SINR model. |
Databáze: | OpenAIRE |
Externí odkaz: |