25-08-2017, 09:32 PM
Load Balanced Short Path Routing in Wireless Networks
Load Balanced Short Path.pdf (Size: 239.74 KB / Downloads: 23)
Abstract
In this paper, we study wireless network
routing algorithms that use only short paths, for minimizing
latency, and achieve good load balance, for
balancing the energy use. We consider the special case
when all the nodes are located in a narrow strip with
width at most
3/2 ≈ 0.86 times the communication
radius. We present algorithms that achieve good performance
in terms of both measures simultaneously. In
addition, our algorithms only use local information and
can deal with dynamic change and mobility efficiently.
Introduction
In a mobile ad-hoc network or a sensor network, devices
communicate to their nearby nodes and form an adhoc
multi-hop communication network. Routing in such
a network is challenging due to the lack of central control
and the high dynamicity of the network. The previous
works have focused on discovering and maintaining routes
that enable the connectivity between the nodes and, if
possible, that minimize the number of hops on a path.
One important restriction of a wireless network is that
the nodes are energy constrained as they are normally
powered by batteries. Besides minimizing latency, the
shortest path routing is good for overall energy efficiency
because energy needed to transmit a packet is correlated
to the path length. However, the algorithms that aim
to minimize the path length may ignore “fairness” in
the routing — for example, the shortest path routing is
likely to use the same set of hops to relay packets for
the same source and destination pair. This will heavily
load those nodes on the path even when there exist other
feasible paths. Such an uneven use of the nodes may cause
some nodes die much earlier, thus creating holes in the
network, or worse, leaving the network disconnected. This
problem is critical in emergency networks, for example, to
locate survivors after structure collapse, where depleting
the battery of a node may have tragic results. In addition,
unbalanced use of the nodes may discourage the nodes to
participate in the routing.
Related work
Our work for the nodes in a narrow strip is closely
related to the on-line load-balancing problems on related
machine model. Azar’s paper [2] and Borodin and El-
Yaniv’s book [3] contain excellent survey of this subject.
Load-balancing routing in general can be formulated as
the unsplittable flow problem where we aim to minimize
the maximum node congestion. This is a well-known NPhard
problem that can be approximated to a factor of
O(log n/ loglog n) [4], [5]. In all the previous work, one
either ignores the length of the path or uses only shortest
paths for regular networks such as meshes. Another related
problem is the on-line virtual circuit routing problem,
which has also been studied extensively [6], [2], [3].
There have been extensive study on routing in wireless
networks in recent years. Among various metrics used for
evaluating the routing quality, the most common one is
probably the number of hops on the routing path. The
protocols that use shortest path routing include Dynamic
Source Routing (DSR) [7], Ad-hoc On-demand Distance
Vector routing (AODV) [8] and many others. Please refer
to the surveys [9] and the references therein.
Hardness of the problem
Before presenting the algorithms, we first show that
the optimum load balancing is difficult even for a simple
network, as shown in Figure 2(i). Suppose that each node
xi wishes to send a packet with size i to the node yi. They
have to choose, from z1, z2, a node to relay the packet. The
optimum solution is then the most even distribution of the
packets on z1, z2. This is exactly the knapsack problem, a
well-known NP-hard problem.
In fact, if there are m nodes z1, · · · , zm, inside the
intersection of the communication ranges of xi’s and yi’s,
then minimizing the maximum load on the m nodes
becomes the on-line load balancing problem on m identical
machines. Even obtaining an approximation within a ratio
of 1.852 has been proven NP-hard [27].
Distributed Implementation
In this section, we present an efficient implementation
of the above algorithms. We assume each node knows its
location by either GPS or some localization methods [28],
[29], [30], [31]. We also assume that the rough location
of the destination is known such that the source node
knows whether it should send the packet to its left or right.
Denote by h1(p) the number of nodes inside the communication
range of p and by h2(p) the number of nodes that
is at most distance two from p.
Conclusion
In this paper, we initiate the study of wireless network
routing with the aim of achieving good performance in
terms of both stretch factor and load-balancing ratio. We
present algorithms which can achieve constant competitive
factors for both measures when all the nodes are located in
a narrow strip. In addition, our algorithm is local and deals
with dynamic change efficiently. One interesting problem
is to extend the study to the other node distribution. For
such an extension, we may have to make assumption on the
traffic patterns too as the load-balanced routing is difficult
even for nodes that form a regular grid.