A Location Based Routing Method for Mobile Ad Hoc Networks

Using location information to help routing is often proposed as a means to achieve scalability in large mobile ad-hoc networks. However, location based routing is difficult when there are holes in the network topology and nodes are mobile or frequently disconnect to save battery. Terminode routing, presented here, addresses these issues. It uses a combination of location based routing (Terminode Remote Routing, TRR), used when the destination is far, and link state routing (Terminode Local Routing, TLR), used when the destination is close. TRR uses anchored paths, a list of geographic points (not nodes) used as loose source routing information. Anchored paths are discovered and managed by sources, using one of two low overhead protocols: Friend Assisted Path Discovery and Geographical Map-based Path Discovery. Our simulation results show that terminode routing performs well in networks of various sizes. In smaller networks, the performance is comparable to MANET routing protocols. In larger networks that are not uniformly populated with nodes, terminode routing outperforms existing location-based or MANET routing protocols.

A Location Based Routing Method for Irregular Mobile Ad Hoc Networks

Ljubica Blazevic, Jean-Yves Le Boudec

Using location information to help routing is often proposed as a means to achieve scalability in large mobile ad-hoc networks. However, location based routing is difficult when there are holes in the network topology and nodes are mobile. Terminode routing, presented here, addresses these issues. It uses a combination of location based routing (Terminode Remote Routing, TRR), used when the destination is far, and link state routing (Terminode Local Routing, TLR), used when the destination is close. TRR uses anchored paths, a list of geographic points (not nodes) used as loose source routing information. Anchored paths are discovered and managed by sources, using one of two low overhead protocols: Friend Assisted Path Discovery and Geographical Map-based Path Discovery. Our simulation results show that terminode routing performs well in networks of various sizes. In smaller networks, the performance is comparable to MANET routing protocols. In larger networks that are not uniformly populated with nodes, terminode routing outperforms existing location-based or MANET routing protocols.

2003

Routing and search on large scale networks

Dominique Florian Tschopp

In this thesis, we address two seemingly unrelated problems, namely routing in large wireless ad hoc networks and comparison based search in image databases. However, the underlying problem is in essence similar and we can use the same strategy to attack those two problems. In both cases, the intrinsic complexity of the problem is in some sense low, and we can exploit this fact to design efficient algorithms. A wireless ad hoc network is a communication network consisting of wireless devices such as for instance laptops or cell phones. The network does not have any fixed infrastructure, and hence nodes which cannot communicate directly over the wireless medium must use intermediate nodes as relays. This immediately raises the question of how to select the relay nodes. Ideally, one would like to find a path from the source to the destination which is as short as possible. The length of the found path, also called route, typically depends on how much signaling traffic is generated in order to establish the route. This is the fundamental trade-off that we will investigate in this thesis. As mentioned above, we try and exploit the fact that the communication network is intrinsically low-dimensional, or in other words has low complexity. We show that this is indeed the case for a large class of models and that we can design efficient algorithms for routing that use this property. Low dimensionality implies that we can well embed the network in a low-dimensional space, or build simple hierarchical decompositions of the network. We use both those techniques to design routing algorithms. Comparison based search in image databases is a new problem that can be defined as follows. Given a large database of images, can a human user retrieve an image which he has in mind, or at least an image similar to that image, without going sequentially through all images? More precisely, we ask whether we can search a database of images only by making comparisons between images. As a case in point, we ask whether we can find a query image q only by asking questions of the type "does image q look more like image A or image B"? The analogous to signaling traffic for wireless networks would here be the questions we can ask human users in a learning phase anterior to the search. In other words, we would like to ask as few questions as possible to pre-process and prepare the database, while guaranteeing a certain quality of the results obtained in the search phase. As the underlying image space is not necessarily metric, this raises new questions on how to search spaces for which only rank information can be obtained. The rank of A with respect to B is k, if A is B's kth nearest neighbor. In this setup, low-dimensionality is analogous to the homogeneity of the image space. As we will see, the homogeneity can be captured by properties of the rank relationships. In turn, homogeneous spaces can be well decomposed hierarchically using comparisons. Further, it allows us to design good hash functions. To design efficient algorithms for these two problems, we can apply the same techniques mutatis mutandis. In both cases, we relied on the intuition that the problem has a low intrinsic complexity, and that we can exploit this fact. Our results come in the form of simulation results and asymptotic bounds.

EPFL2010

A cross-layer design of wireless ad-hoc networks

We consider a cross-layer design of wireless ad-hoc networks. Traditional networking approaches optimize separately each of the three layers: physical layer, medium access and routing. This may lead to largely suboptimal network designs. In this work, we propose a jointly optimal design of the three layers, and we show a significant performance improvement over the conventional approach. In the first part of this thesis, our goal is to select appropriate performance metrics for the joint optimization problem. To that respect, we analyze several existing rate-maximization performance metrics for wireless ad-hoc networks: maximizing the sum of rates, max-min fairness and proportional fairness. We first show with several examples that it is not clear if and how max-min fairness can be defined on each one of the examples. We give a formal proof that the max-min fair rate allocation exists on a large class of sets of feasible rates, among which are the feasible-rate sets of all known ad-hoc networking examples. We also give a centralized algorithm to compute the max-min fair allocation whenever it exists. Next, we compare the three metrics for ad-hoc scenarios in terms of efficiency and fairness. We prove that, similar to wired networking,maximizing the sum of rates leads to gross unfairness and starvation of all but the flows with the best channel conditions. We also prove that, contrary to wired networking, max-min fairness yields all flows having the same rate, thus causing large inefficiencies. These findings offer theoretical explanations to the inefficiency and unfairness phenomena previously observed in the contexts of 802.11 and UWB networks. Finally, we show that proportional fairness achieves a good trade-off between efficiency and fairness and is a good candidate for a rate-based performance metric in wireless ad-hoc settings. Having shown that the proportional fairness is an appropriate optimization objective for our problem, in the second part of the thesis we consider a joint optimization of rates, transmission powers, medium access (scheduling) and routing, where the goal of the optimization is to achieve proportional fairness. We first analyze networks built on physical layers that have a rate which is a linear function of SNR at the receiver (such as UWB or low-gain CDMA systems). We find that the optimal solution is characterized by the following principles: (1)Whenever a node transmits, it has to transmit with the maximum power; otherwise it has to remain silent (0 - PMAX power control). (2) Whenever data is being sent over a link, it is optimal to have an exclusion region around the destination, in which all nodes remain silent during transmission, whereas nodes outside of this region can transmit in parallel, regardless of the interference they produce at the destination. (3) When a source transmits, it adapts its transmission rate according to the level of interference at the destination due to sources transmitting in parallel. (4) The optimal size of this exclusion region depends only on the transmission power of the source of the link, and not on the length of the link nor on positions of nodes in its vicinity. As for the routing, we restrict ourselves to a subset of routes where on each successive hop we decrease the distance toward the destination. We also show that (5) relaying along a minimum energy and loss route is better than using longer hops or sending directly, which is not obvious since we optimize rate and not power consumption. Finally (6), the design of the optimal MAC protocol is independent of the choice of the routing protocol. We present a theoretical proof of optimality of 0 - PMAX power control, and the remaining findings we show numerically on a large number of random network topologies. Next, we consider narrow-band networks, where rate function is a strictly concave function of SNR. There, previous findings do not always hold. We show that in some cases, the size of the exclusion region and the optimal routing depend on transmission powers, and that the optimal MAC design depends on the choice of routing. Nevertheless, as we show with the example of 802.11 networks, a significant improvement over the existing 802.11 MAC can be achieved even with simpler, suboptimal strategies. Although this result is shown by simulations on a simplified model, it still gives further directions on how to improve the performance of RTS/CTS based protocols.

EPFL2005

A cross-layer design of wireless ad-hoc networks

EPFL2005

Routing and search on large scale networks

Dominique Florian Tschopp

EPFL2010