ABSTRACT. Limited battery life is a known problem with mobile computers. In multi-hop ad hoc networks mobile nodes’ excessive energy consumption leads to extinction of nodes and network partition. As communication is the main cause for energy consumption, we need to develop routing methods that prevent overloading of nodes. For this we propose the use of network equilibration. By distributing traffic to several routes according to traffic equilibrium we achieve longer network lifetime and maintain better connectivity. On the other hand, this kind of multi-path routing, carried out here by the use of load balancing cost functions, is a form of congestion control. Network congestion control decreases packet collisions and eventually leads to better throughput [2]. This paper reports a study of ad hoc routing covering equilibrated routing, simulation and performance evaluation in terms of energy consumption and network lifetime.

Keywords: ad hoc networks, congestion control, energy-aware routing, load balancing, multi-path routing, traffic equilibration.

1. INTRODUCTION

The continuous growth of the number of subscribers in mobile wireless business has made possible the tremendous investment to the branch. Thanks to this, the devices have developed enormously, and are still under development. Mobile device’s size, power capacity and memory among other attributes are now totally different from what they were just few years ago. Nowadays wireless voice and data communication is possible almost everywhere. This has made wireless communication a permanent part of our society. This kind of development continues. For example wireless internet and data communication generally becomes more and more popular. The wireless communication is also moving to more ’ubiquitous’ direction. This means that the wireless network is present everywhere, enabling communication in different ways, not only calls. The devices could for example automatically communicate each other enabling different kinds of services and automation. All this makes need for ad hoc type networks.

Pure ad hoc network consists only of a group of mobile hosts (nodes). There is no kind of stationary infrastructure such as base stations or external administration. Because of this and limited radio propagation, if nodes that want to communicate with each other are apart, they have to use nodes between them (intermediate nodes) to forward messages. Consequently, the routes become multi-hop and nodes have to find these routes themselves, i.e. act as routers (see figure 1). The ad hoc network has to be self organized. This means that network itself organizes to manage in different situations, like when the network is established, or the topology of the network changes.

There is a variety of applications which could make use of ad hoc networks [1]. For example emergency services, conferencing or sensor networks [7]. Emergency service could be for example network that can be quickly constructed to a disaster area, without any or with destructed infrastructure, enabling communication during rescue work. In conferencing, devices which come together in some area, can quickly and easily communicate which each other. This could be quite practical for example in conference circumstances. Sensor networks consist of static nodes, e.g. environmental sensors that detect and monitor changes in the environment.

The implementation of an ad hoc network is not a simple task. As in all wireless networks, the limited bandwidth is the main restrictive feature to take into consideration when the network is under planning. Other main feature is energy consumption. This is important because mobile devices work with batteries which have limited capacity. Notice that in ad hoc network, communication between mobile hosts uses resources from also the intermediate nodes. These resources are e.g. bandwidth and battery capacity. As mentioned, in ad hoc networks there is no stationary infrastructure. This means that all hosts can move, and this can cause continuous changing in the topology of the network. This leads to other major problem in ad hoc networks: routing. When a node (origin) wants to communicate with another node (destination), it has to know the route or routes there, i.e. the intermediate nodes between these two. Because topology changes, this information changes all the time.

There are plenty of different kinds of ad hoc routing protocols [1, 7]. Routing protocols are typically divided into two categories: proactive and reactive protocols. With proactive protocols, every node updates frequently routing tables in which the routes to all other nodes are saved. The route to a destination is then known already if it is needed. However, this frequent updating of tables causes a lot of resource wasting overhead signaling to the network. Reactive protocols act differently. Now nodes do not maintain beforehand information about routes to other nodes. When a node needs a route to a destination, it simply starts up a procedure which tries to find the route (or routes). The idea is simple, but in practice this leads also to problems. For example this causes delay to the transmission.

In this paper we do not concentrate deeply to which protocol is used, but one observation can be done: All ’classical’ ad hoc routing protocols find only one route to the destination. This causes some problems [12]. For example, if the link breaks down or if it becomes too congested, the protocol has to find compensatory route from the start. This problem can be avoided using multi-path routing. Multi-path routing means that there is information about more than one route to the destination. There are some papers [5, 8, 12] which consider multi-path routing, and some ideas of how ’classical’ routing protocols (e.g. DSR) can be changed so that they support multi-path routing [10, 12]. Even if we use multi-path routing, there are still major problems. For example, how these routes are used. How is the traffic directed to different routes? What would be the metric or cost, which directs this traffic delivery? These are some open questions that need to be studied. In this paper we consider these problems of traffic assignment. We also discuss what kind of benefits or disadvantages we find with using multi-path routing.

With ad hoc type sensor networks using a multi-path routing scheme Shah & Rabaey [10] have obtained simulation results showing significant improvements in network lifetime. Here we aim to resolve what kind of improvements can be attained with a new multi-path routing scheme both in sensor networks and in mobile ad hoc networks. For traffic assignment we consider a method based on traffic equilibrium. Yet for implementation embedded in ad hoc routing protocols, we refer to future work [6]. When equilibration is put into practice in ad hoc network, the transmitting node will gather information of available routes and execute light operations which result in percentages according to which the traffic is to be distributed. At this stage we investigate what happens when the percentages are calculated to satisfy traffic equilibrium.

Here equilibrated routing is simulated in sensor networks and in mobile ad hoc networks. Compared to a sensor network the mobility of nodes presumably diminishes the battery consumption equalizing effects of equilibration. In fast and unrestrictedly moving networks the nodes’ movements will eventually take each node in turn to a central position in the network. We compare the simulation results of equilibrated routing with results obtained using a single-path routing scheme. It is worth noticing, that even though the network lifetime may not be extended with some rates of mobility, the traffic equilibration scheme presented here still reduces network congestion. However, the far-reaching effects of this aspect are left for future study.

2. EQUILIBRATION

In classical network equilibration, every route from origin to destination is assigned a cost given by a certain cost function. Typically the cost is in relation with the amount of traffic on the route. The aim is to find a balancing distribution of traffic so that the costs of used routes are equalized onto the lowest possible level. In equilibration, the traffic of the network is considered by origin-destination pairs (OD pairs). The traffic is in equilibrium if for all OD pairs the routes in use all have the minimal cost.

The computation of a network equilibrium is based here on the notion that the equilibrium problem is equivalent to a variational inequality problem. This way we are able to use the powerful solution methods developed for variational inequalities (see [3] and references therein).

In classical network equilibrium problem, we consider a general traffic network with the total of m routes between OD pairs. For each OD pair, there is a known traffic flow which is to be distributed among available routes. For every i = 1, 2,…,m let xi be the traffic flow on route pi . Group the traffic flows to flow vector x = (x1,x2,…,xm)T . Define a route cost function C : ℝ+m → ℝ +m,

that determines route cost Ci = Ci(x) for every i = 1, 2,…,m. The total cost of network is defined as the scalar product of flow vector x and corresponding cost vector C(x)

Smith [11] showed that the equilibration of this network is equivalent to finding a feasible flow vector x∗ for which

For the solution of the above variational inequality we use the projection method presented by professor I. V. Konnov [4].

Generally, equilibration methods are iterative procedures that calculate an approximation of network equilibrium. For each OD pair, the most expensive route in use and the cheapest route are found. If the difference of the costs of these routes is within a certain marginal, the traffic of the OD pair is considered equilibrated. Otherwise, according to a given method is calculated a flow pattern that shows increases in flows on cheaper routes and decreases in flows on more expensive routes. New iteration step begins with calculating route costs relative to the current flow pattern.

In this paper, we consider some effects of equilibrated routing in ad hoc networks. Every route is assigned a cost by a given metric. This metric can be based on e.g. the length of the path, packet arrival rates, or the battery capacities in the intermediate routes. An equilibrating flow pattern is calculated using the projection method. The flow between each OD pair is normalized, so the flow pattern calculated actually states the percentages according to which the traffic is to be distributed. For each packet we use weighted randomization to determine which route is used.

The novelty of this multi-path routing scheme lies in the fact that it can be used to optimize a variety of network performance attributes. Depending on which cost function we choose, the equilibration is set to enforce congestion control, energy-aware routing, load balancing or shortest path routing.

For this paper, we formulate two types of cost functions. The first takes into account the packet arrival rates of intermediate nodes, and the second also the energy states of the intermediate nodes.

Let us consider a network with m possible routes for its OD pairs. For every route r1 , r2,…,rm we determine a cost C1 ,C2,…,Cm, respectively. Let Ni1,Ni2,…,Nin mark the intermediate nodes on route ri. Let λi1,λi2,…,λin be their packet arrival rates (in packets∕second) and εi1,εi2,…,εin their ratios of used battery. We have two ways of assigning the cost of each route:

In the following we discuss computer simulations of routing in ad hoc networks. We consider 3 cases of networks of different sizes and with different rates of mobility. In each case, we run simulations with the same movement and communication data simulating costs 1∘ and 2∘ in turn. For comparison, we run each case using a routing scheme 0∘ that utilizes a single shortest path between OD pairs:

3. SIMULATION

For the testing of our equilibration scheme, we constructed a simulation platform. In figure 2 is shown a snapshot of the simulator, calculating Case 3 of following test cases. In the simulator, the mobility of nodes and the emergence of calls are simulated. Furthermore, the battery consumption of nodes is estimated. Assumptions for this are:

In this computer simulation we do not handle data packets. For the cost functions 1∘ and 2∘, instead of packet arrival rates we use the values in OD pairs’ flow patterns. This is based on an assumption that the nodes are homogenous in terms of transmission speed. During a short enough time period, all transmitting nodes will transmit the same amount of packages. We use the sum of the flow values concerning each node to simulate its packet arrival rate.

Using equilibration schemes 1∘ and 2∘, a route is chosen from uniform distribution obeying the percentages of the flow pattern. This is done once for every time slot. The approach for routing scheme 0∘ is different. Now the route is selected randomly from the set of the shortest paths. This is done once per call, except if a shorter path is found or the used route breaks.

This case is a basic example of an arranged sensor network. We have 25 nodes and one OD pair as shown in figure 3.

In the beginning of the simulation the batteries of all nodes are fully loaded. The simulation is let to continue until there are no routes available between OD pairs. This led at the most to approximately 400 iterations. The results of Case 1 are presented in figure 4. The results of different routing schemes are divided into three columns. Graphs on row one describe the extinction of nodes in the process. This means nodes that run out of battery, i.e. ’die’. On row two are given the used battery capacities for each node after 300 iterations. The third row represents the average length of routes during simulation.

We notice that using routing scheme 0∘ the first death occurs quite early. Using equilibration with costs 1∘ and 2∘ the first death occurs approximately 150 iteration steps later. The time when the first node dies, is often regarded as the lifetime of the network [7]. This is an important value, because the splitting of the network begins from this point.

We can see that after 300 iterations 8 nodes have died out using scheme 0∘ , but only 3 nodes with equilibration costs 1∘ and 2 nodes using cost 2∘. Furthermore, from figure 4.b we can see that the standard deviation of battery capacities is lower using 1∘ and 2∘, i.e. we have more balanced battery consumption. These are good results for 1∘ and 2∘ , but the drawback is that the average consumption is higher than with 0∘ . The reason why the average consumption is higher using schemes 1∘ and 2∘ , can be seen from the third row of figure 4. Scheme 0∘ uses always the shortest possible routes which using our assumptions leads directly to the minimum power consumption. With schemes 1∘ and 2∘ used routes are longer from the start. In figure 4.a is presented the table of total battery consumption, i.e. the percentage of used energy from whole network, using different schemes during simulation. We can see, that scheme 0∘ uses least energy and 2∘ most during the whole simulation.

In this case we have another arranged sensor network of 20 nodes and randomized OD pairs (see figure 5). So, the main difference compared to Case 1 is that now there are several OD pairs.

The results from Case 2 are presented in figure 6 in the same form as in the Case 1. From the first row we can see that also now using routing scheme 0∘ , the first death occurs early compared to the other schemes. In fact, there are no deaths using equilibration with cost 1∘ during 400 iterations. Using equilibration with cost 2∘ , there is only one death and this happens very late in the simulation.

In row two are presented the states of battery at the end of the simulation. The same kind of observations can be made as in Case 1. With routing scheme 0∘ , the average battery consumption is on a lower level than with equilibration using costs 1∘ and 2∘, but the standard deviation of battery consumption is the highest using scheme 0∘ . More accurate results are presented also now in graph 6.b. The results are quite the same as in Case 1, but the differences are now much more significant.

On row three is presented the average length of routes. The differences here explain the differences in battery consumptions. Especially when using equilibration with costs 2∘, the length of routes are much longer compared to other schemes. From graph 6.a we can see that this phenomenon can be seen from the beginning of the simulation.

This case is our first test with mobile nodes. We let 12 nodes move along randomized trails with speeds of up to 20 m/s. The simulation area is a rectangle of the size 3 km times 2 km. In order for the 12 mobile nodes to maintain a reasonable rate of connectivity, we chose a range of coverage of 1000 meters. You can see a snapshot of the simulation in figure 2.

We let simulation run for 1000 iterations. The simulation results of Case 3 are presented in figure 7.

The main observation when compared to the previous cases is that now there is not so much differences between the results obtained with different routing schemes. However, the earliest death occurs also now with routing scheme 0∘ . Furthermore, using equilibration with costs 1∘ and 2∘ the routes’ average length increases slightly causing more battery consumption. The difference of battery consumption between equilibration schemes 1∘ and 2∘ is minimal. This is significant, because in previous cases equilibration with cost 2∘ has been clearly the most energy consuming routing scheme.

In this mobile case there isn’t always but one route available. This naturally diminishes the effectiveness of equilibration schemes. In addition, the movement of nodes balances battery consumption implicitly.

4. CONCLUSION

We have presented a load balancing multi-path routing scheme making use of the network equilibrium. We strove to examine the benefits and drawbacks of this routing scheme in terms of energy consumption and network lifetime.

The simulation of equilibrated routing showed prominent effects on battery consumption. The network lifetime was prolonged in all cases using both 1∘ and 2∘ . Naturally, when equilibrated routing was used, routes were longer and so the total battery consumption was heavier. Compared to our reference routing scheme 0∘, equilibration set the scene for a more balanced extinction of nodes.

The formulation of route cost 1∘ considered the traffic flow of intermediate nodes. Compared to scheme 0∘ , this scheme extended the network lifetime substantially. Compared to scheme 2∘ , the lifetime extension was of the same magnitude, but at the same time the total battery consumption was considerably lower. In Case 1, scheme 1∘ had connection up and running for about 50 time slots longer than the other schemes.

Equilibration scheme 2∘ took note of the battery capacities of intermediate nodes. This way we hoped to achieve even longer network lifetimes than with scheme 1∘ . However, this only happened in Case 1. Because of the formulation of route cost 2∘, the scheme produced the most balanced battery consumption distributions (i.e. smallest deviations). Unfortunately, the total battery consumption rose quite high. Especially in Case 2, the total consumption was too high compared to the benefits in terms of network lifetime.

In simulations, the behavior of scheme 1∘ was somewhere in between schemes 0∘ and 2∘. With scheme 1∘ we obtained significant improvements in network lifetime requiring only little growth in total battery consumption. We conclude that equilibration routing scheme 1∘ is the best choice of the three schemes presented here.

As a whole, examples gave promising results that equilibrated routing can effectively be applied in controlling the battery consumption of nodes. However, these results are merely something to base future work on.

References

[1] J. F. R. Antn: Ad Hoc Networks - Design and Performance Issues, Otamedia Oy, Espoo, 2002

[2] S. G. Glisic: Adaptive WCDMA, John Wiley & Sons, Chichester, 2003

[3] I. V. Konnov: Combined relaxation methods for variational inequalities, Springer-Verlag, Berlin, 2001

[4] I. V. Konnov: On an approach to solve transportation equilibrium problems, Preprint, 2002

[5] S-J. Lee - M. Gerla: Split multipath routing with maximally disjoint paths in ad hoc networks, Proc. IEEE International Conference on Communications ICC 2001

[6] K. Lieska - V-M. Jokela - E. Laitinen: An equilibration scheme for multi-path routing in ad hoc networks, In preparation

[7] C. E. Perkins: Ad hoc networking, Addison-Wesley, Boston, 2001

[8] P. Pham - S. Perreau: Multi-path routing protocol with load balancing policy in mobile ad hoc network, Proc. IEEE Conference on Mobile and Wireless Communications Networks MWCN 2002

[9] E. M. Royer - C-K. Toh: A review of current routing protocols for ad-hoc mobile networks, IEEE Personal Communications 6 (1999), 46-55

[10] R. C. Shah - J. M. Rabaey: Energy aware routing for Low energy ad hoc sensor networks, Proc. IEEE Wireless Communications and Networking Conference WCNC 2002

[11] M. J. Smith: The existence, uniqueness and stability of traffic equilibria, Transp. Res. 13B (1979), 295-304

[12] L. Zhang - Z. Zhao - Y. Shu - L. Wang - O. W. W. Yang: Load balancing of multipath source routing in ad hoc networks, Proc. IEEE International Conference on Communications ICC 2002

DEPARTMENT OF MATHEMATICAL SCIENCES, UNIVERSITY OF OULU P.O. BOX 3000, FIN-90014 UNIVERSITY OF OULU, FINLAND