ABSTRACT
In the wireless network with a dominating set, the lifetime of the network depends on the normal work time of the dominating set. The problem of the maximal independent set (MIS) has an extraordinary effect in various wireless networks, receiving extensive attention from the research fields of wireless networks. This chapter introduces the simple MIS parallel algorithm and the proposed MIS construction algorithms. MIS technology is applied extensively in the design of wireless network protocol, especially in the aspects of the connected dominating set (CDS) and coloring. Weakly CDS (WCDS) construction plays a vital role in the clustering algorithm and the design process of the CDS construction algorithm. The first WCDS construction algorithm selects the neighbor with the minimum id as the dominating node. The WCDS algorithm is divided into three stages: leader selection, hierarchical calculation, and coloring label. The chapter provides a local algorithm for solving EWCDS by the extended cutting rule and analyzes the performance of the algorithm.
