الگوریتم های ژنتیکی پویا برای مسئله خوشه بندی متعادل پویا بار در شبکه های ای دی هک موبایل

Clustering can help aggregate the topology information and reduce the size of routing tables in a mobile ad hoc network (MANET). To achieve fairness and uniform energy consumption, each clusterhead should ideally support the same number of clustermembers. However, a MANET is a dynamic and complex system and its one important characteristic is the topology dynamics, that is, the network topology changes over time due to the factors such as energy conservation and node movement. Therefore, in a MANET, an effective clustering algorithm should efficiently adapt to each topology change and produce the new load balanced clusterhead set quickly. The maintenance of the cluster structure should aim to keep it as stable as possible to reduce overhead. To meet this requirement, the new solution should keep as many good parts in the previous solution as possible. In this paper, we first formulate the dynamic load balanced clustering problem (DLBCP) into a dynamic optimization problem. Then, we propose to use a series of dynamic genetic algorithms (GAs) to solve the DLBCP in MANETs. In these dynamic GAs, each individual represents a feasible clustering structure and its fitness is evaluated based on the load balance metric. Various dynamics handling techniques are introduced to help the population to deal with the topology changes and produce closely related solutions in good quality. The experimental results show that these GAs can work well for the DLBCP and outperform traditional GAs that do not consider dynamic network optimization requirements.

A mobile ad hoc network (MANET) (Minhas et al., 2011 and Siva Ram Murthy and Manoj, 2004) is a self-organizing and self-configuring multihop wireless networks, which is comprised of a set of mobile hosts that can move around freely and cooperate in relaying packets on behalf of one another. It has the advantages of low cost, plug-and-play convenience, and flexibility. Analogous to the IP subnet concept in the Internet, a MANET can also be divided into a hierarchical architecture by organizing nodes into clusters. Within each cluster, the information regarding the nodes and links is aggregated. Each cluster can thus be seen as a logical node at the cluster level. The network layer only needs to maintain and manage the information of these logical nodes. The control overhead of the network is reduced with the aid of clustering. Clustering is a key issue in MANETs and their applications (Wang, Liu, Zhou, & Ansari, 2008). The importance of the clustering problem can be summarized in two aspects. First, it plays a critical role in effective network management. A MANET usually has hundreds of mobile nodes. Its flat network infrastructure encounters the scalability problem when the network size keeps rising. Due to node mobility, scalability is more challenging in MANETs than in wired network. Therefore, effective network management is extremely important. So far, clustering is the most efficient way to manage MANETs (Chatterjee, Das, & Turgut, 2002). Second, clustering serves as the foundation for many other key issues in MANETs, e.g., routing (Safa et al., 2010 and Su et al., 2008), intrusion detection (Kim, Kim, & Kim, 2006), topology control (Shen et al., 2004), and backbone construction (Andronache & Rothkugel, 2008). All these problems are solved based on a well clustered network structure. The goal of a clustering algorithm (Yu & Chong, 2005) is to find a feasible interconnected set of clusters covering the entire set of nodes in a MANET. At any instant, one mobile node can only belong to one cluster. A cluster may have a clusterhead or not. However, since the recruiting of clusterheads brings the advantage of easy management, most of the prior research works focus on clustering where clusterheads are appointed. In this paper, our algorithms also generate the clusters with clusterheads. Furthermore, clustering must be conducted with at least one metric such as node ID, node degree and energy (battery energy). The metric is determined based on the application requirements. For example, in the highest degree heuristic (Gerla & Tsai, 1995), the node with the maximum number of neighbors (highest degree) is chosen as the clusterhead. In this paper, we consider the load balance as the clustering metric since it is an important application requirement. The load balance means that every clusterhead should ideally support the same number of clustermembers. It can guarantee the fairness for all the clusterheads in terms of the workload. Moreover, the load balanced clustering can help prolong the lifetime of the cluster structure since each clusterhead will evenly consume its battery energy. It has been proved that finding an optimal set of clusterheads with one or more clustering metrics is NP-hard (Chatterjee et al., 2002). Conventional search techniques, such as hill climbing (Russell & Norvig, 2003), are often incapable of optimizing non-linear multimodal functions. In such a case, a random search method might be required. Genetic algorithm (GA) is a well-known guided random search and optimization technique, which is based on the basic principles of evolution: survival of the fittest and inheritance. Generally speaking, GAs are applied to find a close to optimal solution with respect to a fitness function for NP-hard problems. However, since we consider the load balanced clustering in a continuously changing network environment, the problem turns out to be one dynamic optimization problem (DOP). In recent years, studying GAs for DOPs has attracted a growing interest due to its importance in GA’s real world applications (Yang & Yao, 2008). The simplest way of addressing DOPs is to restart GAs from scratch whenever an environmental change is detected. Although the restart scheme really works for some cases (Yang & Yao, 2005), for many DOPs it is more efficient to develop other approaches that make use of knowledge gathered from old environments. Over the years, several approaches have been developed for GAs to address dynamic environments (Branke, 2002, Morrison, 2004 and Yang et al., 2007), such as maintaining diversity during the run via random immigrants (Grefenstette, 1992 and Vavak and Fogarty, 1996), increasing diversity after a change (Cobb & Grefenstette, 1993), using memory schemes to reuse stored useful information (Branke, 1999, Trojanowski and Michalewicz, 1999, Trojanowski and Michalewicz, 2000, Yang, 2005a and Yang, 2005b), and applying multi-population and speciation schemes to search in different regions of the search space (Branke et al., 2000, Oppacher and Wineberg, 1999 and Parrott and Li, 2006). For the sake of description convenience, we term these GAs that are properly enhanced to address DOPs as dynamic GAs. In this paper, we adapt and apply several types of dynamic GAs that are developed to deal with general DOPs to solve the dynamic load balanced clustering problem (DLBCP) in MANETs. First, we design the components of the Standard GA (SGA) specifically for the DLBCP. Then, we integrate several immigrants, memory, multi-population schemes and their combinations into the SGA to enhance its capability in handling the environmental dynamics. For example, regarding the immigrants schemes, at each generation, a certain number of immigrants are generated and added into the population to maintain the diversity. Once the topology is changed, the new immigrants can help guide the search of good solutions in the new environment. For comparison purposes, we also implement the SGA and the Restart GA (RGA). By extensive simulation experiments, we evaluate their performance on the DLBCP. The results show that these dynamic GAs significantly outperform both the traditional GA methods and the non-GA technique. They work really well in the dynamic real-world wireless networks. The rest of this paper is organized as follows. We discuss related work in Section 2. The MANET model and the DLBCP model are described in Section 3. Section 4 presents the design of a specialized GA for the static load balanced clustering problem. The dynamic GAs that are investigated for the DLBCP are described in Section 5. The extensive experimental study and relevant analysis are presented in Section 6. Finally, Section 7 concludes this paper with some discussions on the future work.

A MANET is a self-organizing and self-configuring multihop wireless network, which has a wide usage nowadays. The clustering problem in MANETs aims to organize the network into a hierarchy structure, i.e., dividing the nodes into different clusters. In each cluster, a node acting as the clusterhead will serve all the other clustermembers as a local coordinator. A fair cluster structure requires that each clusterhead serves the same number of clustermembers, thereby achieving the load balance. This problem has been addressed in MANETs. However, previous works do not pay much attention to the continuous topology changes, which are actually the inherent characteristics of MANETs. Intuitively, it is much more challenging to deal with the dynamic clustering problem in a continuously changing network than to solve the quasi-static one in a quasi-static infrastructure, where only local small modifications are introduced after clustering. In recent years, there has been a growing interest in studying GAs for DOPs. Typical approaches to enhancing the performance of GAs for DOPs include the immigrants schemes, memory schemes, multi-population schemes, and their combinations. In this paper, we term the GAs based on these schemes as dynamic GAs. We develop seven dynamic GAs to solve the DLBCP in a large scale MANET. The GA components for the clustering problem are also specifically designed. To encourage the load balance, we use the standard deviation of clusterhead degrees to evaluate the performance of the clustering results. For comparison purposes, we also implement two traditional GAs and one common non-GA technique. Simulation experiments show that these dynamic GAs are powerful techniques for solving the DLBCP while the traditional GAs cannot deal with the practical DLBCP. The non-GA technique also shows much worse performance than dynamic GAs. Remarkably, EIGA and MEGA outperform other dynamic GAs significantly for the DLBCP tested in this paper. In summary, the major contributions of this paper are as follows. First, a novel general model of dynamic network optimization problem is developed. The DLBCP model has captured the fundamental characteristics of MANETs, i.e., the topology changes in a continuous way. The load balance metric is also accurately formulated. This model could be used by a wide range of AI methods, e.g., ant colony optimization, and artificial immune algorithm. Second, dynamic GAs are developed and it has been shown that they are capable of providing good solutions for the DLBCP. How to solve the DLBCP is an important and challenging problem. By considering the domain knowledge of network clustering, we develop a few dynamics handling schemes and incorporate them into GAs to form the dynamic GAs. This is a novel way to solve the DLBCP and has been proved successful. The efficiency and effectiveness of dynamic GAs have also been verified in practical problem solving. Our work can inspire other researchers to utilize dynamic GAs to solve other DOPs in practice. Third, dynamic network environment and dynamic test environment are constructed. They play important roles in solving dynamic network optimization problems. Our network environment and test environment consider the features of network dynamics and represent them by adjustable parameters. The parameters can be tailored for simulating specific dynamic networks. Therefore, they can be widely used and benefit other research works. We believe that this is the first work to investigate the efficiency and effectiveness of GAs for solving the DLBCP in the real-world wireless networks, i.e., MANETs. Although all the experiment results and analysis are based on simulated environments, the research provides useful guidelines for deploying the methods in a real situation. In our dynamic GAs, the node degree and the number of clustermembers are used for calculating the fitness. In a real situation, these parameters are still the same as in simulated environment and will not be affected by other environmental factors. Therefore, all the algorithms will show similar performance even in real situations. However, slight overall performance degradation should be expected due to the possible inference in topology collection. Since the practical clustering problem may have more than one clustering metrics, one interesting future work will be to investigate GAs for solving dynamic multi-metric clustering problem in MANETs.