A Position-Based Connectionless Routing Algorithm for MANET and WiMAX under High Mobility and Various Node Densities

INTRODUCTION

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:

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:

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.

OUR ALGORITHM

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.

SIMULATION STUDIES

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.

(1)

(2)

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 m². 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:

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.