Comparative Analysis of Methodologies used to Address the MANET Partitioning Problems

Comparative Analysis of Methodologies used to Address the MANET Partitioning Problems

Pradnya Kinge#1,

1 ME Computes Engineering Student, Second Year, Terna Engineering College, Nerul, Navi Mumbai, India

Dr. Lata Ragha#2

2 Prof & HOD, Computer Department

Terna Engineering College, Nerul, Navi Mumbai, India

Abstract: Mobile ad hoc networks (MANETs) are wireless networks without any fixed infrastructure. These networks are highly in use in todays hi-tech environment due to its self organizing and dynamic reconfiguring capability. MANET shows potential of better communication in adverse conditions of emergency scenarios. But due to mobility of nodes it may suffer from network partitioning. We have studied and analysed the various methods for resolving network partitioning problem out of which we found the AMMNET (Autonomous Mobile Mesh Network) to be a promising solution to give better connectivity between mobile nodes in adverse conditions as well.

Keywords: Mobile ad hoc networks, network partitioning, AMMNET, dynamic topology

1. INTRODUCTION

   Wireless technology has been found to be the most powerful transforming technology in this era. Particularly, mobile ad hoc network (MANET) are the most studied networking technology for communication in emergency scenarios like disaster probing, battlefield commanding, crisis management, road traffic monitoring and wild life conservation etc. Here, mobile nodes acts as wireless routers and does the duty of forwarding data packets to their destinations via multi hop relay. As it is infrastructure less network, it is cost effective solution and can be reused and relocated in next situational application.

   The self-directed mobile users move about in MANET causing change in network topology frequently and unpredictably. This condition is detrimental in mission-critical applications like rescue operations and battlefield communications. The grand challenge in designing robust MANET is to minimize the network partitions.

   Researchers have implemented several methods to analyse and reduce this network partitioning problem. Some of these are surveyed here in section II, their comparative analysis is done in section III and we conclude this paper in section IV.

2. TECHNIQUES USED TO RESOLVE NETWORK PARTITIONING PROBLEMS

   1. Introducing Gateway Nodes Between Lower Tier (LT) and Upper Tier (UT) Network

      Jun Sun, Carl Fossa and Thomas Mark have proposed this technique of introducing gateways in MANET [1]. Two types of ad hoc networks are considered as Upper Tier (UT) and Lower Tier (LT). The LT consist of mobile communication node with short radio transmission range while UT consists of communicate on nodes with much longer transmission range than nodes in LT networks. To mitigate the problem of network partitioning problem, a subset of mobile nodes can be collocated with and can be connected to more powerful communication node to form a gateway node. These more powerful gateway nodes has longer radio transmission range and assumed to be connected with each other to form upper tier network. A set of gateway node will improve the connectivity of the LT network through the use of UT network. When partition occurs, to reach destination LT node, LT node can first send the traffic to gateway node which then forwards traffic through UT network to another gateway node. And finally the destination gateway node forwards traffic in its clusters to destination node. In such a way, the LT nodes are always remain connected with each other using gateway nodes.

      In this method, author has assumed that LT nodes are uniformly distributed in a square and gateway nodes are always connected to each other through UT network. The LT network properties are:

      1. Two nodes are said to be connected directly if they are within distance R of each other.

      2. Two nodes A and b are said to be connected if there exist a set of nodes { A1,A2,….,An} such that the pairs (A, A1),(A1,A2),…,(An,B) are directly connected pairs.

      3. A cluster is a set of nodes that are connected to each other.

      4. pg denotes probability that a LT node is also a gateway node.

      The network connectivity is given by:

      Connectivity C = (total no of LT nodes connected to UT) / (total no of LT nodes)

      Once LT network partitioned, LT nodes in a cluster with a gateway node can still communicate with LT nodes in other cluster with gateway nodes, so we need to find out the probability that a node is a gateway node.

      Let the simulation area in L × L size, R is transmission range, and D is density used to describe average number of nodes in unit square.

      Therefore, the number of nodes in square is N = [DL2]Let the area L × L is divided in small squares of d × d and p denote the probability that square d × d has at least 1 point and it is given by:

      When the density is large and the percentage if gateway node is small, a small increase in number of gateway node will cause significant increase in number of connected nodes. However, the number of gateway node increase, the marginal benefit decreases.

      The probability pg that a node is a gateway node can be found by using:

      Where, is a constant.

   2. Satellite Gateways Placement Using KCMBC Algorithm

   M. Hamdi, L. Franck and Xavier Langrange [2] have proposed to use satellite-gateways to improve network connectivity in MANET by using K-hop Compound Metric Based Clustering (KCMBC) algorithm. This algorithm is tested and validated in mobile environment but in dense networks where each node can communicate over multi hop paths with any other node of the network [3]. Authors in [2] has evaluated KCMBC algorithm of k-hop clustering in a scarce-density network where partitioning may occur.

   The KCMBC algorithm works in three steps as:

   1. To assess whether nodes will be able to maintain longer connections with their neighbours and can be eligible for being cluster heads, node metric computation is done using the degree and expiration time.

   2. Cluster head election based on FloodMax and FloodMin protocols[4]

   3. The cluster maintenance where cluster structure is updated according to nodes joining and leaving the cluster.

   Author has used three cases of splitting, merging and node migration as network evolution.

   Splitting and Merging: Splitting occurs when two groups of nodes, initially in same partition , move away from each other and form two different partitions (Figure 1). The nodes, located in a partition where there is no clusterhead, trigger re- clustering. In this context, re-clustering consists in a new clusterhead election from this subset of so called orphaned nodes. According to KCMBC design, if an orphan node

   detects more than d orphan neighbours, all those orphans attempt to trigger a new cluster formation. This rule guarantees that there is at least one clusterhead per partition. However, KCMBC does not detail how to detect the loss of a clusterhead.

   Figure 1: Splitting: Partition 1-bis split in 2 subsequent partitions

   Partitions may also move toward each other to form a single partition (merging). After merging, full network connectivity may be recovered. In this case, due to use of satellite more clustering is not required. The network may also remain partitioned as in Figure 2. In KCMBC, two clusterheads upon their partition merging keep their status, unless they become close neighbours. This is contradictory to a functional requirement in this work which is to have only one clusterhead per parition. One of the clusterhead should therefore resign. According to the value of k chosen above, the diameter of the partition resulting from the merging of two partitions is lower than k. If one of the two clusterheads loses its clusterhead status, previous cluster members are still within k hops from the other clusterhead. In order to manage partition merging, a clusterhead should therefore be able to detect the presence of other clusterheads in the same partition.

   Figure 2: Merging: Partitions 1-b and 1-c merge, but the network is still

   partitioned.

   Each cluster head should able detect the presence of other cluster head in its partition, each cluster member should detect the loss of its cluster heads and orphan nodes should trigger re-clustering.

   C. Introducing Autonomous Mobile Mesh Network

   W. L. Shen, C. S. Chen and K. C. Lin [5] proposed Autonomous Mobile Mesh Network (AMMNET) which is a wireless network with autonomous mobile mesh nodes. These mobile mesh nodes move with their mobile mesh clients and have the intelligence to dynamically adapt the network topology for optimal service.

   AMMNET can forward data for mobile clients along the routing path built by existing ad hoc routing protocols like AODV. AMMNETs have routers with autonomous movement

   capability [6] which are equipped with positioning devices like GPS to provide navigational information for tracking mobile clients. Clients only need to periodically provide beacon messages. Once mobile mesh node receives the beacon message, it can detect the clients within transmission range and can monitor their mobility pattern and move with them to continuous connectivity.

   Figure 3: Topology adaptation of AMMNET under three scenarios

   Figure 4: Fixed grid based square topology under three scenarios

   AMMNETs have three types of routers like intra-group, intergroup and free routers which maintain the changing topology of network.

   Intra-group routers are mesh nodes if it detects at least one client within their radio range and in charge of monitoring movement of clients in their range.

   Intergroup routers act as relay node helping to interconnect with different groups. At least one intergroup is designated as to communicate with any intra-group routers via multi-hop forwarding as bridge router.

   Free router is a mesh node if it neither an intra-group nor intergroup router.

   Figure 5: AMMNET Framework: Routers are partitioned into two groups.

   Intragroup routers support intragroup communication and Intergroup routers prevent network partition.

   Figure 6: Tracking the clients: If the clients move from one router area to another router area as in (a), no action is required. If a client moves out of the current network coverage area as in (b), free routers are triggered to track the

   missing clients.

   For tracking mobile mesh clients, the mobile nodes change their operation based on algorithm 1 [5] as given below.

   Adapting to intra group movement: As group of clients move continuously, their area changes and it must be tracked by intra-group router to dynamically adjust their topology and maintain communication coverage

   Reclaiming redundant routers: While topology changes some intra and inter group routers might become redundant and should be reclaim as free router for future use.

   Interconnecting groups: When clients from one group split into small groups which move in different directions then some free routers are assigned as intergroup router to interconnect these partitioned groups.

   In AMMNET, topology adaptation is done in two phases, viz. Local adaptation and Global Adaptation.

   Local Adaptation: To save intergroup routers, we can replace three independent bridging networks with a star network as shown in Figure 7d. A star topology generally provides shorter relay paths; therefore, it requires fewer intergroup routers. To construct a star topology, let the bridge routers exchange their location information opportunistically, and perform local adaptation as shown in Algorithm 2 [5] when some bridge routers detect that they are close to each other.

   Figure 7: Group partition: When clients are partitioned into several groups and move towards different directions, as in (a) and (b), the intragroup routers, which originally operates as intragroup routers to cover clients, are then switched to act as the intergroup routers that relay data among groups, as in (c). By applying, local adaptation, as in (d), we can eliminate detour paths between groups.

   Global Adaptation: global optimization can be done by Algorithm 2 [5] to construct a star network for all the bridge routers in the AMMNET. But such a star network would be inefficient and need more intergroup routers than necessary if there are more number of groups in network as in Figure8a. Hence, it is proposed to use a hierarchical star topology, which is a near-optimal technique based on R-tree [7] as shown in Algorithm 3 [5] with better overall end-to-end delay. The Rtree is a multidimensional tree structure that aggregates at most M objects into a minimum-bounding rectangle. M of such rectangles is further aggregated into a larger bounding rectangle at the next higher level in the tree. This clustering process is repeated recursively at the higher levels until there is a single minimum-bounding rectangle left at the root of the R-tree. To determine a suitable value of M, we can apply k- means clustering [8] or affinity propagation [9] to cluster the bridge routers in the network.

   Figure 8: Hierarchical topology Construction: Groups can be connected as hierarchical star topology and communicate through shorter relay paths.

   In AMMNET, topology adaptation has done a big contribution in reducing end-to-end delay because of router changing modes of operation and providing better connectivity between moving nodes.

3. COMPARATIVE ANALYSIS OF TECHNIQUES USED FOR RESOLVING NETWORK PARTITION

   PROBLEM

   We have studied the techniques mentioned in section II to resolve network partitioning problem and formed the comparative analysis of these techniques as specified in Table 1 and their advantages and limitations are given in Table 2.

   TABLE I

   COMPARATIVE ANALYSIS OF TECHNIQUES USED TO RESOLVE NETWORK PARTITIONING PROBLEMS

   Techniques Parameters	Introducing gateways	Using Satellite-Gateways	AMMNET
   Methodology Used	Gateways are used to connect LT and UT	K-hop Compound Metric Based Clustering (KCMBC) algorithm is used	Hierarchical Clustering and Topology Adaptation is used
   Partition Controller	Gateway	Satellite-Gateway	Intra and Inter Group Routers
   Model Used With Moving Speed	Static Model	Fire Mobility Model with moving speed of 4.4m/s	Random Way-Point Mobility Model with moving speed 10m/s
   Simulation Area	1 D Grid	–	Grid-Mesh
   Node Density	Less dependent on number of gateways	As node density increases, Satellite-links are need to be used	As node density increases, number of router requirement also increases
   Network Connectivity	Depends on gateway nodes	Since satellite-gateways are used, connectivity is very good	To provide best connectivity, more number of routers are required
   Topology Adaptation	No topology adaptation	No topology adaptation	Local and global topology adaptation done very effectively

   TABLE II

   ADVANTAGES AND LIMITATIONS OF TECHNIQUES USED TO RESOLVE NETWORK PARTITIONING PROBLEMS

   Advantages and Limitations	Advantages	Limitations
   Techniques used
   Introducing gateways	1. Node density is less dependent on number of gateways	1. Here the mobility of nodes is not considered. If mobility is considered then we will know the limitations.
   Introducing Satellite- Gateways	1. Obtains good connectivity due to satellite gateways	1. KCMBC algorithm does not completely fulfil the requirement of cluster maintenance
   AMMNET		1. Does not address the problem of disappearing mobile clients and minimizing routing paths

   1. Full network connectivity

   2. Scalability can be achieved with number of users

   3. The required number of mobile mesh nodes does not increase with increase in population

   4. Provide best network coverage

   5. Topology adaptation is effectively done

4. CONCLUSION

In this paper, we have described the various methodologies used for network partitioning in MANETs. Heterogeneous mobile networks can be connected using gateway nodes and it is found that only a small number of gateway nodes are needed to achieve good network connectivity. In the placement of gateway the satellite links are used to bridge unconnected network partitions. All these methodologies are based on clustering techniques out of which the Autonomous Mobile Mesh Network outperforms well with better mobile client connectivity. AMMNET tracks the users and it dynamically adapts the network topology to support seamlessly for intergroup and intra-group clusters communications. AMNET is scalable with number of users as the mobile mesh node requirement need not increase with increasing user population.

REFERENCES

1. Jun Sun, Carl Fossa, Thomas Mak, On heterogeneous mobile network connectivity: Number of gateway nodes, Proc. The 2011 Military Communications Conference-Track 5

2. M. Hamdi, L. Franck, Xavier Lagrange, Gateway placement in hybrid MANET- Satellite Networks, IEEE Trans. 987-1-4673- 1881-5/12

3. S. Leng, Y. Zhang, H. H. Chen, L. Zhang, and Ke. Liu. A novel

   k-hop compound metric based clustering scheme for ad hoc wireless networks. IEEE Transactions on Wireless Communications, 8(1), 2009

4. A. D. Amis, R. Prakash, T. H.P. Vuong, and D. T. Huynh. Max- min d-cluster formation in wireless ad hoc networks. Nineteenth

   Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2000.

5. Wei-Liang Shen, Chung-Shiuan Chen, Kate Ching-Ju Lin,Autonomous Mobile Mesh Networks, Proc. IEEE Transaction On Mobile Computing, Vol. 13, No. 2, February 2014

6. Quadrocopter LLC, http://quadrocopter.us/, 2013.

7. A. Guttman, R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. ACM SIGMOD Intl Conf. Management of Data (SIGMOD), 1984.

8. A. Savvides, C.-C. Han, and M.B. Strivastava, Dynamic Fine- Grained Localization in Ad-Hoc Networks of Sensors, Proc. ACM MobiCom, 2001.

9. C. Savarese, J.M. Rabaey, and K. Langendoen, Robust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks, Proc. USENIX Ann. Technical Conf., 2002.