Many routing algorithms were proposed for mobile ad hoc network (MANET). They can be classified into two categories: connection-oriented and connectionless. Their performance is usually limited under high mobility or various node densities. A connectionless algorithm even encounter a local maximum problem (also called void problem) under low node density. The problem causes a data packet cannot be transmitted to the destination Mobile Node (MN). Therefore, an improved OHLAR (one-hop location-aided routing) algorithm is proposed in this research. It is designed for the hybrid environment consisting of MANET and WiMAX networks. WiMAX network is used to overcome the broadcast storm of location interchange among MNs under high mobility or high node density. It can also resolve the local maximum problem under small or low node density. Simulation results show that the improved OHLAR can keep high delivery ratio, low end-to-end delay and low control overhead compared to the basic OHLAR and other routing algorithms, including AODV, LAR and CAM.
PDF Abstract XML References Citation
How to cite this article
Wireless networks can be classified into two types: infrastructure mobile networks and non-infrastructure mobile networks. MANET (Mobile Ad hoc NETwork) belongs to the later category. There are no dedicated routers, or servers. It is formed by a set of Mobile Nodes (MNs). The previous routing algorithms for MANET can be classified into two categories: connection-oriented and connectionless algorithms. The classification depends on whether a route must be established before the data packet transmission. In general, the connection-oriented algorithms can be classified into three types:
|•||Proactive or table-driven routing algorithm: In this type of algorithm, the routing table of every MN is updated periodically via message broadcasting among MNs. A well-known DSDV (Destination-Sequenced Distance-Vector routing) algorithm proposed by Perkins and Royer (1994) belongs to this type. Every MN must store a routing table for data packet forwarding. The routing table of a MN is updated periodically via message broadcast. Its advantage is that the data packet transmission is efficient since an end-to-end route is always available, i.e., the end-to-end delay is small. Its disadvantage is the high overhead on maintaining routing table and the waste of network bandwidth. A broadcast storm easily occurs when the node density is high. If the broadcast interval for updating routing table is increased in order to reduce the usage of network bandwidth, it causes the routing table may be inconsistent with the real topology formed by MNs.|
|•||Reactive or on-demand routing algorithm: In this type of algorithm, a route is discovered only before the data packet transmission. When a route is broken caused by the movement of MNs in the route, a route recovery or maintenance procedure is needed to keep the route available. A well-known AODV (Ad-hoc On-demand Distance Vector routing) algorithm proposed by Perkins and Royer (1999) belongs to this type. Message broadcast is only occurred on route discovery to prevent the broadcast storm. However, the route discovery or maintenance causes that the end-to-end delay of a data packet is longer than the table-driven algorithm.|
|•||Hybrid scheme: This type of algorithm attempts to include the advantages of on-demand routing and table-driven routing. For example, Hass and Pearlman (1998) proposed a Zone Routing Protocol (ZRP). A zone of a node is defined to represent those neighbor MNs within n hops from the node. A routing table of a MN records the routing information of these neighbor MNs in a zone of the MN. This part is similar to the table-driven routing algorithm. When a MN attempts to communicate with a node outside its zone, a route discovery procedure similar to on-demand routing algorithm is used to establish the desired route. Although this type of algorithm includes the advantages of both types of algorithms. However, it also has the disadvantages of both algorithms on control overhead and end-to-end delay.|
For the above algorithms, a route must be established before the data packet transmission. However, the dynamic topology of MANET under high mobility or high node density situations may cause a route broken easily. A route recovery or maintenance procedure is needed to keep a route available. Therefore, the performance of these connection-oriented algorithms is degraded quickly as the increase of the number or moving speed of MNs.
In order to overcome the problems related to the maintenance of routing table in connection-oriented algorithms, connectionless algorithms are proposed. There is no routing table or route discovery procedure. Location information is popular used for data packet forwarding in connectionless algorithms. For example, the well-known LAR (Location-Aided Routing) algorithm proposed by Ko and Vaidya (1998) utilizes the location information to restrict the flooding area of data packet. LAR is based on two zones: expected and request zones. Expected zone is the possible area that may include the destination MN. Request zone is the minimal rectangle including the source MN and the excepted zone. Therefore, when a MN receives a data packet, it forwards the data packet only when it is within the request zone. DREAM (Distance Routing Effect Algorithm for Mobility) proposed by Basagni et al. (1998) is the corporation of table-driven and position-based routing algorithms. It enhances the performance of LAR by modifying the rectangular request zone as a cone from the source MN toward to the expected zone of the destination MN. GPSR (Greedy Perimeter Stateless Routing) proposed by Karp and Kung (2000) is also a position-based routing algorithm. It is also called geographic forwarding method (Stojmenovid and Lin, 2001). A packet is forwarded to the next MN with shortest distance to the destination MN. Besides, CAM (Connectionless Approach for MANET) is a position-based approach proposed by Ho et al. (2004, 2006). CAM divides the geographical area into grids. A grid path can be generated easily according to the location of source and destination MNs. When a MN receives a data packet, it forwards the data packet if its location within the grid path of the data packet. That is, a node-by-node route is replaced by a grid-by-grid path. A MN usually stays in a grid for a while. It causes a grid path is less broken than a route and thus reduces the frequency of route maintenance.
The above algorithms are also called position-based routing algorithm (Mauve et al., 2001). Although a connectionless algorithm has no route manipulation for data transmission, it still may encounter two problems:
|•||Broadcast storm problem under high node density: The interchange of location information among MNs is mainly based on message broadcast. The interchange is proceeded in order to get the location of destination MN. Therefore, a broadcast storm may still occur under high node density.|
|•||Local maximum problem under low node density: There is no hop-to-hop route for data forwarding. Therefore, a MN may possibly find no MN to be the next hop. For example, a MN forwards a packet to a one-hop neighbor MN with shortest distance to the destination MN. However, there is no neighbor MN with distance shorter than current MN. It is also called local maximum problem, i.e., void problem. The MN may forward the packet back to the previous node. But, the packet is still forwarded to the same MN again. This is a Ping-Pong Effect (PPE) caused by local maximum problem. This problem is easily occurred under low node density. For example, the node density of simulations in GPSR (Karp and Kung, 2000) is one node per 9000 m2. If the density is decreased to one node per 100000 m2, GPSR may be failure since a perimeter of a region may be unable to find for solving the problem. Another Greedy Anti-void Routing (GAR) protocol proposed by Liu and Feng (2007) can guarantee to solve the local maximum problem. However, it may be failure when the topology is changed very quickly under high mobility situation|
On the other hand, a new metropolitan area network, called WiMAX, was developed by IEEE 802.16 Working Group in 2000. A new version of WiMAX standard-IEEE 802.16e, called Mobile WiMAX, was also announced in December of 2005. The communication range of WiMAX is several km. All the mobile nodes can communicate directly via WiMAX base station. It seems insignificant to develop routing algorithms for MANET. However, the band width of WiMAX is only 75 Mbps. It is insufficient to serve the huge number of mobile nodes in the urban area. Therefore, MANET should be incorporated with WiMAX to be a hybrid network environment. WiMAX is used to interchange information which is critical to the routing algorithm of MANET.
In order to overcome the above problems and incorporate with the WiMAX environment, a connectionless routing algorithm called OHLAR (one-hop location-aided routing) is improved from our previous result (Liao and Lin, 2007). WiMAX network is used to overcome the broadcast storm of location interchange among MNs. The basic OHLAR proposed previously chooses a MN with the shortest distance to the destination MN as the next-hop node. However, it may cause the local maximum problem and PPE. OHLAR is improved to inhibit forwarding a packet to a MN with local maximum situation. Simulation is designed to evaluate the performance of the improved OHLAR under high mobility, high and low node density. The results show that the performance improved OHLAR is very good under the above situations. It is also useful for a hybrid network environment consisting of WiMAX and MANET.
A WiMAX network is used in the environment of OHLAR as shown in Fig. 1 for two reasons. One is to overcome the possible broadcast storm caused by the location interchange of MNs. The other is to design a suitable algorithm for the hybrid network environment consisting of WiMAX and MANET. A primitive design and simulation study is presented in Liao and Lin (2007). All the MNs can obtain location information from positioning technologies, such as the GPS (Global Positioning System). A WiMAX base station is assumed available for the interchange of MNs` location information. The data packet is still transmitted via the MANET but not via WiMAX network. It is reasonable since the band width of WiMAX is unable to satisfy the data transmission of huge number of MNs in the communication area. All the MNs update their location to a centralized server via the WiMAX network periodically. Then, a MN can query the location of neighbor MNs to select the next-hop MN.
Basic OHLAR: When a MN receives a data packet, it queries the location information of one-hop neighbor MNs via the WiMAX base station. Then, the packet is forwarded to a MN with shortest distance to the destination MN.
|Fig. 1:||The environment of OHLAR|
|Fig. 2:||The basic OHLAR algorithm|
This procedure is repeated until the packet reaches the destination MN. The basic OHLAR algorithm is shown in Fig. 2.
In the above algorithm, the source and the destination MNs are denoted as S and D, respectively. Initially, the current MN, denoted as M, is set as S. When M does not equal to D, the algorithm will find a MN n with shortest distance to D and set M as n until M equals to D.
The basic OHLAR is a greedy algorithm. A MN with the shortest distance to the destination MN is always available under normal or high node density. However, a local maximum problem may be encountered under low node density. The problem also causes a situation called Ping-Pong Effect (PPE). An example of PPE is shown in Fig. 3. In Fig. 3a, a data packet is forwarded from S through nodes I, J, K, L and M to D. Assume K is moved out of the communication range of L and marked as K` in Fig. 3b. The neighbor MN of K` with the shortest distance to D is N, K` forwards a data packet to N. At this moment, a local maximum is occurred since there is no neighbor MNs of N closer to D than N as shown in Fig. 3c. According to the basic OHLAR algorithm, the data packet is forwarded back to K`. The data packet is forwarded between K` and N recursively. That is, a PPE occurs between K` and N.
|Fig. 3:||An example of ping-pong effect caused by local maximum problem|
|Fig. 4:||The improved OHLAR algorithm|
Improved OHLAR: In order to solve the local maximum problem, a MN should not forward the same packet to the same MN again. Therefore, a set, denoted as T(M, D), is designed for a node M to record the one-hop neighbor MNs that forward back a packet to D. The improved OHLAR is shown in Fig. 4.
The main difference between the improved and basic OHLAR is on the steps 5 to 7. In step 5, those MNs in T(M, D) are excluded from the one-hop neighbor MNs of M to prevent PPE. In step 6, if the distance of next-hop MN n to D is longer than that of M, it means the PPE is occurred. Therefore, M is included into the set T(n, D) to prevent n forwarding a packet to M.
The same example in Fig. 3c is used to illustrate the PPE resolved by the improved OHLAR. When K` receives a data packet, it forwards the packet to N. Then, N forwards the packet back to K` since N is a local maximum node. Therefore, N is added into the set T(K`, D). At this moment, K` find a MN with shortest distance to D and not in the T(K`, D).
|Fig. 5:||An example of resolving local maximum problem|
Therefore, N is excluded and another MNO is selected as next hop node. K` forwards the data packet to O. The packet is then transmitted to D successfully via the nodes L and M as shown in Fig. 5.
A packet will not be forwarded to the same MN once it is included in T. The improved OHLAR is similar to a depth-first search. When the local maximum problem is occurred, the packet is forwarded back to previous nodes of the path in turns in order to find a possible path to the destination MN. Therefore, a packet will be transmitted from S to D finally if there is a path available. However, MNs is moving and the topology is changed dynamically. Therefore, the set T of every MN is reset for a fixed interval to enable packets reforwarding to the MNs in T.
Two simulations were designed to evaluate the performance of the improved OHLAR. One is under the high mobility; the other is under various node densities. The simulator is NS-2 (Network Simulator, version 2).
|Table 1:||The basic parameter setting of simulation studies|
|Table 2:||The parameter setting of high mobility simulation|
OHLAR is a hybrid of position-based and connectionless approach. It is compared with the well-known position-based algorithm-LAR (Ko and Vaidya, 1998) and the connectionless approach-CAM (Ho et al., 2004, 2006). The well-known on-demand routing algorithm-AODV (Perkins and Royer, 1999) is also compared here. The common parameter setting of simulations is shown in Table 1. The performance analysis mainly includes three metrics: data packet delivery ratio, end-to-end delay and control overhead. The simulations are presented in the following subsections.
The simulation of high mobility: The additional parameter setting of high mobility simulation is shown in Table 2. The moving speed is 5 to 30±10% m sec-1, i.e., 18 to 108±10% km h-1. A special parameter for OHLAR is the location update interval. It is the time interval of a MN on updating its location information. The interval setting is 1 to 4 sec. When the interval is large, the difference between actual and the last updated location of a MN is large, too.
The result of data packet delivery ratio versus speed is shown in Fig. 6. The ratio of AODV and LAR is decreased quickly as the increase of moving speed since the routes are broken easily under high moving speed. But, the improved OHLAR with one second update interval can keep a high delivery ratio as expected. However, if the location update interval is three or four seconds, the delivery ratio is worse than AODV and LAR. When the update interval is four seconds and packet rate is two per second, there are eight packets within four seconds. If the moving speed is 30 m sec-1, the moving distance is 120 m after four seconds. Such a large difference between the actual and the last updated location information causes the delivery ratio decreased to about 60%. However, the ratio of two-second update interval is still better than that of AODV and LAR.
|Fig. 6:||Data packet delivery ratio vs. speed|
|Fig. 7:||End-to-end delay vs. speed|
Figure 7 shows the results of the average end-to-end delay of a data packet as the increase of moving speed. When the moving speed is increasing, a route must be recovered frequently since it is broken easily. Therefore, the end-to-end delay of AODV and LAR is increasing as the moving speed. Oppositely, the connectionless characteristic of the improved OHLAR causes the end-to-end delay keeping very low as shown in the figure. Besides, the end-to-end delay is not influenced by the update interval. Therefore, only the result with one-second interval is shown in the Fig. 7.
Figure 8 shows the number of control packet per data packet as the increase of moving speed. The control packet overhead of AODV and LAR is the number of control packets divided by the number of delivered data ackets.
|Table 3:||The comparison of OHLAR and CAM under high node density|
|Table 4:||The comparison of OHLAR and CAM under small node density|
|Fig. 8:||Control overhead vs. speed|
Similarly, the overhead of the improved OHLAR is the number of location query/update packets divided by the number of the delivered data packets. According the curves in Fig. 8, the control packet overhead of AODV and LAR is increasing as the increase of the moving speed. Oppositely, the overhead of the improved OHLAR is almost not influenced by the moving speed. A large update interval causes a small control overhead.
The simulation of various node densities: The local maximum problem does not occur under high node density. Therefore, the simulation results of the improved OHLAR under high node density were the same as that presented in Liao and Lin (2007). In this subsection, the results are compared with CAM (Ho et al., 2006). However, the simulator used in Ho et al. (2006) is GloMoSim but not NS-2. Fortunately, LAR was used for comparison both in Liao and Lin (2007) and Ho et al. (2006). Therefore, the comparison of the improved OHLAR and CAM is based on the improvement over the same LAR operated on two simulators. The improved ratios of three metrics are computed separately. Assume the simulation result of LAR is denoted L and the result of CAM or OHLAR is denoted as V. The improved ratio of data packet delivery ratio is computed by using (1). When V is larger than L, it means there is a positive improvement. The improved ratio of end-to-end delay and control overhead is computed by using (2). A positive improvement happens when V is smaller than L.
The comparison of OHLAR and CAM under high node density is shown in Table 3. The number of MNs is 200 with a moving speed 20 m sec-1. By observing the packet delivery ratio, the improved ratio of OHLAR is 19.6%. It is even better than 1.2% of CAM. For the end-to-end delay, the improved ratio of OHLAR is a litter higher than that of CAM. For the control overhead, the improved ratio of OHLAR is not so good as CAM. However, it still achieves almost 50% improvement than LAR.
The comparison of OHLAR and CAM under small node density is shown in Table 4. The number of MNs is 50 and the moving speed is 20 m sec-1. By observing the packet delivery ratio, the improved ratio of CAM is -27.7% which means CAM is not suitable for small node density. Oppositely, the improved ratio of OHLAR is 15%. It means that OHLAR is even better than CAM. For the results of end-to-end delay, the improved ratio of OHLAR is still higher than that of CAM.
|Table 5:||The parameter setting of low node density simulation|
|Fig. 9:||Data packet delivery ratio under low node density|
For the results of control overhead, the improved ratio of OHLAR is a little lower than that of CAM. According to the above results in Table 3 and 4, it is obvious that the performance of OHLAR is better than CAM under high and small node density.
An additional simulation was designed to evaluate the data delivery ratio of the improved OHLAR under low node density. The parameter setting is shown in Table 5. The number of MNs is only 10 to 40 for the same simulation area. The lowest node density is only 1 node per 100000 m2. The moving speed of a MN is 5±10% m sec-1.
The simulation result is shown in Fig. 9. According to the curves in the Fig. 9, the data packet delivery ratio of AODV and the basic OHLAR is less than 60% when the number of MNs is only 10. However, the data packet delivery ratio of improved OHLAR is a little better than LAR and can keep over 90%. Obviously, the improved OHLAR can overcome the local maximum problem under low node density.
According to the above simulation results, the performance of the improved OHLAR is very good no matter under high mobility or various node densities. It is also suitable for a hybrid network environment consisting of WiMAX and MANET.
CONCLUSION AND FUTURE WORKS
Although mobile ad hoc network technology is developed for several decades, most of the routing algorithms are connection-oriented. The performance of connection-oriented algorithms is unsatisfactory under high mobility since routes are easily broken. They also cause some side-effects, including a longer end-to-end delay and a higher control overhead. Besides, their performance is also unsatisfactory under high or low node density. Therefore, a connectionless algorithm is proposed in this paper. It is improved from our previous OHLAR algorithm to overcome the problem of local maximum problem. The contributions of the improved OHLAR include:
|•||The incorporation of WiMAX and MANET: The bandwidth of WiMAX is insufficient to serve huge number of MNs in the communication range. However, it is suitable to transmit critical information among MNs. In this paper, WiMAX is used to transmit the location information of MNs. The simulation results show that the incorporation of WiMAX and MANET is helpful on increasing the performance of the proposed algorithm.|
|•||Good performance under diverse situations: Unlike some algorithms can only useful under normal situation. No matter high mobility, low or high node density, the improved OHLAR can keep high data packet delivery ratio, low end-to-end delay and low control overhead according to the simulation results.|
|•||Coping with high dynamic topology: The topology of MANET is changed dynamically under high mobility. For the improved OHLAR, a MN usually chooses the best MN as next-hop node for coping with high dynamic topology.|
Although the improved OHLAR is performed well under diverse situation, the control overhead listed in Table 3 and 4 can still be refined further. In the future works, the refinement can be obtained from the following two parts.
|•||Adaptive location update mechanism: When the moving speed of a MN is low, the location update interval can be large. Oppositely, a small interval is needed for a MN with high moving speed. Therefore, an adaptive location update mechanism should be designed to adjust the update interval automatically according to the moving speed for decreasing the control overhead.|
|•||The area for location update: For the current OHLAR, all the MNs update their location according the update interval. However, it is unnecessary for a MN if it is not within the linear area between the source and destination MNs. Therefore, if highlight areas can be maintained according to the current data packets. A MN updates its location when it is within the highlight areas. It should be useful to reduce the control overhead related to location update in advance.|
- Ho, Y.H., A.H. Ho, K.A. Hua and T. Do, 2006. Adapting connectionless approach to mobile ad hoc networks in obstacle environment. Proceedings of the International Symposium on Wireless Pervasive Computing, January 16-18, 2006, Phuket, Thailand, pp: 7-7.
- Liao, H.C. and C.J. Lin, 2007. A WiMAX-based connectionless approach for high mobility MANET. Proceedings of the 9th International Conference on Advanced Communication Technology, February 12-14, 2007, Phoenix Park, Korea, pp: 479-483.
- Liu, W.J. and K.T. Feng, 2007. Greedy anti-void routing protocol for wireless sensor networks. IEEE Commun. Lett., 11: 562-564.
- Perkins, C.E. and P. Bhagwat, 1994. Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers. Proceedings of the Conference on Communications Architectures, Protocols and Applications, August 31-September 2, 1994, England, UK., pp: 234-244.
- Perkins, C.E. and E.M. Royer, 1999. Ad-hoc on-demand distance vector routing. Proceedings of the 2nd Workshop on Mobile Computing Systems and Applications, February 25-26, 1999, New Orleans, LA., pp: 90-100.
- Stojmenovid, I. and X. Lin, 2001. GEDIR: Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks. IEEE Trans. Parallel Distrib. Syst., 12: 1023-1032.