A Scalable Routing Method for Irregular Mobile Ad Hoc Networks

We designed the terminode routing protoc ol with the objective to scale in large mobile ad hoc networks where the topology, or node distribution, is irregular. Our routing protocol is a combination of two protocols: Terminode Local Routing (TLR - to reach a close destination) and Terminode Remot e Routing (TRR - to send data to remote destinations). TRR is the key element to achieve scalability and reduce dependence on intermediate systems. Termin-ode routing uses anchored paths, a list of geographic points - that are not affected by nodes mobili ty -, rather than conventional paths of nodes. Terminode routing is completed by a low-overhead distributed method for discovering of anchored paths, and by a method for handling the inaccuracy of the location information. The presented simu-lation result s confirm that terminode routing performs well in different sized networks. In smaller ad hoc networks performance of terminode routing is comparable to MANET routing protocols. In larger networks, where MANET-like routing protocols break, terminode routing performs well; moreover, in larger networks that are not uniformly populated with nodes, terminode routing outperforms the existing location-based routing protocols.

Scalable routing protocols with applications to mobility

Ljubica Blazevic

In this thesis we study two routing problems related to mobility. The first problem concerns scalable multicast routing when there is a large number of multicast groups with a small number of receivers. Existing dense and sparse mode routing protocols have the following problems when the number of groups is large, but the groups are small: (1) high overhead in control traffic (dense mode), (2) poor utilization of backbone links and (3) complexity of management of single core routers (sparse mode). Our solution to this problem is the Distributed Core Multicast (DCM) routing protocol. DCM is an extension of the core-based tree approach and its architecture is based on several core routers per multicast groups. We explain the objectives achieved with DCM: (1) avoiding state information in backbone routers, (2) avoiding triangular routing across expensive backbone links, (3) scaling well with the number of multicast groups. DCM can be applied to support host micromobility in a large single Internet domain network, where every mobile host is assigned a multicast address in a domain it visits. The advantages of the multicasting-based approach for supporting host mobility are low latency and minimal disruption during handover. The second problem studied in this thesis concerns scalable routing in a large scale mobile ad hoc network. Ad hoc networks have gained increasing popularity in recent years because of their ease of deployment. No wired base station or infrastructure is needed, and mobile nodes communicate with each other using multi-hop wireless links. In ad hoc networks, routing protocols are challenged by the establishment of and the maintenance of multihop routes in the face of mobility, bandwidth limitation and power constraints. Routing protocols that rely on state concerning all links on the network, or all links on a route between a source and a destination result in poor scaling properties in larger mobile ad hoc networks. Position-based routing protocols are better suited for large mobile ad hoc networks. These protocols use the positions of nearby nodes and of packet's destination to make the packet forwarding decisions. We present a scalable routing protocol for a large mobile ad hoc network that is called terminode network. We call the nodes terminodes because they act as network nodes and terminals at the same time. Our routing scheme is a combination of two protocols called Terminode Local Routing (TLR) and Terminode Remote Routing (TRR). TRR is activated when the destination is remote and it uses the location of the destination obtained either via location management or by location tracking. TLR acts when the packet gets close to the destination and it uses routing tables that are built by nodes for close terminodes. The use of TRR results in a scalable solution that reduces dependence on the intermediate systems, while TLR allows to increase the probability of reaching the destination, even when it has moved considerably from the location that was known at the source. We use simulations to demonstrate terminode routing's scalability in different sized mobile ad hoc networks.

EPFL2002

Self Organized Terminode Routing

Ljubica Blazevic, Jean-Yves Le Boudec

We consider the problem of routing in a wide area mobile ad-hoc network called Terminode Network. Routing in such a network is designed with the following objectives. Firstly, it should scale well in terms of the number of nodes and geographical coverage, secondly, routing should have scalable mechanisms that cope with the dynamicity in the network due to mobility, and thirdly nodes need to be highly collaborative and redundant, but, most of all, cannot use complex algorithms or protocols. Our routing scheme is a combination of two protocols called Terminode Local Routing (TLR) and Terminode Remote Routing TRR). TLR is used to route packets to close destinations. TRR is used to route to remote destinations and is composed of the following elements: Anchored Geodesic Packet Forwarding (AGPF), Friend Assisted Path Discovery (FAPD), multipath routing and path maintenance. The combination of TLR and TRR has the following features: (1) it is highly scalable because every node relies only on itself and a small number of other nodes for packet forwarding; (2) it acts and reacts well to the dynamicity of the network because multipath routing is considered as a rule; and (3) it can be implemented and run in very simple devices because the algorithms and protocols are very simple and based on high collaboration. We have performed simulations of the TLR and TRR protocols in GloMoSim. The simulation results demonstrate that the routing protocol is able to deliver over 80% of user data in a large, highly mobile simulation environment whereas Dynamic Source Routing(DSR) achieves less than 10%.

2000

Nodes Bearing Grudges: Towards Routing Security, Fairness, and Robustness in Mobile Ad Hoc Networks

Sonja Buchegger, Jean-Yves Le Boudec

Devices in mobile ad hoc networks work as network nodes and relay packets originated by other nodes. Mobile ad hoc networks can work properly only if the participating nodes cooperate in routing and forwarding. For individual nodes it might be advantageous not to cooperate, though. The new routing protocol extensions presented in this paper make it possible to detect and isolate misbehaving nodes, thus making it unattractive to deny cooperation. In the presented scheme,trust relationships and routing decisions are made based on experienced, observed, or reported routing and forwarding behavior of other nodes. A hybrid scheme of selective altruism and utilitarianism is presented to strengthen mobile ad hoc network protocols in their resistance to security attacks, while aiming at keeping network throughput, or goodput, high. This paper focuses particularly on the network layer, using the Dynamic Source Routing (DSR) protocol as an example.

2002

Scalable routing protocols with applications to mobility

Ljubica Blazevic

EPFL2002