Health Articles

 

Mobility-based d-hop clustering algorithm for mobile ad hoc networks

Mobility-based d-Hop Clustering Algorithm for Mobile Ad Hoc Networks
Winston K.G. Seah1,2 {stuerii, winston}@i2r.a-star.edu.sg 1Institute for Infocomm Research 2Department of Computer Science Agency for Science Technology and Research School of Computing National University of Singapore Abstract- This paper presents a mobility-based d-hop effective topology [1]. By organizing nodes into clusters,
clustering algorithm (MobDHop), which forms variable-
topology information can be aggregated. This is because the diameter clusters based on node mobility pattern in
number of nodes of a cluster is smaller then the number of nodes MANETs. We introduce a new metric to measure the
of the entire network. Each node only stores fraction of the total variation of distance between nodes over time in order to
network routing information. Therefore, the number of routing estimate the relative mobility of two nodes. We also estimate
entries and the exchanges of routing information between nodes the stability of clusters based on relative mobility of cluster
are reduced[3]. Apart from making large networks seem smaller, members. Unlike other clustering algorithms, the diameter
clustering in MANETs also makes dynamic topology appear less of clusters is not restricted to two hops. Instead, the diameter
dynamic by considering cluster stability when they form[2]. of clusters is flexible and determined by the stability of
Based on this criterion, all cluster members that move in a clusters. Nodes which have similar moving pattern are
similar pattern remain in the same cluster throughout the entire grouped into one cluster. The simulation results show that
communication session. By doing this, the topology within a MobDHop has stable performance in randomly generated
cluster is less dynamic. Hence, the corresponding network state scenarios. It forms lesser clusters than Lowest-ID and
information is less variable[3]. This minimizes link breakage MOBIC algorithm in the same scenario. In conclusion,
and packet loss. MobDHop can be used to provide an underlying hierarchical
Clustering algorithm in MANETs should be able to routing structure to address the scalability of routing
maintain its cluster structure as stable as possible while the protocol in large MANETs.
topology changes[1]. This is to avoid prohibitive overhead incurred during clusterhead changes. In this paper, we propose a Keywords: cluster, mobility-based clustering, mobile ad hoc
mobility-based d-hop clustering algorithm (MobDHop) that networks, MANET, mobility pattern.
forms d-hop clusters based on a mobility metric suggested by Basu et al.[8]. The formation of clusters is determined by the mobility pattern of nodes to ensure maximum cluster stability. 1. Introduction
We observe that mobile users in MANET may move in groups. This is known as group mobility[10]. Mobile hosts may be Mobile ad hoc network (MANET) consists of a number of involved in team collaborations or activities. They may have a wireless hosts that communicate with each other through multi- common mission (save victims that are trapped in collapsed hop wireless links in the absence of fixed infrastructure. They building), perform similar tasks (gather information of threats in can be formed and deformed spontaneously at anytime and a battlefield) or move in the same direction (rescue team anywhere. Some envisioned MANETs, such as mobile military designated to move towards east side of disaster struck area). networks or future commercial networks may be relatively large Therefore, our algorithm attempts to capture group mobility and (e.g. hundreds or possibly thousands of nodes per autonomous uses this information to form more stable clusters. system). The need to store complete routing details for an entire MobDHop, a distributed algorithm, dynamically forms network topology raises scalability issue. The flat hierarchy stable clusters which can serve as underlying routing adopted by most of the existing MANET routing protocols may architecture. First, MobDHop forms non-overlapping two-hop not be able to support the routing function efficiently since their cluster like other clustering algorithms. Next, these clusters routing tables could grow to an immense size if each node had a initiate a merging process among each other if they could listen complete view of the network topology. Therefore, clustering to one another through gateways. The merging process will only algorithms are proposed in MANETs to address scalability issue be successful if the newly formed cluster achieves a required by providing a hierarchical network structure for routing. level of stability. As mentioned, most of the existing clustering Clustering algorithms can be performed dynamically to algorithms form two-hop clusters which may not be too useful in adapt to node mobility[2]. MANET is dynamically organized very large MANETs. Therefore, MobDHop is designed to form into groups called clusters to maintain a relatively stable d-hop clusters that are more flexible in cluster diameter. The used to compute the relative mobility between neighboring diameter of clusters is adaptive to the mobility pattern of nodes, which determines the ALM of each node. network nodes. MobDHop is simple and incurs as low overhead All of the above algorithms create two-hop clusters in as possible. Information exchange during the formation of MANETs. They are more suitable for dense MANETs in which clusters, clusterhead changes and clusterhead handovers are kept most of the nodes are within direct transmission range of to minimum. The remainder of this paper is organized as follows: clusterheads. However, these algorithms may form a large We present an overview of clustering algorithms proposed for number of clusters in relatively large and sparse MANETs. MANETs in Section 2. Next, details of MobDHop are presented Therefore, two-hop clusters may not be able to achieve effective in Section 3. Section 4 discusses our simulation results and topology aggregation. Amis et al. generalized the clustering analysis. Finally, we conclude in Section 5. heuristics so that an ordinary node can be at most d hops away from its clusterhead[9]. This algorithm allows more control and 2. Related Work
flexibility in the determination of clusterhead density. However, clusters are formed heuristically without taking node mobility A number of clustering algorithms have been proposed in and their mobility pattern into consideration. McDonald and literature such as Linked Cluster Algorithm (LCA)[4], Lowest- Znati[2] designed a (α,t)-clustering algorithm that adaptively ID Algorithm (L-ID)[5], Maximum Connectivity Clustering changes its clustering criteria based on the current node mobility. (MCC)[6], Least Clusterhead Change Algorithm (LCC)[7], and This algorithm determines cluster membership according to a LCA[4] was developed for packet radio cluster's internal path availability between all cluster members networks and intended to be used with small networks of less than 100 nodes. LCA organizes nodes into clusters on the basis of node proximity. Each cluster has a clusterhead, and all nodes 3.Mobility-based d-hop Clustering Algorithm
within a cluster are within direct transmission range of the clusterhead. Gateways are nodes that are located in the A successful dynamic clustering algorithm should achieve a overlapping region between clusters. Two clusters communicate stable cluster topology with minimal communications overhead with each other via gateways. Pair of nodes can act as gateways and computational complexity [2]. The efficiency of the if there are no nodes in the overlapping region. LCA was later algorithm is also measured by the number of clusters formed revised[5] to reduce the number of clusterheads. In the revised [11]. Therefore, the main design goals of our clustering version of LCA, a node is said to be covered if it is in the 1-hop algorithm are as follows: neighborhood of a node that has declared itself as clusterhead. A 1. The algorithm minimizes the number of clusters by node declares itself to be a clusterhead if it has the lowest id considering group mobility pattern. among the non-covered nodes in its 1-hop neighborhood, known 2. The algorithm must be distributed and executed as Lowest-ID algorithm. Parekh suggested MCC in which the clusterhead election is 3. The algorithm must incur minimal clustering overhead, be it based on degree of connectivity instead of node id[6]. A node is cluster formation or maintenance overhead. elected as a clusterhead if it is the highest connected node in all 4. Network-wide flooding must be avoided. of the uncovered neighboring nodes. This algorithm suffers from 5. Optimal clustering may not be achieved, but the algorithm dynamic network topology, which triggers frequent changes of must be able to form stable clusters should any exists. clusterheads. Frequent cluster reconfiguration and clusterhead MobDHop, we first make a few
reselection incur prohibitive overhead. assumptions on the network: LCC[7] is designed to minimize clusterhead changes. A 1. Two nodes are connected by bi-directional link (symmetric clusterhead change occurs when two clusterheads come within range of each other, or a node becomes disconnected from any 2. The network is not partitioned. cluster. When two clusterheads come into direct contact, one of 3. Each node can measure its received signal strength. the clusterheads will give up its role. Some of the nodes in one cluster may not be members of the other clusterhead's cluster. Through periodic beaconing or hello messages used in some Therefore, one or more of those nodes must become a routing protocols, a mobile node can estimate its distance to its clusterhead. Such changes propagate across the network, causing neighbor based on the measured received signal strength from a rippling effect of clusterhead changes. that particular neighbor. In the Friss transmission equation, the Basu et al.[8] propose a weight-based clustering algorithm, received power over a point-to-point radio link is given by: MOBIC, which is similar to L-ID. Instead of node ID, MOBIC uses a new mobility metric, Aggregate Local Mobility (ALM), P = P *G *G * to elect a clusterhead. The ratio between the received power (4 *π * d ) levels of successive transmissions between a pair of nodes is where Pr = received power, Pt = transmitted power, Gt = antenna is larger than the old distance, the neighboring node is moving gain of the transmitter, Gr = antenna gain of the receiver, λ = away from the measuring node. We group the nodes into two- wavelength (c/f), and d = distance. hop clusters based on their relative mobility in the first stage. This shows the familiar inverse square-law dependence of Next, we expand the cluster by merging individual nodes with received power with distance, i.e. Pr α 1/d2. Therefore, we derive two-hop clusters or merging two or more two-hop clusters based the estimated distance between two nodes from the above on the previously described metric, i.e. the variation of estimated equation based on received signal strength. In real world distance between gateway nodes. Before introducing MobDHop, scenario, it may not be possible to obtain an exact calculation of we give a brief introduction to different terms and metrics used the physical distance between two nodes from the measured signal strength. However, MobDHop does not depend on accurate estimation of distances between two nodes to operate 3.1 Preliminary Concepts
correctly. Instead, we observe the variation of the estimated distances (in other words, fluctuation of the received signal A node may become a clusterhead if it is found to be
strength) between two nodes over time. From the series of the most stable node among its neighborhood. Otherwise, it is an distance variations, we use statistical testing to predict relative ordinary member of at most one cluster. When all nodes first
mobility pattern between two nodes. We intuitively conclude enter the network, they are in non-clustered state. A node that is
that two nodes are stably-connected if the received signal able to listen to transmissions from another node which is in strength between them varies negligibly over time. If two nodes different cluster is known as a gateway. We formally define the
are moving together at a similar speed towards the same following terms: (1) estimated distance between nodes, (2) direction, the variation of their received signal strength should relative mobility between nodes, (3) stably-connected node pair, be very small. This serves as one of the metrics we used to group (4) local stability, and (5) estimated mean distance. the nodes into its respective cluster. Definition 1: Estimated distance between node A and B, E[DAB],
Based on the above justification, we will not use complex is calculated as below.Please note that this formula is not aimed calculation in MobDHop in order to obtain accurate physical to obtain exact physical distance between two nodes. Instead, it distance. Instead we use the received signal strength measured at is an approximation to show the "closeness" of two nodes. the arrival of every packet to estimate the distance from one node to its neighbor node. The stronger the received signal strength, the closer the neighbor node. It is important to know that the "closeness" between two nodes is not necessarily measured by their absolute or physical distance. For example, Definition 2: Relative mobility between nodes A and B,
node A may be very close to node B. However, it runs out of indicates whether they are moving away from each other, energy and transmits packets at lower power. In this case, it moving closer to each other or maintain the same distance from behaves like a distanced node from node A. Therefore, absolute each other. To calculate relative mobility, we compute the distance may not be useful in predicting link stability in this case. difference of the distance at time, t and the distance at time, t - 1. Relative mobility at node A with respect to node B at t is calculated as follows: Relative mobility of clusterhead wrt node B is Definition 3: The variation of E[DAB] over a time period, T,
is defined as the changes of estimated distances between node A and B over a predefine time period. Let's consider node A as measuring node. Node A has a series of estimated distance Relative mobility of values from node B measured at certain time interval for n times, clusterhead wrt node B is E[DAB]={E[DAB]t, t = 0, 1, 2, … , n}. Therefore we calculate AB as the standard deviation of distance variation as follows: VD = σ ( [ E D ] − [ Figure 1. Relative Mobility
E D ] − E[D ] , . , [ E D ] − [ Measured signal strength of successive packets is used to estimate the relative mobility between two nodes. We calculate Definition 4: Local stability at node A, StA, represents the degree
the difference of estimated distance from a neighboring node at of stability at node A with respect to all its neighbors. Local two successive time moments. The difference indicates the pair-wise relative mobility as shown in Figure 1. If the new distance stability is the standard deviation of relative mobility values of the most stable node among its neighborhood. Hence, it has the all neighbors. Therefore it is calculated as follows: greatest potential to be a real group leader in real life scenarios. 3.3 Merging Stage

Definition 5: Estimated Mean Distance (EMD) for cluster, C1,
After the discovery stage, all nodes are covered by two-hop indicates the mean distance from each neighbor to the clusters. There are two cases that may initiate a merging process: clusterhead, CH1 of cluster, C1. The EMD is calculated as a) A non-clustered node requests to join the neighboring b) Two neighboring gateways request to merge their clusters. ], E[D ], ., E[D In the first case, a non-clustered node initiates the merging process. In the second case, two neighboring gateway nodes, G1 3.2 Discovery Stage
and G2 from C1 and C2 respectively, which are in transmission This is an initial setup stage for two-hop clusters when the range of each other, initiate the merging process. Nodes network is first initialized. All nodes periodically broadcast initiating merging process start collecting samples for estimated Hello messages, including their local stability value (initialized distance between them. From the samples of estimated distances, to infinity at the beginning of operation). Each node measures they compute mean of estimated distance, E[DG1G2], and the received signal strength of every received Hello message and variation of distance over time, VDG1G2. Apart from this, they estimates the distance with each neighbor. After receiving at also calculate their relative mobility with respect to each other. least two successive Hello messages, each node calculates To be successfully merged, both gateway nodes must fulfill the relative mobility with its neighbor at time t using equation in following two criteria at the end of sampling period, TS: Definition 3. After a discovery period, TD, each node assumes
1) VDG1G2 ≤ min{StC1, StC2}, and that it has the complete knowledge of its neighborhood. Then it 2) µ(E[DG1G2]) ≤ max{EMDC1, EMDC2} computes its local stability value using equation in Definition 4.
Then, it broadcasts Hello messages with the computed local The first criterion ensures that the variation of estimated stability value. Thus, each node knows the local stability of their distance between two merging nodes is less than or equal to the neighbors. After an assignment period, T minimum value of group stability among two clusters. This A, each node compares its own local stability value with those of its neighbors. If a node indicates that the link between two nodes is at least as stable as has the lowest value of local stability among all its neighbors, it other links in one of the clusters which is more stable. The assumes the status of a clusterhead. Its local stability value second criterion tells us that the distance between two nodes becomes group stability (GS). conforms to the distance characteristic of the larger cluster. Then, the clusterhead computes EMD with respect to all Therefore both clusters have higher probability to be originated cluster members (one-hop neighbors of clusterhead). The EMD from the same group of real life situation as suggested in RPGM. is computed to capture another characteristic of the network if In most of the group communication applications, members the nodes are moving in groups. This characteristic is suggested belong to the same group tend to remain in each other by Reference Point Group Mobility (RPGM) model[10]. The transmission ranges over time by maintaining a constant distance RPGM model suggested that a group center is used to from group leader. characterize the movement of its corresponding group members, including their direction, speed, and distance from group center. 3.4 Maintaining Stage
This is similar to the real life group communication in which We first consider two cases that may cause topology group leader guides the movement of its group members. changes in MANET and thus invoke cluster maintenance stage: Therefore, group members will not move too far away from the group leader. Their movement area is usually bounded. EMD is 1) A node switches on and joins the network. used as one of the metrics in the merging process to allow a new 2) A node switches off and leaves the network. cluster member to join the cluster. When a node switches on, it will initiate the merging If a cluster member is able to hear hello messages from process in the same manner as described in Section 3.3. It another node from another cluster, it assumes the role of a checks all the links with its neighboring nodes and collects gateway. Otherwise, it declares itself to be a cluster member. If samples for estimated distance from each neighbor. Then it two neighboring nodes in non-clustered state have the same computes the variation of distance over time, VD, with each value of local stability, the clusterhead assignment is deferred neighbor. At the end of sampling period, it chooses the neighbor for a back-off period. The local stability will be recomputed at with lowest VD, and joins its cluster. the end of back-off period. This is to ensure the clusterhead is When a node switches off and the node is a clusterhead, this will cause its cluster members to lose the clusterhead and fail to receive cluster advertisements for a predefined period. The neighbors. Therefore, clusters are less dynamic and the number immediate neighbors of the clusterhead will initiate the of clusterheads changes also decreases. discovery process as described in Section 3.2 in which a new We also compare the performance of MobDHop with the clusterhead will be elected. The information of the new Lowest-ID algorithm and MOBIC in a 50-node MANET under clusterhead will then be propagated to other cluster members, constant mobility (20m/sec). In Figure 4, we note that there is a which are further away from it. However, during the clusterhead small difference between Lowest-ID and MOBIC with respect to election period, other cluster members which are at least 2 hops the average number of clusters formed. This is because both away from the old clusterhead may detect the loss of clusterhead algorithms are variations of a local weight based clustering and decide to join neighboring cluster if the merging criteria technique that forms two-hop clusters. MobDHop forms less specified in Section 3.3 can be met. If a node found itself in non- clusters in the similar scenario since it forms variable-diameter clustered state, it will initiate merging with neighboring clusters clusters based on node mobility pattern. This is one of the whenever possible. Otherwise, it will declare itself to be a desirable properties in clustering algorithm especially when the clusterhead of a one-node cluster. From time to time, it will try scalability is the main concern. to merge with other clusters if possible. Table 1. Simulation Parameters for MobDHop
4. Simulation Results and Discussions
Parameter Meaning
The performance of MobDHop is evaluated via simulations Simulation
using NS-2 with CMU wireless extensions [12]. The scenarios were generated with input parameters as listed in Table 1, such as network size, speed, transmission range, broadcast interval, MaxSpeed Maximum clusterhead contention interval and simulation time. The movement of mobile nodes is randomly generated and Transmission Range continuous within the whole simulation period. We implemented MobDHop as described in Section 3. The local stability value, Interval 0.75-1.25 group stability value, node status, node clusterhead id, and Discovery Interval cluster EMD are added into "Hello" messages. "Hello" Assignment Interval messages have been widely used in on-demand routing protocols to maintain neighbor connectivity. Each node broadcasts "Hello" Contention Period messages at certain broadcast interval to tell the neighbors of its existence. MobDHop does not use additional control packets for information exchange to form or maintain clusters. Figure 2 and 3 show the performance of MobDHop for MANETs which are different in number of nodes and transmission ranges. The mobile nodes are moving continuously at 20m/sec throughout the entire network simulation period (300 seconds). We note that the average number of clusters is relatively high when the transmission range is small (10 - 20 m). For small ranges, most nodes tend to be out of each other's transmission range and the network may become disconnected. Therefore, most nodes form one-node cluster, which only consists of itself. Due to our algorithm design, which require one-node clusters to attempt to merge with neighboring clusters whenever possible, clusterhead will switch their status to non-clustered state in order to merge with their neighbors (if any). This causes the high rate of clusterhead changes in disconnected networks. However, we argue that this will not affect network performance as this will only occur when the network is Transmission Range (m) disconnected (A disconnected network is unable to function too). When transmission range increases, more nodes can hear Figure 2. Average number of clusters
each other. The average number of clusters formed decreases and the clusters become larger in size. Since the transmission range is large, mobile nodes tend to remain in the range of their same cluster. As long as the nodes are moving towards the same direction in a stable behavior, they can be grouped into the same cluster. This is justified by the assumption of group movement, in which members of a group tend to move towards a similar destination in real-life scenarios. We have simulated MobDHop and presented some preliminary results in Section 4. In conclusion, the performance of MobDHop is comparable to other existing algorithms. It also creates lesser and more stable clusters in order to achieve high scalability. The clusterhead change is relatively low. However, we will perform extensive simulation-based comparisons between existing clustering algorithms and MobDHop to evaluate different aspects of performance such as cluster stability, overhead consumption, latency and others. We may use Transmission Range (m) other mobility models which are more realistic such as RPGM in Number of Clusterhead Changes our simulations. Finally, designing a multicast routing protocol which can work on-top of MobDHop in order to address Figure 3. Number of clusterhead changes
scalability issues in MANET is part of our ongoing research. References:
[1] C. R. Lin and M. Gerla. Adaptive clustering for mobile wireless networks. IEEE Journal on Selected Areas in Communications, 15(7):1265-1275, Sept. 1997. [2] A. B. McDonald and T. F. Znati. A mobility-based framework for adaptive clustering in wireless ad hoc networks. IEEE Journal on Selected Areas in Communications, 17(8):1466- 1486, Aug. 1999. [3] C. E. Perkins, editor. Ad Hoc Networking. Addison-Wesley, [4] D. J. Baker and A. Ephremides. The architectural organization of a mobile radio network via a distributed algorithm. IEEE Transactions on Communications, 29(11):1694-1701, 1981. Transmission Range (m) [5] A. Ephremides, J. Wieselthier, and D. Baker. A design concept for reliable mobile radio network with frequency hopping Figure 4. Comparisons between different clustering
signaling. In Proceedings of IEEE 75, pages 56-73, 1987. algorithms in a 50-node MANET.
[6] A. K. Parekh. Selecting routers in ad hoc wireless networks. In ITS, 1994. [7] C.-C. Chiang, H.-K. Wu, W. Liu, and M. Gerla. Routing in 5. Conclusions
clustered multihop, mobile wireless networks with fading Clustering can provide large-scale MANETs with a channel. IEEE Singapore International Conference on Networks (SICON) hierarchical network structure to facilitate routing operations. In , pages 197-211, Apr. 1997. [8] P. Basu, N. Khan, and T. D. C. Little. Mobility based metric this paper, we proposed a distributed clustering algorithm which for clustering in mobile ad hoc networks. Workshop on forms variable-diameter clusters that may change its diameter Distributed Computing Systems, pages 413-418, 2001. adaptively with respect to mobile nodes' moving patterns. [9] A. D. Amis, R. Prakash, T. H. P. Vuong, and D. T. Huynh. Inspired by Basu et. al[8], we proposed two mobility metrics Max-min d-cluster formation in wireless ad hoc networks. In based on the relative mobility concept: (1) variation of estimated Proceedings of IEEE INFOCOM '00, Vol. 1, pages 32-41, Mar. distance between nodes over time and (2) estimated mean distance for cluster, in order to measure the stability of a cluster. [10] X. Hong, M. Gerla, G. Pei, and C. Chiang. A group mobility These metrics are used to decide cluster memberships. Therefore, model for ad hoc wireless networks. In Proceedings of ACM/IEEE MSWiM, Seattle, WA, Aug.1999. the formation of clusters in MobDHop is determined by the [11] F. G. Nocetti, J. S. Gonzalez, I. Stojmenovic, "Connectivity mobility pattern of nodes to ensure maximum cluster stability. based k-hop clustering in wireless networks," To achieve the desired scalability, MobDHop forms Telecommunication Systems 22 (2003) 1-4, 205-220, 2003. variable-diameter clusters, which allows cluster members to be [12] K. Fall, and K. Varadhan, "The ns Manual," more than two hops away from their clusterhead. The diameter http://www.isi.edu/nsnam/ns/, 2002. of clusters is dependent on the mobility behavior of nodes in the

Source: http://homepages.ecs.vuw.ac.nz/~winston/papers/WCNC2004-MobDHop.pdf