ABSTRACT
CONTENTS 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 6.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6.2.1 CDS-based VBs under DNM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 6.2.2 Related Literature about PNM Model . . . . . . . . . . . . . . . . . . . . . . 122 6.2.3 Literature Review of MOGAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 6.2.4 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.3 Network Model and Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 6.3.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 6.3.2 Network Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
. . . . . . . . . . . 6.3.4 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
6.4 LBVBP-MOGA Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 6.4.1 Overview of MOGAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.4.1.1 Multi-objective Problem (MOP) Definitions and Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.4.1.2 GA Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6.4.1.3 MOGA Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
6.4.2 Design of LBVBP-MOGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.4.2.1 Representation of Chromosomes . . . . . . . . . . . . . 131 6.4.2.2 Population Initialization . . . . . . . . . . . . . . . . . . . . . . 132 6.4.2.3 Fitness Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 6.4.2.4 Selection Scheme and Replacement Policy . . . 133 6.4.2.5 Genetic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.4.3 Convergence Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 6.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.5.1 Simulation Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 6.5.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
6.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
6.1 Introduction Wireless sensor networks (WSNs) are emerging as the desired environment for increasing numbers of military and civilian applications, such as disaster control, environment and habitat monitoring, battlefield surveillance, and health care applications [52]. Indeed, WSNs distinguish themselves clearly from wired networks with many features, i.e., absence of a fixed infrastructure, wireless multi-hop communication, limited bandwidth, and irreplaceable battery. Therefore, designing an energyefficient communication scheme for WSNs is one of the most important issues that has a significant impact on the network performance. Due to the infrastructure-less and dynamic nature in WSNs, most routing protocols in WSNs (i.e., flooding) usually cause a serious broadcasting storm [53]. A connected dominating set (CDS) has been a well known approach for constructing a virtual backbone (VB) to alleviate the broadcasting storm thus improving the performance and increase the efficiency of routing protocols in WSNs. A dominating set (DS) is defined as a subset of nodes in a WSN such that each node in the network is either in the set or adjacent to some nodes in the set. If the induced subgraph by the nodes in a DS is connected, then this DS is called a CDS. The nodes in a CDS are called dominators denoted by set B, or dominatees denoted by set W. Using CDS as a VB, only nodes in a CDS need to forward the messages. Thus, the average message burden of a WSN could be reduced so that routing becomes much easier and can adapt quickly to network topology changes [54]. Furthermore, using dominators as forwarding nodes can efficiently reduce the energy consumption, which is also a critical concern in WSNs. In addition to routing protocols, a CDS-based VB has many other applications in WSNs, such as
Since every node in a CDS works as a central management agent with heavy load, constructing a CDS with minimized size can greatly help to reduce the transmission interference, the number of control messages, and the storage overhead [54]. Hence, it is desirable to build a minimum-sized CDS (MCDS)-based VB.
