GRAPH THEORETIC ROUTING ALGORITHM (GTRA) FOR MOBILE AD-HOC NETWORKS (MANET)

GRAPH THEORETIC ROUTING ALGORITHM (GTRA) FOR MOBILE AD-HOC NETWORKS (MANET)

• 1.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 GRAPH THEORETIC ROUTING ALGORITHM (GTRA) FOR MOBILE AD-HOC NETWORKS (MANET) Kirtikumar K. Patel1,Dhadesugoor.R.Vaman2 Roy G. Perry College of Engineering,Prairie View A & M University,Prairie View, TX77446 1 – Doctoral Candidate; Electrical and Computer Engineering Department 2 – Texas A&M University System Regents Professor, Electrical and Computer Engineering Department Abstract Battlefield theater applications require supporting large number of nodes. It can facilitate many multi-hop paths between each source and destination pairs. For scalability, it is critical that for supporting network centric applications with large set of nodes require hierarchical approach to designing networks. In this research we consider using Mobile Ad Hoc Network (MANET) with multiple clusters. Each cluster supports a few nodes with a cluster head. The intra-cluster connectivity amongst the nodes within the cluster is supported by multi-hop connectivity to ensure handling mobility in such a way that no service disruption can occur. The inter-cluster connectivity is also achieved by multi-hop connectivity. However, for inter-cluster communications, only cluster heads are connected. The selection of intra-cluster communications and inter-cluster communications allow scalability of the network to support multiservices applications end-to-end with a desired Quality of Service (QoS). This paper proposes graph theoretic approach to establish efficient connection between a source and a destination within each cluster in intra-cluster network and between clusters in inter-cluster network. Graph theoretic approach traditionally was applied networks where nodes are static or fixed. In this paper, we have applied the graph theoretic routing to MANET where nodes are mobile. One of the important challenges in MANET is to support an efficient routing algorithm for multi-hop communications across many nodes which are dynamic in nature. However, dynamic behavior of the nodes requires greater understanding of the node degree and mobility at each instance of time in order to maintain end-to-end QoS for multi-service provisioning. This paper demonstrates graph theoretic approach produces an optimum multi-hop connectivity path based on cumulative minimum degree that minimizes the contention and scheduling delay end-to-end. It is applied to both intra-cluster communications as well as inter-cluster communications. The performance shows that having a multi-hop connectivity for intra-cluster communications is more power efficient compared to broadcast of information with maximum power coverage. Each cluster performs similarly and the algorithm is also used for inter-cluster communications. Our simulation results show that the proposed graph theoretic routing approach will reduce the overall delay and improves the physical layer data frame transmission. Keywords Graph Theory, Dynamic Network, MANET, Routing algorithm, QoS assurance DOI:10.5121/jgraphoc.2013.5401 1
• 2.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 1. INTRODUCTION Mobile Ad Hoc Network (MANET) [1] is often characterized as infrastructure-less as it does not use towers or base stations. It can be defined as a system of autonomous mobile (Dynamic) nodes that communicate over wireless links without any preinstalled infrastructure [2]. The network deployment is easy. The network is both power and bandwidth constrained and yet it is expected to provide multi-service provisioning with end-to-end Quality of Service (QoS) provisioning to end users. MANET doesn’t have any dedicated routers to do routing (define a path for packet to transmit from source to destination), Thus each node can work as a relay in the communication path. Each node is able to send and receive data from other nodes in the network [3]. When a node wants to send data to another node which is outside the coverage area (or in a different cluster), then the source node will forward this data to an intermediate node. The intermediate node will forward the data to the next hop or destination node. As long as the cumulative power for multi-hop path is less than the broadcast power, it is feasible to achieve power efficiency [4]. This method also achieves overall throughput efficiency and end-to-end response time. However, since the nodes move freely, maintaining continuous path connectivity imposes additional complexity. MANETs rely on all participating nodes to share the task of routing and forwarding peer traffic. Thus, it is very necessary to develop a routing algorithm which can be efficient in terms of power and bandwidth usage as well as it can improve the overall efficiency of the network to provide quality of service (QoS) assurance for the required application. QoS in MANET is defined as the collective effect of service performance with constraints on delay, jitter, system buffer, network bandwidth, number of hops, power at each node, node mobility in MANET, and packet loss. Also, the performance efficiency achieved with a small set of nodes must be scalable for large set of nodes. Furthermore, in MANET, fast and unpredictable topology changes due to nodes mobility, and channel capacity vary due to environmental effects. Thus, it is more prone to errors compared with that of wired networks. These factors reduce the overall network throughput than equivalent wired network. Thus, supporting media applications such as “video streaming” over MANET is challenging. As infrastructures need to be quickly deployable in applications such as battlefield and homeland security theaters [5, 6, 7, 8, 9]. MANET architectures are still attractive even if complexity to handle mobility is higher. This paper is organized as follows. Section II described background research. Section III describes the system model followed by simulation performance in section IV followed by conclusion in Section V. 2. BACKGROUND A routing protocol is needed to deliver packet from a source to destination based on distance and power availability of the nodes in the network. It selects a path for each source and destination pair based on the system constraints which are extracted from the application needs. International Engineering Task Force (IETF) MANET WG is developing a routing specification [1] which enables scalability to support large number of nodes (hundreds). There are many routing algorithms have been developed by researchers [10, 11, 12 13 14 15, 16]. They tend to have both advantages and limitations that prohibit them to be useful for deployment in a scalable MANET. 2
• 3.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 These routing protocols can be divided in three main sections. (1) Proactive Routing protocols [17-31] (2) Reactive Routing Protocols [32-38] (3) Hybrid routing protocols [39] Each protocol is explained briefly as follows. • Proactive Routing Protocols Proactive routing protocols are table driven protocols; it is not based on flooding network. Routes are setup based on continuous control traffic and maintain all the routes all the time. It maintains the routes to destinations even if they are not needed. Proactive methods maintain routes to all nodes, including nodes to which no packets are sent. Such methods react to topology changes, even if no traffic is affected by the changes. In order to maintain correct route information, a node must periodically send control messages. • Reactive Routing Protocols Reactive routing protocols can dramatically reduce routing overhead because they do not need to search for and maintain the routes on which there is no data traffic. It does not take initiative for finding routes. This property is very appealing in the resource-limited environment. The routes can be established on demand by flooding network with request packets to whole network. • Hybrid Routing Protocols These types of protocols combines the advantages of proactive and of reactive routing. The routing is initially established with some proactively prospected routes and then serves the demand from additionally activated nodes through reactive flooding. The choice for one or the other method requires predetermination for typical cases. In this paper, we concentrated on proactive routing algorithms. Fisheye Routing Scheme (FSR) [17] is a table-driven routing protocol which requires exchanging link information with neighbors to perform routing but in the case, the neighbor is absent, then it’s hard to develop routing in such a scenario. Exchange link information with neighbors increase the memory usage and it increase the overload on MANET network. Optimized Link State routing (OLSR) [18, 19] scheme, each node periodically produce the HELLO message for the neighbors and find the 2-hop connection to destination. This can be applicable for only in dense network environment where it is easy find 2-hop connection to destination. It can not be scalable and it uses much more overhead in routing for MANET. Also it increases traffic at each MPR (Multi-point Relays). Topology broadcast based on reverse path forwarding (TBRPF) [20, 21] and Better Approach to Mobile Ad Hoc Network (BATMAN) [22] routing algorithm update neighbor discovery and update their information if they are up or down and send packets to that node to forward if those nodes are in UP position. But this routing scheme requires periodic information from neighbor nodes which increase usage of bandwidth and memory in the network. Destination Sequenced Distance Vector Routing (DSDV) [23] routing algorithm generates table for next hop, number of hops with their install time and it uses the sequence number generated by destination. The least sequence number 3
• 4.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 route will be selected for routing but this algorithm requires updating its routing tables very frequently. This update process requires bandwidth and power usage even if network is idle. Therefore it is not feasible routing scheme for highly dynamic network. Hierarchical State routing (HSR) [24] is defined based on hierarchy of the network and each node forward their packets via cluster head but this algorithm will increase load on CH and delayed forwarding application in case of highly traffic network. Cluster Gateway Routing protocol (CGSR) [25] develops the routing path using the gateways between two clusters where the hierarchy is maintained by CH. In case of absence of gateway or it moves out of the network, the routing can not be implemented in MANET. Wireless routing protocol (WRP) [26] maintains four tables simultaneously and updates neighbor information by broadcasting the HELLO packets to get information about nodes in the network. Therefore maintaining four tables simultaneously increases management overhead in MANET network. Global State Routing (GSR) [27] is based on exchange information between intermediate nodes using their localized information which requires updating this information and increasing delay in finding neighbor every time thus it’s not feasible for sparse network where nodes are away from each other. This periodical update increases the bandwidth and power usage in the network which reduces the efficiency of the MANET. In addition, Source Tree Adaptive Routing (STAR) [28] is based on links from source to destination and it does not require any periodical update for all nodes in the network which will reduce the routing overhead but this can’t be applicable for dynamic network. In Distance Routing Effect Algorithm for Mobility (DREAM), [29] each node must have knowledge of geographical co-ordinates of other nodes in the network which implement the necessity of GPS in the network. In addition, Meghanathan et al. concentrated on developing graph theory based routing algorithm but they did not consider collision and contention at each node due to its degree [30, 31]. Reactive routing protocols [3238] use flooding technique to find the new route if an existing route breaks and thus it will direct to more packet loss in deciding the on-demand routing algorithm. It uses more network overhead in finding the new route and ad-hoc networks have very limited resources therefore it is not adequate idea to use more resources to find new route even if there is no guarantee that new selected route will be more effective than previous one. These existing routing algorithms are either scalable or power and bandwidth efficient. In wireless communication, link quality is proportional to the transmission power and therefore, for long distance communication we need multi-hop connectivity to save power at each intermediate node. Many researchers provide their multi-hop connectivity based on shortest path and minimum power. Most of researchers considered only the power constraint in developing routing scheme but no one considered the congestion at each node due to receiving packets from different nodes to forward to related destination. As per author’s knowledge, there is no research proposed to date, which is scalable, power and bandwidth efficient to provide QoS assurance for multi-service application based on traffic consideration at each node. In this paper, a novel idea of graph theoretic routing approach is presented, which is efficient in terms of power dissipation, bandwidth usage, and QoS guarantee. In addition, presented idea is also scalable and it can works for large number of nodes to provide video streaming in dynamic network. The proposed scheme considers congestion at each node to develop a routing path from source to destination node and this newly developed routing algorithm will reduces the scheduling time at each node by selecting the least congested node first in routing path, consequently this reduces the overall delay and accomplish the targeted QoS for the application. In addition, it is proactive routing and it saves bandwidth and power at each intermediate node consequently to increase efficiency of the MANET. 4
• 5.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 3. SYSTEM MODEL Our proposed graph theoretic routing approach is intended for application to distributed mobile ad hoc network (MANET) in which whole network can be divided in number of clusters. Each cluster has a defined cluster head which is elected during initialization of each cluster. Cluster head is expected to be vehicle mounted (air or ground). The cluster heads of different cluster heads uses a higher point (and therefore longer reach) inter-cluster backbone network, while radios or nodes communicate with the cluster head with low power intra-cluster communications network. The inter-cluster network operates on a higher bandwidth. Both inter-cluster and intracluster network are mobile where any node and any cluster can move. Each cluster head keeps track of all the nodes within its own cluster and has knowledge of location of its nodes, therefore geography of the cluster. The MANET architecture allows independent management of intracluster routing and inter-cluster routing. The graph theoretic based routing is identical for both intra-cluster and inter-cluster path connectivity. In the intra-cluster routing within each cluster, the routes are established from a given source node to a destination node and between a source node and the cluster head when the destination node is in a different cluster. When nodes are in different clusters, the intra-cluster connectivity is used between the source node and its local cluster head. The cluster head establishes a path between itself and a destination cluster over inter-cluster network while the designation cluster head connects to the destination node within its cluster. While the routing algorithm is identical, path connectivity decisions are independent. The route selection is based on maintaining a low contention using a cumulative minimum degree path end-to-end. In this paper, we focus on intra-cluster routing and path connectivity since the procedure is identical for both intra-cluster and inter-cluster network architecture. We develop a model that selects minimum cumulative degree path between the source and a destination (cluster head), we also showed the theoretical performance of in terms of end-to-end throughput and delay as well as simulation of the network that verifies the performance results. We assume that the background Position, Location and Tracking (PL&T) algorithm that determines the locations of all mobile nodes continuously and the Cluster Head (CH) keeps track of all the PL&Ts of nodes within each cluster [40,41]. Periodically, CH broadcasts the snapshots of all nodes and their PL&T within the cluster. This is the initial step of the algorithm. Furthermore, the following steps are used for route discovery and connectivity: Step 1: Each Node desiring to set up a routing path to a destination Node uses the snap shot at an instance of time to identify all possible multi-hop paths. Step 2: Each node computes the degree of the nodes that are deemed to be in the multi-hop path connection. Step 3: Based on the degree of each node (which is defined as the number of path connections established through that node for all sources), it selects the path that has the cumulative minimum degree. That is the path that will be used for packet transfers from the source. The same is done by all source nodes. This algorithm achieves minimum contention due to minimum degree and also minimum scheduling time for onward packet traffic. In case of tie, when two nodes will have same contention then our proposed algorithm will select the minimum number of hops as an efficient routing path. 5
• 6.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 The functions within the management reference plane are critical to the design of graph theoretic routing. The background process for continuous monitoring of node PL&T in the Cluster Head is accomplished by the integrated zone and P&T triangulation with dynamic references. It uses both physical layer and the IP layer. The cross layer route management is accomplished in the network management plane. The time stamping for the IP packets are done at the physical layer for measurement of range between the target node and the reference node, while the packets delivered for measuring the PL&T are IP layer packets. Zone finding at the “current instance of time” uses a predictive trajectory algorithm based on knowing three good PL&T previous locations of the node and their instances of times. Once the zone is realized, the references that have good PL&Ts are used for determining the target node locations. These references are selected using the zone and maintaining proper geometry such that no angle is less than 30 degrees or greater than 150 degrees in the triangular formation of the references for two dimensional PL&T operation [40, 41]. If the angles violate these rules, the accuracy of prediction of PL&T is compromised. Thus, the zone finding must come first and then triangulation. Once the target nodes’ PL&T is identified, the desired reference node will send the information to the Cluster Head (CH). 3.1. Route Discovery To perform route discovery for packet transmission from source node to destination, following steps will be performed at source node. • • • • • • • Source node will calculate the distance and degree of each node in the cluster based on received snapshot from the cluster head. It will calculate the cost for each route based on scheduling time and contention time. Based on the available data, it will determine intermediate nodes and create the matrix (i.e. Primary Matrix and secondary matrix) for less traffic route (i.e. less contention time + less scheduling time), such that the delay can be reduced in packet transfers. After setting up matrices, source node will send packets to an intermediate node and this intermediate node checks the destination bits of the received packets, if that packet is for it then it will extract the data, else it will forward the received packet towards next intermediate node and eventually to the CH if the packet is deemed to be delivered to a destination in another cluster. If more than one source node is connected to the intermediate node, each of these sources will attempt to send the packet to the same intermediate node where there can be a collision. Collision resolution algorithm allows one successful packet from a source to enter the intermediate node. Therefore, there is a collision resolution time. In addition, the packet scheduling time adds to the end-to-end delay at each intermediate node. The routing algorithm that has both collision and scheduling is described in later sections. Therefore, in our proposed routing scheme, each node can route packet to next available node with less amount of power, thus power can be saved at each intermediate node. Now cluster head will determine the destination address and decide the route based on it for inter cluster communication. If the destination is outside of the cluster then CH will route that received packet to cluster head of the next cluster in the direction of destination based on minimum node cluster and using this approach, packet is transmitted with security to 6
• 7.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 destination without losing any information. We also have secondary route in addition to primary route to provide preemptive solution to packet transfer. 3.2. Route Maintenance Cluster Head will periodically broadcast the snapshots and each node can have different degrees at each instance they move. Thus each source node can check the congestion at other nodes based on next received snapshot from the CH to maintain QoS for desired application. If that congestion increases more at the intermediate node in the predefined path, then switch the existing route to the secondary path. After switching to secondary path, the source node will update the next available less congestion path. Thus secondary matrix becomes primary matrix and new secondary matrix will be generated by the source. In this fashion switching can increase the packet transmission reliability before the existing route breaks or more congested. Furthermore, in this proposed scheme, new routing path is available in hand before existing route breaks to maintain the QoS for the multi-media application. Therefore, this routing scheme is called preemptive routing. Additionally, this is based on table-drive routing scheme and called proactive routing algorithm. 3.3. Node Architecture The Architecture design of each node has two node consists of two sections: • Receive Section (The node can receive packets from other nodes, but not transmit) • Transmit Section (The node can transmit packets to other nodes, but not receive) The default mode for the node is set to “receive mode”. This implies that the antenna will be receiving and not transmitting the information. In the receive mode, the node will receive packets from other nodes which are logically connected. If more than one packet is arriving, the node experiences collision and it is detected within a small amount of time. However, the collision duration is set to a value where the entire packet reception is completed. The node will then resolve the collision and allow one of the collided packets to be transmitted by the designated node. At this stage, the node will go to transmit mode and the initial fields specify the node ID that is allowed to transport the packet and the nodes that sent packets, but collided will have to wait for a random amount of time exceeding the transmissions of two packets and the next reception of the desired node packet. When the node switches from receive mode to transmit mode, the collision resolution information is sent initially along with the transmission of its own packet and the packet that that was received in the previous cycle when it was in receive mode. Then it goes into receive mode for reception of packets. This process is followed by each node in the cluster as they make their own decision on selecting the multi-hop paths. A complete cycle in the node consists of one transmission mode and one receive mode where one or two packets are transmitted during transmission mode and one packet is received in the receive mode. Each node can have its source provide a packet for transmission. 7
• 8.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 Figure. 1 Flow Chart describing the scheduling algorithm 3.4. Nodes In Transmit Mode Or In Receive Mode Along The Multi-Hop Path In MANET, since we assume that each node has only one antenna, the node can either receive or transmit a packet and not both. We set the default of each node such that it is in “receive mode”. When a node has a packet to be transmitted, it goes into “transmit mode” and executes transmission of a packet and it cannot receive any packet at that instance of time. In a multi-hop path, the adjacent intermediate node is set to “receive mode” for it to receive the packet from a source node. When more than one node is sending a packet, the intermediate node experiences a collision. It executes a collision resolution algorithm to select one source node to send a packet. The other source nodes wait for a random amount of time before retrying to send their packets. 3.5. Packet Scheduling After receiving the packet, the intermediate node changes its mode from “receive mode” to “transmit mode” to schedule a transmission of a packet. The node at an instance of time may have a packet from its user and a packet from a neighboring node. It has to schedule a packet to be sent onwards to the next adjacent node selected in the path. It either finds that the packet is destined to its user or to the next adjacent node and decides transmission accordingly. The design encompasses transmitting the packet that was received first from the neighbor and then transmit its own packet if it has a packet ready to be sent. Once this is accomplished, the switches the antenna and RF from “transmit mode” to “receive mode”. By using multi-hop connectivity, each node can route packet to next available node with less amount of power, thus power can be saved at each intermediate node. 3.6. Power Calculation of Routing Path Power required to transmit from the source to destination is calculated based on the distance between them. For a transmission from source node k to destination node j, separated by a distance Rkj, The transmitter power at k is modeled to as equation shown below. 8
• 9.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 P = Rαkj (1) Where α is the channel loss exponent (typically between 2 and 4, depending on the channel medium) [42]. In this research, we assume the value of α = 3. Since the channel can experience interference, choosing a value of ALPHA of 3 may not be exact as it may be increased, but when there is no interference, the value may go down, therefore, we believe it is reasonable to assume an average value of α = 3. 3.7. Theoretical Modelling of A Node We assume that the packet sizes are fixed and therefore the service rate at each node to transmit a packet is fixed. Since more than one node sends packet to an intermediate node and each packet arrival is memory less and has no correlation, the packet arrival rate can be assumed to be “Poisson”. We also assume that there is only one antenna that can go either in transmit mode or in receive mode. Therefore, the node behaviour can be modelled using M/D/1 queuing [43]. However, since we are using RF transmission at each node with only one antenna, the conventional M/D/1 model has to be modified for MANET operation. The modified M/D/1 model with packet contention and packet scheduling is shown in Fig.2. In this model, we assume the following: • • • Arrival rate is Poisson due to memory-less property Service rate is deterministic since packets are of equal size so for this case and we transmit both the packet received from the neighbour and the packet from its own source from each node before relinquishing the transmit mode. Each node is considered to have only one antenna which is a single server. Figure. 2 Modified M/D/1 Queuing Model for a MANET Node 9
• 10.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 4. SIMULATION PERFORMANCE 4.1. Route Selection Based On Proposed Algorithm We used MATLAB to simulate MANET architecture where nodes are randomly distributed within an area of 200 x 200 square meters area and set each node to randomly move. Fig.3 shows the random distribution of nodes in the whole network. Table. 1 SIMULATION PARAMETERS Parameter Values 200*200 meters 50 Random Random Area Number of Nodes Node Placement Strategy Mobility 100 35 29 42 90 70 31 13 38 10 21 60 50 50 25 30 43 14 8 2 40 44 18 12 37 9 34 41 19 80 40 15 46 39 45 30 36 27 33 49 3 32 22 23 17 24 48 5 4 10 0 20 28 7 20 0 1 11 6 10 26 47 20 16 30 40 50 60 70 80 90 100 Figure. 3 Node distribution in Cluster Source and destination nodes keep changing in the overall operation of MANET. Figure 4 illustrates a scenario where node 5 is the source node and node 12 is the destination node. Also, node 12 is in the third circle from node 5 therefore, node 5 needs to select an intermediate node from the middle circle. During the initial conditions, node 5 sends its packets via node 18 because node 18 has lower degree compared to other nodes in the vicinity. Therefore, the path from node 5 to node 12 goes through node 18. Fig 4 shows the direct path with blue line as well as multi-hop path via node 18 via black line (for source node 5 to destination node 12). It also shows that by using a node with the least degree as the intermediate node, the path is able to maintain bounded time for scheduling the packets and forwarding the incoming packet to its final destination. It should be noted that the direct path from node 5 to node 12 would require more power for transmission compared to that of the multi-hop connected path (5-18-12). The intent of using minimum power multi-hop path would increase the network life time. Calculation of the required transmit power is shown in Table 2. Figure 5 shows that node 18 moves from its original place 10
• 11.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 causing disruption of the path connectivity. In this case, the proposed algorithm reroutes the packet exchange with the next available path available prior to the disruption of the path connectivity and therefore, the probability of information loss is significantly reduced. In this case, the source node 5 selects node 8 as the intermediate node which has lesser degree and source node 5 will send packet to destination node 12 via node 8. Thus, it possible to show that packet transmission can be achieved without service interruption while maintaining minimum transmission power (section 3.6). Table. 2 POWER REQUIRED FOR TRANSMISSION ATSOURCE NODE Source Node 5 5 18 5 8 200 Destination Node 12 18 12 8 12 15 180 32 Node location in Y axis 160 Node Location in Different Clusters at initialization 24 39 5 10 17 11 29 9 46 140 14 27 50 38 37 48 120 40 6 4 8 22 36 28 80 42 3 60 25 26 31 40 19 13 41 20 40 49 1 35 20 245 60 80 100 120 140 160 Node location in X axis 21 0 34 33 30 16 20 7 23 43 44 12 47 18 100 0 Required Power (mw) 443.755 207.961 237.029 141.359 325.442 180 200 Figure. 4 Node position at the time of MANET Initialization 11
• 12.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 24 Node Location in Different Clusters after movement 5 200 180 27 14 Node location in Y axis 160 46 39 47 11 40 32 9 15 48 140 8 6 4 37 120 12 42 60 26 40 44 20 18 7 23 25 3 80 21 16 31 30 43 20 40 60 22 34 36 19 45 20 0 17 28 38 100 0 29 10 50 2 80 100 120 140 Node location in X 41 axis 33 1 160 180 49 1335 200 Figure. 5 Node position of all nodes after Movement for the Same Source - Destination pair via different intermediate node. 4.2. Throughput and Delay Computation We considered the following parameter values for packet size and Packet Transmission time in order to compute the throughput and delay: Packet Size = 1500 Bytes Pt = 6 ms We varied the offered traffic from 10 to 1000 packets/sec over channel of 2 Mbit/s. We normalized the parameters with packet transmission rate. Figure 6 shows the normalized throughput vs. the normalized offered traffic. We can see that when the packet generation rate is higher than the packet transmission rate, the node is not capable of forwarding the incoming packets continuously, thereby reducing the throughput. Also, when the packet generation rate is smaller than the packet transmission rate, the packets are delivered continuously, thereby increasing the throughput. Figure 6 illustrates the normalized throughput vs. the normalized offered traffic for different values of the degree of connectivity of each node. 12
• 13.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 Normalized Throughput Vs Offered Traffic 0.16 Degree = Degree = Degree = Degree = Degree = Degree = Degree = 0.14 Normalized Throughput 0.12 0.1 1 2 3 4 5 6 7 0.08 0.06 0.04 0.02 0 0 0.2 0.4 0.6 0.8 1 1.2 Normalized Offered Traffic 1.4 1.6 1.8 Figure. 6 Normalized Throughput Vs Normalized Offered traffic with various degrees at each node. In general, we can write the following equations for the model: Normalized service rate is assumed to be 2, since we assume that both the neighboring node packet as well its own source packet are delivered when the node is set to be in “transmission mode”. The above parameters are also normalized with the packet transmission rate as we develop the theoretical results. In conventional networks, when the utilization factor which is the ratio of the 13
• 14.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 arrival rate and the service rate is less than 1, the node does not experience packet losses. On the other hand, when the ratio exceeds 1, packet losses will occur. In the case of MANET architecture, each node will have one packet selected for transmission from its neighbors and one packet from its source is also transmitted each time the node goes into “transmit” mode. For the proposed multi-hop connectivity, we can write the following set of equations: Figure 7 shows the computed throughput at each node for different values of degrees. It is seen that as the degree of the node increases, the throughput decreases since the contention resolution time increases for packets from multiple sources. Figure 8 shows the delay due to contention resolution and scheduling time at each node. It can be observed that when the node has a higher degree, the overall delay increases, which includes the contention resolution time, packet scheduling time and packet transmission time. 14
• 15.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 -3 1.6 Throughput at Each Node x 10 1.4 Throughput at Each Node 1.2 1 0.8 0.6 0.4 0.2 0 0 5 10 15 20 25 Node 30 35 40 45 50 Figure. 7 Throughput at Each node for a Snapshot Delay at Each node based on Degree 0.7 Contention Resolution Time Scheduling Time Total Delay 0.6 0.5 Delay 0.4 0.3 0.2 0.1 0 0 5 10 15 20 25 Node 30 35 40 45 50 Figure. 8 Delay at Each node based on its degree 5. CONCLUSION We developed graph theoretic based routing algorithm for cluster based MANET that works independently in intra-cluster and inter-cluster network. It is efficient due to the fact that the contention resolution time is the only random parameter and therefore computational complexity is significantly reduced which is directly related to processing power in each radio. The proposed graph theoretic routing algorithm achieves lower packet error rate (PER) and higher throughput with using less power at each intermediate node for the transmitted packets. The fact that the PL&T of nodes is known to each node, it is able to establish an alternate path which will facilitate preemptive switching to an alternate path if any node in the primary path moves beyond the coverage area, thus making it efficient. In this paper, we showed both the theoretical and 15
• 16.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 simulation performance. We modify the basic M/D/1 queuing model to allow contention resolution based on the degree of the node as a suitable application for MANET architecture. Also, the service rate is averaged due to scheduling since at any instance of time, if an external packet is scheduled, there is a potential that its own source packet may also needed to be transmitted. In our simulation, we considered that there is always a source packet along with an external packet. ACKNOWLEDGEMENTS This research work is supported in part by the National Science Foundation NSF 0931679. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the National Science Foundation or the U. S. Government. REFERENCES [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] http://datatracker.ietf.org/wg/manet/charter/ K. Srinivas and A. A. Chari, “Cross layer congestion control in MANETs and current state of art,” International Journal of Computer Applications, vol. 29, no. 6, pp. 28-35, September 2011 Ad Hoc Networking, edited by C. E. Perkins, Addison Wesley, 2001. R. Wattenhofer, L. Li, P. Bahl, and Y. Wang. Distributed topology control for power efficient operation in multihop wireless ad hoc networks. In IEEE INFOCOM 2001, April 2001. Dow, C.R.; Lin, P.J.; Chen, S.C.; Lin, J.H.; Hwang, S.F.; , "A study of recent research trends and experimental guidelines in mobile ad-hoc network," Advanced Information Networking and Applications, 2005. AINA 2005. 19th International Conference on , vol.1, no., pp. 72- 77 vol.1, 28-30 March 2005 G. Aggelou, R. Tafazolli, RDMAR: a bandwidth-efficient routing protocol for mobile ad hoc networks, in: ACM International Workshop on Wireless Mobile Multimedia (WoWMoM), 1999, pp. 26–33. C-Y. Chong, S.P. Kumar Sensor networks: evolution, opportunities, and challenges Proceedings of the IEEE, 91 (8) (2003), pp. 1247–1256 Oh, S.Y.; Lau, D.; Gerla, M.; , "Content Centric Networking in tactical and emergency MANETs," Wireless Days (WD), 2010 IFIP , vol., no., pp.1-5, 20-22 Oct. 2010 D. R. Vaman, “Complexities of ad hoc wireless network architectures and their dual use capabilities for Multi-service QoS assured applications”, Proceedings of IEEE Conference on Enabling Technologies for Smart Appliances, Vol. 1 Key Session ETMA, January 12-14, 2005, Hyderabad, India (Invited Paper) Abolhasan, M., Wysocki, T., & Dutkiewicz, E. (2004). A review of routing protocols for mobile ad hoc networks. Ad hoc networks, 2(1), 1-22. S. R. Das, R. Castaneda and J. Yan, “Simulation Based Performance Evaluation of Mobile, Ad Hoc Network Routing Protocols,” ACM/Baltzer Mobile Networks and Applications (MONET) Journal, July 2000, pages 179-189. J. Broch, D.A. Maltz, D.B. Johnson, Y.-C. Hu, and J. Jetcheva, “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols,” in Proceedings of ACM/IEEE MOBICOM’98, Dallas, TX, Oct. 1998, pp. 85-97. M. Royer and C.-K. Toh, ”A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks”, IEEE Personal Communications Magazine, April 1999, pp. 46-55. Iwata, C.-C. Chiang, G. Pei, M. Gerla, and T.-W. Chen, ”Scalable Routing Strategies for Ad-hoc Wireless Networks,” IEEE Journal on Selected Areas in Communications, Aug. 1999, pp. 1369-1379. 16
• 17.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 [15] S.-J. Lee, C.-K. Toh, and M. Gerla, ”Performance Evaluation of Table- Driven and On-Demand Ad Hoc Routing Protocols,” in Proceedings of IEEE PIMRC’99, Osaka, Japan, Sep. 1999, pp. 297-301. [16] Bellman-Ford: R.E. Bellman, Dynamic Programming, Princeton University Press, Princeton, NJ, 1957. [17] G. Pei, M. Gerla, and T.-W. Chen,”Fisheye State Routing: A Routing Scheme for Ad Hoc Wireless Networks,” in Proceedings of ICC 2000, New Orleans, LA, Jun. 2000 [18] P. Jacquet, P. Muhlethaler, A. Qayyum, A. Laouiti, L. Viennot and T. Clausen, ”Optimized Link State Routing Protocol,” draft-ietf-manet-olsr- 05.txt, Internet Draft, IETF MANET Working Group, Nov. 2000. [19] T. Clausen and P. Jacquet. Optimized Link State Routing Protocol (OLSR). IETF, October 2003. RFC 3626. [20] R. G. Ogier, F. L. Templin, B. Bellur and M. G. Lewis, “Topology Broadcast based on Reverse-Path Forwarding (TBRPF),” draft-ietf-manettbrpf 05.txt, INTERNET-DRAFT, MANET Working Group, Mar. 2002. [21] B. Bellur, R.G. Ogier, F.L Templin, Topology broadcast based on reverse-path forwarding routing protocol (tbrpf), in: Internet Draft, draft-ietf-manet-tbrpf-06.txt, work in progress, 2003. [22] Neumann, C. Aichele, M. Lindner, and S. Wunderlich, Better Approach To Mobile Ad-hoc Networking (B.A.T.M.A.N.), Internet-Draft, pages 1-24, 2008. Network Working Group. [23] E. Perkins and P. Bhagwat, “Highly dynamic destination sequenced distance-vector routing (DSDV) for mobile computers“, Computer Communications Review, pp. 234-244, Oct.1994. [24] K.K. Kasera, R. Ramanathan, A location management protocol for hierarchically organised multihop mobile wireless networks, in: Proceedings of the IEEE ICUPC_97, San Diego, CA, October 1997, pp. 158–162. [25] C.-C. Chiang, Routing in clustered multihop mobile wireless networks with fading channel, in: Proceedings of IEEE SICON, April 1997, pp. 197–211. [26] G. Pei, M. Gerla, X. Hong, and C. -C. Chiang, ”A Wireless Hierarchical Routing Protocol with Group Mobility,” in Proceedings of IEEE WCNC’99, New Orleans, LA, Sept. 1999. [27] T.-W. Chen, M. Gerla, Global state routing: a new routing scheme for ad-hoc wireless networks, in: Proceedings of the IEEE ICC, 1998. [28] J. Garcia-Luna-Aceves, C. Marcelo Spohn, Source-tree routing in wireless networks, in: Proceedings of the Seventh Annual International Conference on Network Protocols Toronto, Canada, October 1999, p. 273 [29]S. Basagni, I. Chlamtac, V. R. Syrotiuk, and B. A. Woodward, ”A distance routing effect algorithm for mobility (DREAM),” in ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom98), 1998,pages 76 - 84. [30] M. A. Rajan, M. G. Chandra, L. C. Reddy and P. Hiremath, “Concepts of Graph Theory Relevant to Ad-hoc Networks”. International Journal of Computers, Communications & Control, Vol. 3, No.Suppl, pp. 465-469, 2008. [31] Meghanathan, Natarajan, “Applications of Graph Theory Algorithms in Mobile Ad hoc Networks”. [32] E. Perkins and E. M. Royer, “Ad-hoc on-demand distance vector routing,” in Proc. IEEE Workshop on Mobile Comp. Sys.and Apps., Feb. 1999, pp. 90-100. [33] B. Johnson and D. A. Maltz, “Dynamic source routing in ad hoc wireless networks,” in Mobile Computing, 1996, pp. 153-181. [34] C.-K. Toh, “Associativity-Based Routing For Ad Hoc Mobile Networks,” Wireless Personal Communications Journal, Special Issue on Mobile Networking and Computing Systems, Kluwer Academic Publishers, vol. 4, no. 2, Mar. 1997, pp. 103-139. [35] Park V. and S. Corson, 2001. Temporary-ordered Routing Algorithm (TORA). Internet Draft, draftietf-manettora-spec-04.txt. [36] Y. Ko and N. H. Vaidya, “Location-aided routing (LAR) in mobile ad hoc networks,” Wireless Networks, 6(4), July 2000, pp. 307-321. 17
• 18.
  International journal onapplications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.5, No.4, December 2013 [37] J. Raju, J. Garcia-Luna-Aceves, A new approach to on demand loop-free multipath routing, in: Proceedings of the 8th Annual IEEE International Conference on Computer Communications and Networks (ICCCN), Boston, MA, October 1999, pp. 522–527. [38] MALEKI, M., DANTU, K., AND PEDRAM, M. 2003. Lifetime prediction routing in mobile ad hoc networks. In Wireless Communication and Networking Conference. New Orleans, LA. USA [39] Z.J. Haas and M.R. Pearlman, ”The Performance of Query Control Schemes for the Zone Routing Protocol,” ACM/IEEE Transactions on Networking, vol. 9, no. 4, August 2001, pp. 427-438. [40] D.R. Vaman, N. Shakhakarmi, “Integrated Key based Strict Friendliness Verification of Neighbors in MANET, IEEE International Conference On Security Science and Technology, Jan 22, ICSST 2011. [41] N. Shakhakarmi, D. R. Vaman, “Distributed Position Localization and Tracking (DPLT) of Malicious Nodes in Cluster Based Mobile Ad hoc Networks (MANET)”, WSEAS Transactions in Communications, ISSN: 1109-2742, Issue 11, Volume 9, November 2010. [42] Marks, R.J.; Das, A.K.; El-Sharkawi, M.; Arabshahi, P.; Gray, A., "Minimum power broadcast trees for wireless networks: optimizing using the viability lemma," Circuits and Systems, 2002. ISCAS 2002. IEEE International Symposium on , vol.1, no., pp.I-273,I-276 vol.1, 2002 [43] Kleinrock, Leonard (1975). Queuing Systems Volume 1: Theory. Authors Kirtikumar K. Patel received the B.S. degree in Electronics and Communication Engineering from Hemchandracharya North Gujarat University, India, and M.S. degree in Electrical Engineering from Lamar University, United States of America in 2006 and 2008, respectively. He is currently working towards his PhD. degree in the Department of Electrical and Computer Engineering at the Prairie View A&M University, a member of the Texas A&M University System. His current research interests include mobile ad hoc network, routing algorithms, graph theory applications and contention resolution algorithms. Dhadesugoor R. Vaman is Texas Instrument Endowed Chair Professor and Founding Director of ARO Center for Battlefield Communications (CeBCom) Research, ECE Department, Prairie View A&M University (PVAMU). He has more than 38 years of research experience in telecommunications and networking area. Currently, he has been working on the control based mobile ad hoc and sensor networks with emphasis on achieving bandwidth efficiency using KV transform coding; integrated power control, scheduling and routing in cluster based network architecture; QoS assurance for multi-service applications; and efficient network management. Prior to joining PVAMU, Dr. Vaman was the CEO of Megaxess (now restructured as MXC) which developed a business ISP product to offer differentiated QoS assured multiservices with dynamic bandwidth management and successfully deployed in several ISPs. Prior to being a CEO, Dr. Vaman was a Professor of EECS and founding Director of Advanced Telecommunications Institute, Stevens Institute of Technology (1984-1998); Member, Technology Staff in COMSAT (Currently Lockheed Martin) Laboratories (1981-84) and Network Analysis Corporation (CONTEL)(1979-81); Research Associate in Communications Laboratory, The City College of New York (1974-79); and Systems Engineer in Space Applications Center (Indian Space Research Organization) (1971-1974). He was also the Chairman of IEEE 802.9 ISLAN Standards Committee and made numerous technical contributions and produced 4 standards. Dr. Vaman has published over 200 papers in journals and conferences; widely lectured nationally and internationally; has been a key note speaker in many IEEE and other conferences, and industry forums. He has received numerous awards and patents, and many of his innovations have been successfully transferred to industry for developing commercial products. 18