Joics.com

Journal of Information & Computational Science 10:17 (2013) 5457–5466 A Multi-parameter Weighted Clustering Algorithm for
Mobile Ad Hoc Networks ⋆
aCollege of Communication Engineering, Chongqing University, Chongqing 400044, China bJiangbei Power Supply Bureau of Chongqing Electric Power Corp., Chongqing 401147, China Abstract
Clustering is an efficient way of network topology management, and the hierarchical structure obtainedby clustering algorithm can largely improve the performance of Mobile Ad Hoc Network (MANET). Tobetter accommodate MANET, we propose a Multi-parameter Weighted Clustering (MWC) algorithmwhich takes into consideration three parameters: residual power, connectivity, and average mobility. Wealso designed different average mobility parameter for two typical MANET models, that is, RelativeStability (RS) for Random Walk Mobility (RWM) networks and Moving Correlation (MC) for ReferencePoint Group Mobility (RPGM) networks. Simulation results showed that the proposed algorithm has abetter performance than HD and MOBIC in three aspects: topology simplicity, environment adaptability,and cluster stability.
Keywords: MANET; Clustering Algorithm; Node Mobility; Network Topology Management Introduction
One of the key issues of MANET is dynamic routing. Relative studies have shown that perfor-mance and expansibility of planar network will be degraded with increasing number of nodes.
Belding-Royer’s studies have shown that communication overhead of MANET with n nodesbased on priori routing protocols is O(n2) [1].
RREQ (flooding route request message) and route creation delay of MANET based on reactive routing protocol will also increase with nodedensity and mobility. As a result, it is impossible to meet the requirements of QoS in applica-tion.
As a typical hierarchy, clustering is widely used in data processing, network topology control and many other fields. In terms of network topology control, clustering have three major ad-vantages [2]: network capacity is largely increased because of spatial multiplexing; overload of ⋆Project supported by the National Nature Science Foundation of China (No. CSTC2009BA2064) and the Fundamental Research Founds for the Central Universities of China (No. CDJXS11162236).
Email address: fengwj@cqu.edu.cn (Wenjiang Feng).
1548–7741 / Copyright 2013 Binary Information PressDOI: 10.12733/jics20102385 W. Feng et al. / Journal of Information & Computational Science 10:17 (2013) 5457–5466 route establishment can be significantly reduced because of virtual backbone formed of cluster-heads and gateway nodes; and network becomes more simplified and more robust and easier tomanage and maintain. Further more, clustering support node mobility and network scalability.
However, formation and maintenance of clusters involves a large number of information exchange[3]. Local changes such as movement and node death may cause re-election of clusterhead andeven trigger global reconstruction [4]. All these lead to additional overhead. Furthermore, be-cause of dynamic nature, the configuration of clusterhead is constantly changing, so the numberof clusterhead should be minimized. As a result, we should adopt a rational clustering algorithmto improve stability of clusters and reduce network overhead.
Related Work
In the past years, a number of clustering schemes have been proposed for MANETs. Some of themhave been described in details in the recent survey papers [3, 5]. These clustering schemes canbe categorized based on different characteristics. According to the existence or absence of clus-terhead, they can be divided into clusterhead based clustering algorithm [6] and non-clusterheadbased clustering algorithm [7]. According to the number of hops between clustermember and theclusterhead, they can be divided into one-hop clustering algorithm [8, 9] and multi-hop clusteringalgorithm [10]. According to different optimization objective, it can be divided into dominant setbased clustering algorithm [11], low overhead clustering algorithm [12], mobile-aware clusteringalgorithm [13], energy efficient clustering algorithm [14], load-balance clustering algorithm [15],multi-parameter based clustering algorithm [6, 9, 16] and so on.
One of the most popular topology-aware algorithms is HD (highest-degree) algorithm [8] in which node with the largest number of one-hop neighbors is elected as clusterhead. While theclusterheads are not likely to play their role for very long time, the increasing number of nodeswill reduce the throughput and degrade system performance. Basu et al. studied node mobilityand proposed a mobility clustering (MOBIC) algorithm [13]. MOBIC algorithm selects node ofthe least relative mobility in the set as clusterhead. Also introduced with cluster maintenancemechanism, MOBIC is effective to avoid cluster reconstruction. The Weighted Clustering Algo-rithm (WCA) [9] which obtains 1-hop cluster takes more factors into consideration and makesclusterhead election and cluster maintenance more reasonable. But WCA has the drawback ofcommunication overhead and also the cumulative time of the node serving as clusterhead cannotaccurately reflect current battery power. Another multi-parameter based clustering algorithmis on-demand weighted clustering algorithm for adaptive (AOW) [6]. AOW require message ex-change only among adjacent nodes, thus largely reduce the control overhead. Weighted distributedclustering algorithm (CBMD) [16] is another multi-parameter based clustering algorithm. CBMDassumes a predefined limit for the number of nodes to be held by a clusterhead, and successfullyimproves load balancing and performance of the networks. To maximize lifetime of the net-work and balance load, an energy efficient clustering algorithm [14] is proposed. The clusterheadcan be replaced by candidate clusterhead after its continuous working time reaches the givenvalue.
In this paper, we propose a Multi-parameter Weighted Clustering (MWC) algorithm which adapts to the needs of networks and dynamic nature of nodes. MWC makes network topologysimpler and makes sure stability of clusters.
W. Feng et al. / Journal of Information & Computational Science 10:17 (2013) 5457–5466 Our Contribution
Principle of MWC
As to clustering, we assume that there is at least one clusterhead in the neighbor set of eachclustermember, and each clustermember is only dominated by its clusterhead; if the difference ofadjacent clusterhead Stability Parameter (SP ) value is greater than threshold wth, then cluster-head of smaller SP value will become a clustermember, and join the cluster with larger SP value.
Our aim is to design an algorithm which can select appropriate node as clusterhead and simplifythe topology of the network. The election of clusterhead is based on metrics explained as below.
Residual Power Parameter: Because of heavier load, clusterhead consume more power
than clustermember. In order to balance power in the net, MWC takes residual power intoconsideration and elects node of higher residual power as clusterhead. Assume that nodes areable to obtain residual power through its own power management unit. The residual powerparameter of node i at time t is denoted by Ei(t), as Ei(t) = ei(t)/ei(0), where ei(t) and ei(0) is available residual power and initial power of node i at time t, respectively.
Connectivity Parameter: The connectivity refers to the number of neighbors, and it is
inversely proportional to the number of clusters, that is, with reduced number of clusters, thenetwork topology become simpler. In order to form a simpler network topology, the connectivityshould be taken into considerations. Assume that information of neighbors can be obtained byinteractions with others, and ni(t) denotes the number of neighbors which has a direct link andone hop to node i at time t. The connectivity parameter Ni(t) can be defined as: Ni(t) = 1 − 1/ni(t). Average Mobility Parameter: The main characteristic of MANET is the dynamic topology,
we designed different average Mobility Parameter (M P ) for different network model, RelativeStability (RS) for Random Walk Mobility (RWM) [17] networks and Moving Correlation (M C)for Reference Point Group Mobility (RPGM) [18] networks.
a. Relative Stability (RS): It is designed for Random Walk Mobile (RWM) networks. Base
on RS, we can elect a relatively stable node as clusterhead.Assume that node i can obtain itsown location (xi(t), yi(t)) at time t, then the distance between node i and node j is denoted bydi,j(t), as: (xi(t) − xj(t))2 + (yi(t) − yj(t))2. The relative speed of node i to node j is denoted by mi,j(t), as: mi,j(t) = |di,j(t) − di,j(t − ∆T )|/∆T. Then, RS of node i can be denoted by Si(t) as: Si(t) = 1 − E[mi,j(t)]/mth. W. Feng et al. / Journal of Information & Computational Science 10:17 (2013) 5457–5466 where E[mi,j(t)] is the average speed of node i to its all neighbors, and mth is the threshold ofrelative speed.
b. Moving Correlation (M C): It is designed for Reference Point Group Mobile (RPGM)
networks, in which there is a strong correlation in node mobility. So we can select a node withstrong correlation to the group as clusterhead.
Assume that clustering signal Cluster(i) is send every time ∆T , during which the node measured its location M times, so the time interval is denoted by τ , as τ = ∆T /M . Then, we can get theequation as: { ∆x(m) = xi(t + mτ) −xi(t), ∆y(m) = yi(t + mτ ) − yi(t). The average speed and direction of node i from time t to t + mτ is denoted by vi(t + mτ ) and ∆x(m)2 + ∆y(m)2/(mτ ).  arctan |∆y(m)| × sgn(∆y(m)),
di(t + mτ ) =  (π/2) × sgn(∆y(m)),
 (π − arctan|∆y(m)|) × sgn(∆y(m)), ∆x(m) < 0
Macro speed and directions of node i from time t to t + T are denoted by vi(t + T ) and di(t + T ), vi(t + mτ ). di(t + mτ ). Correlation speed and directions of node i to node j at time t are denoted by Rs(i, j, t) and Rd(i, j, t), and the moving correlation denoted by Rsd(i, j, t) can be defined as the multiplicationof Rs(i, j, t) and Rd(i, j, t), as: i(t), vj (t)) max(vi(t), vj(t)) Rd(i, j, t) = cos(di(t) − dj(t)) Rsd(i, j, t) = Rs(i, j, t) × Rd(i, j, t) So M C of node i denoted by Ri(t) can be defined as the average moving correlation of node i W. Feng et al. / Journal of Information & Computational Science 10:17 (2013) 5457–5466 Description of MWC
Based on the preceding discussions, we propose MWC algorithm which effectively combines themultiple node parameters. The Multi-parameter Weight (M W ) W i can be described as: 1Ei(t) + ω2Ni(t) + ω3Mi(t) where ωm ⊂ [0, 1](m = 1, 2, 3) and ω1 + ω2 + ω3 = 1, superscript of W i(n = 1, 2) refers to node i, and subscript refers to the type of network model. In this paper, we consider two types of networkmodel, i.e. n = 1 and n = 2. n = 1 indicates RWM network in which Mi(t) refers to relativestability parameter Si(t), while n = 2 indicates the RPGM network, and in this case Mi(t) refersto moving correlation parameter Ri(t). Here, ωm ⊂ [0, 1] can be adjusted based on applicationrequirements. For example, for Wireless Sensor Networks (WSN), energy is more important andthe residual power should be given greater weight. On the other hand, if considering the effectof node mobility, weight for average mobility should be given greater weight. Flexibility in theallocation of weight makes MWC algorithm adaptable to a variety of network environments.
We take RWM network for example. Nodes are in direct communication if and only if they are within transmission range of each other. Each node send and receive Clsuter(i) to and fromits neighbors every ∆T to have a better knowledge of its neighbors. Clsuter(i) contains ID(j),Status(j), dominant clusterhead IDC(j), W j(t), and others. Note that S fined), CM (clustermember) or CH (clusterhead), and is initialized as UD, and W i(t) is initialized as 0. Also note that each node computes its own value of each parameter cited above. MWC iscomposed of two stages. Both stages are described below.
stage 1: Determination of status
step 1: Build a table of neighbors for each node i, and compute its connectivity parameter step 2: Obtain residual power through its own power management unit, and compute its residual power parameter Ei(t).
step 3: Obtain the location of node j, and compute its relative stability parameter Si(t).
step 4: Calculate the stability parameter according to 15 for each node.
step 5: According to the updating policy and the calculated W i(t) determine the status of
step 6: Repeat Step 1 to 5 based on Clsuter(i) broadcasted every ∆T for topology updating.
stage 2: Updating policy
Due to the dynamic nature of the network, the status of node can change with time. Based on the current status of node i Status(i), there are three cases as displayed below.
case 1: Status=UD: If the MW value of node i is wth or more than the maximum MW value
of its adjacent clusterhead, that is W i(t) > max W ajacent−CH (t) + w th, then, node i will become CH. If the case is on the contrary, W i(t) < max W ajacent−CH (t) + w th, then node i will become CM. If there exists no clusterhead in its neighbor set, and its M W value is higher than any otherUD neighbors, then it will become CH, otherwise, the node will keep the current state.
case 2: Status(i)=CH: If there exists clusterhead k in the neighbor set of clusterhead i, and
ifW k(t) > W i(t) + w th, then, node i will become CM of the cluster k. if there is no clusterhead W. Feng et al. / Journal of Information & Computational Science 10:17 (2013) 5457–5466 in the neighbor set of node i, then the node will keep the current state.
case 3: Statusi=CM: If its clusterhead disappear from its neighbor set, it will become an UD,
and it will go to case1. If the maximum M W value of clusterhead k in its neighbor set is more
than its own clusterhead, then it will become CM of cluster k. Otherwise, the node will keep the
current state.
Simulation
In order to assess the performance of the proposed MWC algorithm, we made simulation andcomparative analysis of MWC, MOBIC and HD algorithms. We choose to study three metrics: Number of clusterhead NCH: The number of clusterhead is closely related with the size and
number of cluster formed in the networks. It is an important way to evaluate the efficiency ofnetwork topology management.
Number of re-affiliation NRA: If a clustermember disassociate itself from its clusterhead,
and associate to another cluster, then the re-affiliation occurs. It is an important way to evaluatestability of clusters and the overhead of cluster maintenance. The higher the NRA, the lower thestability of clusters, and the higher the control traffic overhead.
Number of reconstruction NRC: NRC refers to the phenomenon that a clusterhead abandon
its identity as CH, resulting in the reconstruction of clusters. This metric is an important indica-tion of cluster stability. If the number of reconstruction is reduced, the overhead of communicationwill be largely reduced.
As to the particularity of proposed algorithm, we made simulations based on different scenarios: A. RWM-based simulation
In this scenario, nodes move randomly according to the random point model in all possible directions. The time interval is set as 1 second, and the update of cluster structure is done inevery 15 seconds. ω1, ω2, ω3 are all set 1/3, wth = 0.2. Other basic parameters used in ourexperiments are summarized in the Table 1 below: Table 1: Simulation parameters in RWM-based simulation We take the average value of 50 simulations as the result, and each simulation last 15 minutes Fig. 1 and Fig. 2 show the average NCH of different clustering algorithms for varying densities.
The figures indicate that NCH is proportional to densities and transmission range. Note thatNCH of MWC is lower than that of HD and MOBIC.
Fig. 3 shows the evolution of NRA according to transmission range for the three algorithms.
We observe that NRA increase with the transmission range from 100 m to 200 m, while, NRA willdecline when transmission range is larger than 200 m. We also note that NRA of MWC is lower W. Feng et al. / Journal of Information & Computational Science 10:17 (2013) 5457–5466 Fig. 3: Impact of transmission range on NRA Fig. 4: Impact of transmission range on NRC than that of HD and MOBIC. Fig. 4 shows the relationship of NRC and transmission range forthe three algorithms. we can see that NRC of MWC is the lowest of the three.
From the figures above, we can see that MWC obviously outperforms HD and MOBIC in RWB B. RPGM-based simulation
In this scenario, nodes center around a virtual reference point and move according to the reference point group model. Each node in the group has a closely related but relatively randommovement to the reference point. ω1, ω2, ω3 are set as 1/4, 1/4, 1/2. wth = 0.2. The update ofcluster structure is done in every 15 seconds. other basic parameters used in our experiments aresummarized in the Table 2 below: We take the average value of 50 simulations as the result, and each simulation last 15 minutes W. Feng et al. / Journal of Information & Computational Science 10:17 (2013) 5457–5466 Table 2: Simulation parameters in RPGM-based simulation Fig. 5 and Fig. 6 show the average NCH of different clustering algorithm for varying densities.
We can see that NCH is proportional to densities and transmission range. Note that NCH ofMWC is lower than that of HD and MOBIC.
Fig. 7 shows the evolution of NRA according to transmission range for the three algorithms in RPGM networks. Because of taking movement correlation instead of merely movement into Fig. 7: Impact of transmission range on NRA Fig. 8: Impact of transmission range on NRC W. Feng et al. / Journal of Information & Computational Science 10:17 (2013) 5457–5466 consideration, MWC has the least NRA. Fig. 8 shows the relationship of NRC and transmissionrange for the three algorithms. we can also see that NRC of MWC is the lowest of the three.
Conclusion
Clustering is an efficient way of network topology control. Motivated by the challenges of clus-tering in MANET, we have presented a multi-parameter weighted clustering algorithm. Andsimulation results show that our algorithm has a better performance on average in three aspects:firstly, the formed topology is more simple and easier to be controlled; secondly, MWC has astrong environmental adaptability, and it can adapt well to changes in node mobility and trans-mission range. Thirdly, MWC can improve the stability of clusters, and reduce the overhead ofcommunication and cluster maintenance.
Further studies on identification of network model can be done, and the clustering algorithm proposed in this paper is a good foundation in network topology control, network optimization,QoS guarantees in MANET.
References
Mohammed Tarique, Kemal E. Tepe, Sasan Adibi, Survey of multipath routing protocols for mobilead hoc networks, Journal of Network and Computer Applications, 32 (2009), 1125-1143 Atslands R. Rocha, Luci Pirmez, Flavia C. Delicato, WSNs clustering based on semantic neigh-borhood relationships, Computer Networks, 56 (2012), 1627-1645 Umamaheswari, Clustering schemes for mobile ad hoc networks: A review, in: Proc. InternationalConference on Computer Communication and Informatics, 2012, 1-6 Z. P. Zhou, An energy balanced cluster algorithm for wireless sensor networks, in: Proc. 24thChinese Control and Decision Conference, 2012, 3843-3848 Abolfazle Akbari, Ali Khosrozadeh, Naser Lasemi, Clustering algorithms in mobile ad hoc net-works, in: Proc. 2009 Fourth International Conference on Computer Sciences and ConvergenceInformation Technology, 2009, 1509-1513 Haitao Wang, Hui Chen, Lihua Song, Improved AOW clustering algorithm for wireless self-organized network and performance analysis, in: Proc. 2012 Cross Strait Quad-regional RadioScience and Wireless Technology Conference, 2012, 142-146 Jiguo Yu, Nannan Wang, Guanghui Wang, Constructing minimum extended weakly-connecteddominating sets for clustering in ad hoc networks, Journal of Parallel and Distributed Computing,72 (2012), 35-47 C. Tselikis, S. Mitropoulos, C. Douligeris et al., Empirical study of clustering algorithm for wire-less ad hoc networks, in: Proc. 16th International Conference on Systems, Signals and ImageProcessing, 2009, 1-6 Mainak Chatterjee, Sajal K. Das, Damla Turgut, WCA: A weighted clustering algorithm for mobilead hoc networks, Journal of Cluster Computing, 5 (2002), 193-204 [10] Jiehui Chen, Chul-Soo Kim, Fu Song, A distributed clustering algorithm for Voronoi cell-based large scale wireless sensor networks, in: Proc. 2010 International Conference on Communicationsand Mobile Computing, 2010, 209-213 W. Feng et al. / Journal of Information & Computational Science 10:17 (2013) 5457–5466 [11] Bo Han, Weijia Jia, WSN19-14: Efficient construction of weakly-connected dominating set for clustering wireless ad hoc networks, in: Proc. IEEE Global Telecommunications Conference, 2006,1-5 [12] Zhezhuang Xu, Chengnian Long, Cailian Chen, Hybrid clustering and routing strategy with low overhead for wireless sensor networks, in: Proc. IEEE International Conference on Communica-tions, 2010, 1-5 [13] P. Basu, N. Khan, T. D. C. Little, A mobility based metric for clustering in mobile ad hoc networks, in: Proc. International Conference on Distributed Computing Systems Workshop, 2001, 413-418 [14] Min Xiang, Weiren Shi, Changjiang Jiang, Energy efficient clustering algorithm for maximizing lifetime of wireless sensor networks, International Journal AEU of Electronics and Communica-tions, 2009, 289-298 [15] Chor Ping Low, Can Fang, Jim Mee Ng, Efficient load-balanced clustering algorithm for wireless sensor networks, Computer Communications, 31 (2008), 750-759 [16] A. Hussein, S. Yousef, S. Al-khayatt, An efficient weighted distributed clustering algorithm for mobile ad hoc networks, in: Proc. 2010 International Conference on Computer Engineering andSystems, 2010, 221-228 [17] Fatiha Djemili Tolba, Damien Magoni, Pascal Lorenz, Connectivity, energy and mobility driven clustering algorithm for mobile ad hoc networks, in: Proc. IEEE Global TelecommunicationsConference, 2007, 2786-2790 [18] Yan Zhang, Jim Mee Ng, Chor Ping Low, A distributed group mobility adaptive clustering algo- rithm for mobile ad hoc networks, Computer Communications, 32 (2009), 189-202

Source: http://www.joics.com/publishedpapers/2013_10_17_5457_5466.pdf