Recyclable Connected Dominating Set for Large Scale Dynamic Wireless Networks

摘要

Many people studied the Minimum Connected Dominating Set (MCDS) problem to introduce Virtual Backbone (VB) to wireless networks. However, many existing algorithms assume a static wireless network, and when its topology is changed, compute a new CDS all over again. Since wireless networks are highly dynamic due to many reasons, their approaches can be inefficient in practice. Motivated by this observation, we propose Recyclable CDS Algorithm (RCDSA), an efficient VB maintenance algorithm which can handle the activeness of wireless networks. The RCDSA is built on an approximation algorithm CDS-BD-C1 by Kim et. al. [1]. When a node is added to or deleted from current graph, RCDSA recycles current CDS to get a new one. We prove RCDSA's performance ratio is equal to CDS-BD-Cl's. In simulation, we compare RCDSA with CDS-BD-C1. Our results show that the average size of CDS by RCDSA is similar with that by CDS-BD-C1 but RCDSA is at least three times faster than CDS-BD-C1 due to its simplicity. Furthermore, at any case, a new CDS by RCDSA highly resembles to its old version than the one by CDS-BD-C1, which means that using RCDSA, a wireless network labors less to maintain its VB when its topology is dynamically changing.