Sage Journals: Discover world-class research

Abstract

Mobile ad hoc networks are self-organizing networks that provide rapid network connectivity in infrastructureless environments. Most routing protocols designed for MANETs assume connected networks. Such a restriction directly limits the application domains of MANETs. In this paper, we study the problem of providing time-critical data delivery in sparse ad hoc networks where network partition can last for a long period, without imposing any restrictions on the node mobility. Supporting real-time communication with unconstrained mobility is important to many mission-critical applications such as battlefields and search and rescue in large-scale disaster areas.

In this paper, we propose microrouting networks consisting of tiny nodes similar to sensors but without transducers (called microrouters) as a substrate for time-critical data delivery in sparse MANETs. We describe the microrouting protocol for the resulting hybrid network which exploits the fact that microrouters are stationary, but are constrained by energy and memory. Key features of the microrouting protocol design include stateless architecture and localized route repair. We demonstrate the viability of the microrouting network architecture via detailed simulation evaluation. Our results show that microrouting networks running the microrouting protocol efficiently extend the connectivity of sparse MANETs and provide high packet delivery ratios.

Keywords

C.2.1.k Wireless communication C.2.2.d Routing protocols C.2.7.e Wireless C.2.8.c Mobile communication systems C.2.7.c Sensor networks

I. Introduction

A mobile ad hoc network (MANET) consists of a collection of wireless mobile nodes dynamically forming a temporary network without relying on any existing network infrastructure or centralized administration. A fundamental challenge in MANETs is the design of scalable and robust routing protocols that can provide any-to-any communication among its participants. Most routing protocols designed for MANETs assume connected networks, i.e., a multi-hop path exists between any two nodes. Such an assumption restricts the geographic area of operation to be a function of the number of nodes and their radio transmission range, and thus directly limits the application domains of MANETs.

In this paper, we study the problem of supporting real-time data delivery in sparse MANETs in which network partitions happen frequently and can last for a long period, without imposing any restrictions on the mobility of the participating nodes. One can envision many practical application scenarios in which a small number of mobile nodes (participants) are deployed in large geographic regions. Such sparse deployment scenarios can arise due to budgetary limitations, the nature of the applications, or physical constraints of the environment. For example, in a battlefield, several units of soldiers can be dispersed in a large combat zone. As another example, in a large disaster area, a large number of small teams of personnel can be roaming around performing search and rescue operations. Any mechanism supporting data delivery in such applications needs to satisfy the following three criteria:

Frequent network partitioning: The mechanism needs to be able to operate under frequent network partitioning, since the area covered by the mobile nodes may be large and any fixed infrastructure is not available or may have been damaged.

Real-time communication: The mechanism needs to support real-time communication as the tasks being carried out such as disaster relief are often time-critical.

Unconstrained mobility: The mechanism should not impose any controlled mobility as certain imposed movement of nodes may not be feasible due to the inhospitable terrain, enemy fire, obstacles due to a disaster, etc. Additionally, in such critical application scenarios, the tasks to be accomplished can be fundamentally more important than ensuring connectivity, i.e., the mobile nodes may not be able to simultaneously perform their duties efficiently and adjust their movements to ensure connectivity. For example, in disaster relief, it is more important to search a large area quickly than to stay connected but search a small area.

In summary many critical applications of MANETs like disaster relief and military operations are characterized by sparse deployment, real-time communication, and unconstrained mobility which require a new communication paradigm that is flexible, efficient, and easily deployable.

There have been several recent work on supporting data delivery in sparse or disconnected networks via exploiting the mobility of nodes in MANETs [1], [2], [3], [4], [5]. Such mobility-based protocols either exploit the existing mobility of the nodes to buffer and deliver messages across network partitions [2], [3], or require nodes to move in a controlled manner to ensure network connectivity [1], [4], [5]. Relying on existing node mobility for message delivery can suffer from high delays and potentially unreliable data delivery. Altering the movement of mobile nodes is limited to application scenarios where such altered movement is feasible and does not interfere with the tasks being performed. Therefore, these mobility-based approaches are unsuitable for the class of mission-critical applications that we envision.

In this paper, we propose to use microrouting networks consisting of tiny nodes, called microrouters, which are similar to sensors but without transducers as a substrate for data delivery in sparse MANETs. Unlike sensor nodes, such microrouters are expected to be cheaper, smaller, and have a higher lifetime since they do not need to be equipped with sensing devices that increase the cost, size, and energy usage. Like sensor nodes, such microrouters can be easily and quickly deployed to cover a geographic region in which a small number of mobile wireless nodes will be sparsely deployed to perform short-term or time-critical missions. For example, in Fig. 1 a military unit consisting of soldiers and vehicles deployed in a large area uses the underlying microrouting network to communicate and coordinate their activities. Such a substrate is easily deployable in inhospitable terrains or disaster stricken areas. At the same time, it decouples the mobility of these nodes (soldiers, rescue personnel, military vehicles, rescue robots, etc.) from the task of maintaining connectivity amongst them and thus the mobile nodes can optimize their mobility solely based on the need of the mission. Our study demonstrates that this substrate provides high data delivery rates with low overhead and delays for such sparse MANETs. We believe many mission-critical applications can greatly benefit from this new communication paradigm.

Figure 1

A microrouting network. Soldiers and military vehicles use the routing substrate to communicate.

A primary challenge in using microrouting networks is to design a multi-hop routing protocol that provides efficient and reliable data delivery to its mobile participants. The key characteristics of such a protocol are stateless operation, energy efficiency, and robustness. The protocol ideally should be stateless and robust since the microrouters are likely to be intermittently available due to frequent wake/sleep cycles for energy savings and due to external interference in hostile environments. Additionally, microrouters are energy- and memory-constrained devices which can only support minimal routing protocol capabilities.

The rest of the paper is organized as follows. Section II discusses previous work on data delivery in sparse MANETs. Section III describes the characteristics of microrouting networks and compares it with traditional ad hoc networks and sensor networks. Section IV provides a detailed description of the microrouting protocol for microrouting networks. Section V provides an analysis of the routing overhead incurred by the various components of the microrouting protocol. Section VI presents simulation results and finally, Section VII concludes the paper.

2. Related Work

Previous research on data delivery in sparse MANETs have largely focused on exploiting the mobility of nodes to buffer data packets during network partitions and forward data packets when the network is connected again. Such mobility-based protocols are thus suitable for delay-tolerant applications such as sensor data collection. These approaches can be classified as proactive and reactive schemes. Reactive schemes typically exploit the existing mobility of the nodes to buffer and deliver messages across network partitions, while proactive schemes require nodes to move in a controlled manner to ensure network connectivity.

Epidemic routing [2] is a reactive scheme in which disconnected nodes rely on their own mobility to allow them to get reconnected. It relies on random pair-wise exchanges of messages among nodes for eventual messages delivery. Subsequently, Davis et al. [3] propose a reactive scheme that exploits node movement patterns for efficient packet passing. Li and Rus [1] propose a proactive approach in which mobile nodes actively modify their movement for data delivery and network connectivity. It provides an algorithm that guarantees message transmission with minimum time and minimum trajectory modifications. More recently, two more proactive approaches have been proposed. In [5], Zhao et al. propose message ferrying which utilizes a special set of nodes called ferries with known non-random movement patterns which are used by nodes in the MANET for data delivery. In [4], Goldenberg et al. propose mobility as a network control primitive. They exploit controlled node mobility to provide adaptive, self-configuring networks that improve the communication performance.

A considerable amount of work has been done on topology control [6], [7], [8] which involves the adjustment of transmit powers of nodes in order to maintain certain network properties such as connectivity. However, this approach assumes that transmission powers can be arbitrarily adjusted and can lead to rapid energy drain of the nodes.

Several protocols [9], [10] have been proposed for sensing and data collection in sparse sensor networks that arise in many applications such as wildlife monitoring. They propose the use of mobile nodes to disseminate data in sparse sensor networks.

Instead of a larger number of small microrouters, a smaller number of larger devices such as UAVs, satellites, or mobile vehicle basestations could potentially be deployed/ used solely to enhance network connectivity without constraining the mobility of the existing nodes. However, such solutions could deplete the energy of the existing mobile nodes by requiring them to transmit over larger distances since these larger devices cannot be deployed ubiquitously. Additionally, unlike microrouters that can be sprayed anywhere, mobile vehicles may not be deployable in all scenarios due to the terrain. Further, with advances in manufacturing techniques, microrouters are likely to be more cost-effective than these approaches.

3. Microrouting Networks

In this section, we discuss the architecture of microrouters, the characteristics of the corresponding microrouting network, and the design principles of the microrouting protocol.

A. Microrouter Architecture

The microrouting networks we propose in this paper consist of microrouters that are similar to sensor nodes in sensor networks except that they do not contain any transducers for performing sensor operations in order to reduce costs and form factor. To be easily deployable, these microrouters need to be low cost and dispensable, and have a small form factor. Figure 2 shows a schematic diagram of a microrouter. Each microrouter is made up of a processing unit, a transceiver unit, and a power unit.

Figure 2

Architecture of a microrouter.

The processing unit is associated with a small memory unit, and implements the microrouting protocol (explained in Section IV). Like in sensor nodes, the memory unit available to the processing unit is a scarce resource. For example, the smart dust prototype has 512 bytes RAM and 512 bytes EEPROM [11] while the MICA2Dot [12] nodes have 128 Kbytes of program flash memory and 4 Kbytes EEPROM. The transceiver unit performs wireless communication. Typically the radio design of a microrouter can be similar to that used in current MICA motes. The power unit can be a one-time energy source such as a battery when a microrouting network is deployed for short-term missions. It can also be a power scavenging unit in medium-term to long-term deployment scenarios. In either case, microrouters need to be energy-efficient to extend the lifetime of the network.

We assume that the microrouters are not equipped with location finding units such as GPS for the following reasons as argued in [13]:

GPS units have a high production cost, especially when a large number of microrouters are to be equipped.

GPS devices may not be able to function in environments such as indoor locations or locations with dense foliage or obstacles that block the line of sight from GPS satellites.

The power consumption of the GPS devices would reduce the battery life of microrouters.

A GPS and its antenna increase the form factor of the microrouters. This inhibits the easy deployment of microrouters. Note that assuming no position information reduces the applicability of sensor routing protocols that can deliver data to mobile sinks [14] in microrouting networks.

In summary, microrouters are memory-constrained, energy-constrained, low cost devices. Since the goal of a microrouting network formed by stationary microrouters is to provide data delivery to mobile nodes in a sparse MANET, the multi-hop routing protocol needs to be supported on both the microrouters and the mobile nodes in the resulting hybrid network. For simplicity, in the rest of the paper, we will refer to the hybrid network as the microrouting network.

B . Characteristics of Microrouting Networks

We discuss the unique characteristics of microrouting networks by comparing them to traditional mobile ad hoc networks and sensor networks as shown in Table I.

Table 1
Comparison of the three network architectures

Feature Ad-Hoc Sensor μRouting

Size small-medium large large

Range medium small small

Density medium high high

Communication any-to-any many-to-one any-to-any (mobiles)

Addressing global ID no global IDs global ID

Aggregation No Yes No

Feature	Ad-Hoc	Sensor	μRouting
Size	small-medium	large	large
Range	medium	small	small
Density	medium	high	high
Communication	any-to-any	many-to-one	any-to-any (mobiles)
Addressing	global ID	no global IDs	global ID
Aggregation	No	Yes	No

MANETs are envisioned to have typically few hundreds of nodes, whereas sensor networks are much larger in scale. A microrouting network has a large number of microrouters similar to a sensor network to ensure coverage and connectivity. The typical radio range in a MANET is higher than most sensor nodes. In contrast, a microrouting network may have heterogeneous ranges, small for the microrouters and larger for the mobile nodes. Also, the node density of a MANET is generally lower than that of a sensor network. The node density of a microrouting network is similar to that of a sensor network. In a MANET, all the nodes are generally mobile and thus the topology is highly dynamic. A sensor network has typically static sensor nodes. However, a change in topology can still occur due to failure of a sensor or due to sensors that have run out of energy. Thus, sensor networks have a slowly changing topology. In contrast, a microrouting network has nodes that are constantly mobile and microrouters that are static and susceptible to failures and energy constraints similar to in a sensor network. In MANETs and microrouting networks, any mobile node can communicate with any other mobile node. However in a sensor network, the sensors typically communicate only with the sink, resulting in a many-to-one communication pattern. Finally, in a MANET, globally unique identifiers (IDs) are required to identify and communicate with all the nodes. In a microrouting network, unique IDs are similarly required for both mobiles as well as microrouters to enable end-to-end connection establishment and maintenance. However, microrouters can be addressed separately from mobile nodes since they do not initiate or terminate a flow. Sensor nodes need not be individually addressable for typical sensing applications.

C. Microrouting Protocol Design Principles

The unique architecture of microrouters and the characteristics of microrouting networks dictate the following design principles for the multi-hop microrouting protocol.

Stateless Architecture: The protocol for the microrouters should be stateless since microrouters are resource-constrained devices with limited memory and energy source. In addition, they also suffer from intermittent availability due to frequent wake-sleep cycles when using energy saving techniques. Thus, stateless techniques like source routing may be more useful in microrouting networks since they can be efficient in the presence of intermittent availability.

Localized Route Repair: The protocol running on the mobile nodes should minimize the frequency and extent of route discoveries. In large scale networks, such flooding-based route discoveries lead to the broadcast storm problem [15] as well as energy drain. More importantly, any repair technique performed by the microrouters should ideally be stateless.

Previously proposed sensor routing protocols can not be readily used in microrouting networks. The primary goals of sensor routing and data dissemination protocols are data aggregation and efficient dissemination. Most protocols propose the use of data-centric routing in place of node-centric routing required in a microrouting network. Also, the majority of the protocols developed for sensors do not deal with highly dynamic topology caused by mobility of nodes, whereas microrouting needs to handle such mobility. Exceptions are dissemination protocols such as TTDD [14] which handle only sink mobility. However, TTDD assumes the presence of GPS on sensor nodes. Additionally, both endpoints of a flow in a microrouting network may not be resource-constrained and may have replenish-able energy resources unlike in a sensor network. This would not be exploited by sensor routing protocols.

Similarly, off-the-shelf MANET routing protocols can not be readily used in microrouting networks. Most of the protocols proposed assume resource rich nodes all along the path which can keep a large amount of state and perform a lot of computation. Hop-by-hop routing protocols like AODV [16] and DSDV [17] need to maintain state on intermediate nodes for forwarding packets and consequently their routing table sizes grow with the network size or the number of active packet sources. For example, in AODV, each intermediate node along the route maintains a routing table for forwarding packets, a packet buffer for local repair, and backward pointers for route error propagation. In the presence of intermittent availability, such state may be lost frequently along paths causing costly rediscoveries. In DSR, each node maintains a cache of source routes that may be a graph [18] or a list of paths [19]. Intermediate nodes use the cache to salvage packets with stale routes and reply to route requests. Additionally, AODV, DSR, and TORA [20] are unsuitable for microrouting networks since they all frequently invoke global flooding of route requests to discover routes to destinations. Finally, protocols developed for MANETs fail to take advantage of the static nature of microrouters in microrouting networks.

4. Microrouting Protocol Design

This section presents the design of the microrouting protocol, μRP, for supporting data delivery between sparsely deployed mobile nodes in microrouting networks. μRP is used as a representative routing protocol to demonstrate the viability of the microrouting network architecture. Conceptually, μRP has two distinct and separate modules. The first module runs on the energy- and memory-constrained microrouters. The second module runs on the mobile nodes which have larger memory and more energy. The two modules are designed to inter-operate seamlessly to provide end-to-end connectivity between mobile nodes while exploiting the characteristics and capabilities of the devices they run on. Since μRP uses source routing, it is similar to DSR in many aspects and can be thought of as an adaptation of the DSR protocol for microrouting networks.

A. Node Addressing

Each mobile node is addressed using an IP address. We assume some address assignment algorithm exists which assigns these to mobile nodes. Since the microrouters do not act as endpoints of communication, we can efficiently encode their addresses with the minimum number of required bits rather than using 32-bit IP addresses. This significantly reduces the overhead of using stateless source routing which encodes addresses in packets. Additionally we assume that the address of a device can be used to distinguish between it being a microrouter or a mobile node. This can be easily achieved, for example, using a predefined prefix for the addresses of the microrouters.

B. Transmission Range

Mobile nodes and microrouters can potentially have different transmission ranges, and this hybrid nature of microrouting networks can result in unidirectional links. The results in [21] show that using unidirectional links does not generally improve performance and should be avoided. Thus, in a microrouting network, the transmission range of the mobile nodes is adjusted to be similar to that of the microrouters. This also conserves the energy of the mobile nodes.

C. Route Discovery

μRP discovers an initial route between a pair of mobile source and destination nodes reactively. When a mobile node S needs to send packets to a destination D for which it has not discovered a route, it floods a QUERY packet into the microrouting network in a way similar to route discovery in reactive routing protocols such as DSR and AODV. Each microrouter that has not previously received the Query rebroadcasts it after appending its address to the accumulated path in the packet. Because of the sparsity of mobile nodes, any route between a source and a destination will likely consist of multiple microrouters as intermediate hops. To maximize the lifetime of a route, only microrouters forward Query packets while mobile nodes along the way ignore such packets unless they are the queried destination node. An initial route discovered in this way will consist of only stationary microrouters as intermediate hops and only the first and the last hops will be affected by the mobility of mobile nodes.

Due to memory constraint, the microrouters along the path of the reply do not cache any route information and consequently no intermediate replies are possible for route discoveries. Once the Query reaches D, D sends a Query Reply back to S by reversing the accumulated path. When the Query Reply reaches S, S adds the link information in the route to a graph cache. A graph cache stores individual links of paths to build a topological graph of the network. Each link is assigned a timeout value as follows: Links between microrouters are assigned a large timeout since these links are not affected by mobility. Links involving a mobile node are assigned a timeout value based on an adaptive scheme that uses past mobility history of the nodes involved in the link. This adaptive scheme is similar to the graph cache scheme proposed in [18]. The source node then runs a single source shortest path algorithm to discover a route for sending packets to D. To maximize the lifetime of a route, the shortest path algorithm is modified to ignore mobile nodes as intermediate hops in a route. Figure 3(a) shows an example of an initial route discovered that connects the source S and the destination D.

Figure 3

μRP route discovery and repair.

D. Local Route Repair

Since the two end nodes of a route, i.e., the source and destination nodes, are mobile, both the first hop and the last hop of the route will break as the two nodes move. Figure 3(b) shows that the source has moved from S to S∗, which is beyond the transmission range of the first microrouter M₁, breaking the first hop. Similarly, the destination node has moved from D to D∗, which is beyond the transmission range of microrouter M_n. This movement breaks the last hop of the route.

μRP uses two different local repair mechanisms to fix breakage of the first hop and the last hop, instead of frequently rediscovering a new route using a network-wide flooding.

1) Source local repair

On the source node side, μRP uses a reactive scheme for local route repair. This reactive scheme is low overhead and does not require any maintenance of state. When the first hop breaks, the source node first tries to use its current graph cache to construct an alternative route to reach M₁ or other nodes on the path. If such a route cannot be found, it performs a search of its L-hop neighborhood by broadcasting a Neighborhood Discovery packet. Each microrouter that receives a Neighborhood Discovery for the first time appends itself to the header and rebroadcasts the Neighborhood Discovery. When the Neighborhood Discovery has traveled L hops, the last microrouter sends a Neighbor Reply using the encoded L-hop route in the packet back to the source node. The source adds the link information received in Neighbor Replies into its graph cache. This L-hop flooding provides the source with a path to M₁ which can then be concatenated with the old route from M₁ → D. Thus, the source repairs the route by running a single source shortest path algorithm on its graph cache. Figure 3(b) shows that the new route now goes through microrouters A and B before reaching M₁. Note that the repaired path may not go through M₁, for example, if it discovers a shorter or equally long route to some other node on the path, e.g., M₂. If the source repair does not succeed, a route discovery is initiated. The source side local repair involves an L-hop flooding of a Neighborhood Discovery packet, followed by the replies from the nodes on the perimeter of the L-hop flooding zone.

2) Destination local repair

On the destination side, μRP could potentially use the same technique as used on the source side to repair broken paths, i.e., the last microrouter on the path to the destination can invoke a Query to search for a route to the destination. Upon discovering a new route to the destination, the microrouter can then send packets using this route. We avoid this technique in μRP for the following reasons:

A microrouter is memory constrained and such a technique would require it to buffer data packets until the route is repaired.

Invoking a Query from a microrouter would require it to maintain state in order to monitor the progress of the Query and potentially retransmit it.

A microrouter would not be able to adhere to its sleep-wake duty cycles since it would have to remain awake to successfully receive a reply to the Query.

Due to all these factors, on the destination node side, μRP uses an adaptive proactive scheme for local route repair which does not burden the microrouters with excessive memory or processing requirements. After replying to an initial route discovery, the destination node D prepares to receive data packets. As it moves, it invokes a beaconing procedure to leave a “trail” in the microrouting network for data packets to follow. Periodically, D broadcasts a Trail packet with a TTL value of K. Upon receiving a Trail packet for the first time, a microrouter checks if it is within K hops from D and if so, it inserts its ID into the packet and rebroadcasts the packet. Such K-hop broadcast will reach M_N if it is within K hops from D, and M_N stores the partial multi-hop route between itself and D in a trail cache. When M_N discovers that the direct hop to D is broken in trying to send a data packet, for example, as shown in Figure 3(b), it consults its trail cache to find a route towards the destination node. Figure 3(b) shows that microrouter M_N repairs the route using microrouter C to reach the destination at its new position D∗. Additionally, an error packet is sent back to the source whenever a route is repaired by a microrouter. The error packet contains the broken link as well as the repaired local route to the destination node. Upon receiving the error packet, the source node D removes the broken link from and stores the repaired route into its local graph cache and recalculates the shortest path to D when sending the next data packet.

When node D moves at high speed, it is possible that it has moved beyond K hops from M_N by the time the next data packet reaches M_N. In this case, the route is repaired and extended recursively till it reaches the destination.

Note that node trails can be used for repairing all connections intended for a particular node from multiple sources. Also, note a mobile node initiates the periodic beaconing only if it is currently receiving data packets from other nodes, and periodic beaconing from a destination node can repair packets coming to it from multiple sources.

E. Pre-emptive Route Discovery

When S discovers a route to D initially, it records the original hop count of the route (H) in its localization table. As time progresses, due to route repair on both sides, this route could potentially shrink or grow in hop length. S keeps track of the hop length growth and if it grows to H + h hops where h = α·H, the node performs a pre-emptive route discovery. The motivation behind this pre-emptive rediscovery is to prevent repaired routes from becoming arbitrarily long by discovering shorter routes to the destination. If routes become too long, that very fact can adversely affect the delivery of packets. Thus, preemptive discovery effectively bounds the length that a route between any two nodes is allowed to grow relative to the shortest path between the two nodes at the cost of slightly increased overhead. α is a system parameter chosen to be 0.75 for reasons explained in Section VI-B.

In order to localize the query, the new route discovery is limited to a radius of H + h hops which will cover the expected zone the destination node D would exist in.

F. Handling Microrouter Failures

Since microrouters have limited energy and can be deployed in hostile environments such as enemy territories or disaster recovery areas, they may fail unexpectedly while serving as intermediate hops for some active routes. μRP uses an intermediate repair mechanism to deal with such failures. When a delivery failure is detected by a microrouter when forwarding a data packet to another microrouter, it changes the packet to broadcast mode and initiates a 2-hop broadcast of this data packet to attempt to reach the next hop node after the failed node in the source route. In addition, it sends an error packet to the source to inform it of the link break. If the next hop node after the failed node in the source route receives the broadcast, it changes the data packet mode back to source routing and continues the transmission. Due to the low bandwidth in microrouting networks, congestion may cause failures to occur frequently. To compensate this, intermediate repair retries a unicast of the packet after a random backoff before initiating the 2-hop broadcast discussed above.

G. Memory Requirement

Each microrouter uses a constant amount of memory. It needs to store a sequence number per source node. Additionally each node has a small cache of m source routes for storing node trails. m is configured to be as small as 5 to conserve memory resources on the microrouters. Apart from this mini-cache, the microrouters store no other routing state. Note that unlike the DSR route cache in which each path is of length $O (\sqrt{N})$ , the routes stored in this mini-cache are of constant length equal to the trail depth K making the total size m·K·address_byte_size. In the worst case, even if we use IP addresses for the microrouters, this cache only requires 40 bytes of memory for K=2.

5. ANALYSIS

In this section, we analyze the routing overhead incurred by different components of μRP. such an analysis helps to understand the benefits of the local repair design principle of μRP and the choice of parameters in the operation of μRP.

We use $N_{r}^{A}$ to represent the number of microrouters in a region of radius r around node A. Consider a route from a source S to a destination D consisting of p links. The lifetime L_i of the ith link in the route is modeled as an exponential random variable. The first link (L₁) and the last link (L_p) in the route are between a mobile node and a microrouter and we assume their lifetimes are exponentially distributed with mean $\frac{1}{λ_{1}}$ and $\frac{1}{λ_{p}}$ respectively. The remaining (p − 2) links are between microrouters and the lifetimes of these links are each exponentially distributed with mean $\frac{1}{λ_{m}}$ Since the rate of link breaks between mobile nodes and microrouters are expected to be similar, λ ₁ = λ _p. Since microrouters are static, it is expected that the rate of link breaks between microrouters λ _m is much lower than λ ₁ and λ _p. Additionally, all link lifetimes are assumed to be independent of each other. Let the average speed at which a mobile node moves be υ, and the transmission range be R. In the following, we analyze the overhead per unit time incurred by each of the four components of μRP and compare the overhead of μRP with and without local repair.

a) Route Discovery

The route discovery procedure is invoked when a route to D is requested for the first time, and during subsequent occurrences of pre-emptive route discovery. All route breaks, either the source-to-microrouter, microrouter-to-microrouter, or microrouter-to-destination, are repaired locally. S performs a pre-emptive route discovery every time the hop length from S to D grows to H + h hops where h = α · H. With an average speed of υ, the average interval for the two end nodes to move beyond h = α · H hops away is proportional to $\frac{h \cdot R}{2 v}$ . The overhead for the source node to discover a route of maximum length H + h is approximately proportional to $N_{H + h}^{S}$ packets. Thus the total overhead per connection due to pre-emptive route discovery is $N_{H + h}^{S} \cdot \frac{2 υ}{h \cdot R}$ .

b) Source Side Repair

μRP uses a reactive scheme to locally repair the source-to-microrouter link of a connection when it breaks. The local repair involves an L-hop flooding of a Neighborhood Discovery packet, followed by the replies from the nodes on the perimeter of the L-hop flooding zone. The total packets transmitted are thus $2 N_{L}^{S}$ . The average interval for the breakage of the first link $\frac{1}{λ_{1}}$ is proportional to $\frac{R}{υ}$ . Since the packet may arrive less frequently than first link breakage, the total overhead for source side repair is at most $2 N_{L}^{S} \cdot λ_{1}$ . Note that in many cases a repair may be triggered at a much lower rate due to the use of the graph cache at the source which can be used to repair a broken link through another previously discovered neighboring microrouter. To ensure the L-hop source repair will continue to function, at least one repair is triggered before a node moves more than L-hops away.

c) Destination Side Repair

μRP uses a proactive scheme to locally repair the microrouter-to-destination link of a connection when it breaks. To leave a trail in the microrouting network, the destination node D periodically broadcasts a Trail packet with a TTL value of K. The overhead of such periodical broadcast is thus $N_{K}^{D} \cdot f_{t}$ , where f_t is the frequency of the broadcast. To ensure that D does not move beyond K hops within each broadcast period, f_t should be at least Kδp which is proportional to $K \frac{v}{R}$ .

d) Microrouter Failure Repair

The microrouter-to-microrouter local repair happens whenever such a link along the connection between S and D breaks due to either energy drainage, congestion, or unexpected interference in enemy territories. In this analysis, we assume the impact of congestion and interference from adversaries is insignificant compared to the effect of battery drainage. A route consisting of (p − 2) microrouter-to-microrouter links will experience a microrouter-to-microrouter link failure at an average rate of (p − 2) · λ _m per second under the assumption of independent and exponentially distributed link failures. Each microrouter failure although rare triggers a full route discovery. Thus the local repair overhead for microrouter failures is approximately proportional to N · (p − 2) λ _m, where N is the number of nodes in the network.

e) Comparison

We compare the overhead of μRP with that of μRP_basic which does not incorporate any local repair. Since in microrouting networks, intermediate nodes (microrouters) do not maintain a route cache due to resource constraints and thus cannot reply to discoveries, each flooded route discovery has a cost of N where N is the number of nodes in the network. The μRP_basic protocol initiates a route discovery on every route break detection. Thus the overhead incurred by μRP_basic in a time interval T is given by N + N · λ _basic · T, where λ _basic is the rate of route failure and the first term N reflects the cost of initial route discovery. We can define the lifetime of a route of length p as T_p = min(L₁, L₂, …, L_p) where L_i is the lifetime of the ith wireless link as described earlier.

Thus T_p is also an exponentially distributed random variable with a mean of $\frac{1}{λ_{b a s i c}}$ , where $λ_{b a s i c} = λ_{1} + (p - 2) \cdot λ_{m} + λ_{p}$

In summary, the overhead cost of μRP_basic is given by

C o s t_{b a s i c} = N + N \cdot (λ_{1} + (p - 2) \cdot λ_{m} + λ_{p}) \cdot T

and based on the analysis of the repair techniques, the overhead cost of μRP is

C o s t_{r e p a i r} = N + (2 N_{L}^{S} \cdot λ_{1} + N \cdot (p - 2) \cdot λ_{m} + N_{K}^{D} \cdot f_{t} + N_{H + h}^{S} \cdot \frac{2 v}{h R}) \cdot T

The above equations show that without repair, the protocol incurs much higher overhead than with local repair. Since the values of L and K are very small, i.e., in the range of 2 and 3 as shown in Section VI, the overhead for a first or last hop repair is far less than that of a route discovery, as $N_{L}^{S} ≪ N$ and $N_{K}^{S} ≪ N$ . When link breaks between microrouters, both protocols need to perform a route discovery. However, this happens much less frequently compared to link breaks between mobile nodes and microrouters, i.e., $λ_{1} = λ_{p} ≫ (p - 2) \cdot λ_{m}$ . Thus the route discovery overhead caused by them is expected to be overshadowed by the route discoveries due to the first and last link breaks in μRP_basic. Finally, pre-emptive route discovery happens on average $\frac{h}{2} = \frac{H \cdot α}{2}$ times less often than first or last link breaks. Thus the overhead caused by them is expected to be far less than route discoveries caused by first or last link breaks in μRP_basic.

6. Performance Evaluation

In this section, we first describe our simulation methodology and then evaluate the routing performance of μRP. our performance comparison primarily focuses on μRP since it is to the best of our knowledge the first protocol developed for microrouting networks. Other protocols developed for MANETs such as DSR and AODV cannot be fairly compared to μRP since they involve maintaining a lot of state (packet buffers, route caches, next hop tables, black lists for route errors, etc.) and processing on the microrouters.

A. Simulation Methodology

We implemented μRP in the Glomosim [22] simulator. Glomosim is a widely used simulator for wireless networks with a comprehensive radio model. The effects of multiple access interference, capture, RF propagation, signal strengths, and propagation delays are modeled in Glomosim.

1) Microrouter Model and Deployment

We model our microrouters after MICA Motes [12] except that they do not have transducers. The simulator implements a 802.11-based MAC layer and the microrouters use this as the MAC protocol. 802.11 has been widely used [23], [24], [14] in simulation evaluation of sensor networks. In this study, we do not assume the use of topology control algorithms during the deployment of the microrouters. The devices are assumed to be sprayed and randomly placed in the target area. The experiments consider a data rate of 200Kbps and a 220m radio range for the microrouters and mobile nodes similarly as in [24]. This range can already be achieved by the MICA2Dot [12] motes currently available, while newer 802.15.4 Motes will achieve a rate of 250Kbps.

2) Traffic and Mobility Models

We use the modified random waypoint mobility model [25] to simulate the movement of mobile nodes. Nodes move without pausing at a speed randomly chosen between [1 –9] m/s. Traffic is generated and received only by the mobile nodes and the microrouters only forward traffic. We assume constant bit rate (CBR) traffic, same as in previous MANET protocol comparison studies (e.g. [26], [27]). Each mobile node initiates one random CBR connection to another mobile node with a packet rate of one 32-byte packet/sec. The simulation duration is 15 minutes and the simulation results are averaged over multiple runs.

3) Energy Model

Efficient usage of the limited energy of microrouters can extend the operation lifetime and connectivity for mobile users. Microrouters consume energy due to computation (packet processing, routing, etc.) and wireless communication. Our focus in this study is on the costs of wireless communication. Since our work focuses on the routing layer, we do not assume a lower layer protocol that coordinates the wake/sleep cycles of microrouters. Since a microrouter's radio is expected to be similar to that of a MICA Mote, we adopt the radio energy consumption parameters of the MICA2Dot Motes [12]. Specifically, the current drawn for transmission is 25mA and that for reception is 8mA. We modified the Glomosim radio layer to include these energy consumption metrics. The transmit and receive durations of each node were logged and the corresponding energy consumption calculated.

4) Metrics

We use the following four metrics to evaluate the performance of μRP:

Routing overhead — the number of control packets transmitted to discover and maintain routes between mobile nodes.

Packet delivery ratio (PDR) — the ratio of the number of successfully received data packets to the number of data packets sent.

Delay — the average time between transmission and reception of data packets. This metric accounts for all possible delays caused by buffering during route discovery latency, queuing at the interface queue, retransmission delays at the MAC, and propagation and transfer times.

Energy consumption — the communication energy consumed during transmission and reception, for microrouters only.

B. Effect of Local Repair Ranges

In this section, we evaluate the effects of two important design choices for μRP: the node trail depth K used in destination repair and the sender repair depth L. The evaluation scenario consists of 20 mobile nodes continuously moving in an area of 16 km². Microrouters are deployed with a density of 10 microrouters per radio range.

Table 2 depicts the effect of varying K on the performance of μRP. Apart from the overall overhead, PDR, and delay, we also show the number of packet drops that occur between the last microrouter on a path and the destination mobile node as well as the overhead incurred due to Trail packets.

Table 2
Effect of destination repair parameter K · L=3

K 0 1 2 3

Overhead 391,890 408,979 128,450 158,446

Dest. repair 0 1800 20,327 49,421

PDR 97.7 97.7 99.9 99.9

Delay 0.16 0.17 0.15 0.18

Drops (M_n → D) 371 372 3 4

K	0	1	2	3
Overhead	391,890	408,979	128,450	158,446
Dest. repair	0	1800	20,327	49,421
PDR	97.7	97.7	99.9	99.9
Delay	0.16	0.17	0.15	0.18
Drops (M_n → D)	371	372	3	4

When node trails are not used (K=0), 371 packets are dropped due to breaks between the last microrouter and the destination, and μRP incurs an overhead of 391,890 packets. When node trails are used, K=2 is the best choice. At K=2, the number of drops reduce from 371 to 3 while the overall overhead reduces by 67%. This is because after each repair, a special repair error and the repaired local route are sent back to the source of the packet, avoiding costly route discoveries. Additionally, the PDR is increased by 2%. As K is increased further, the proactive beaconing overhead increases without an increase in rescued packets.

Table 3 depicts the effect of varying L on the performance of μRP. The repair overhead is due to Neighborhood Discovery and Neighbor Reply packets. The number of queries sent reflects the repair success rate. The lower the success rate of repair, the more the queries sent and thus the higher the total overhead.

Table 3

Effect of sender repair parameter L · K=2

L	0	1	2	3	4
overhead	237,342	182,535	132,381	128,450	140,901
Sender repair	0	1,565	6,674	14,223	23,119
PDR	99.9	99.9	99.9	99.9	99.9
Delay	0.14	0.15	0.16	0.15	0.17
Query	297	201	115	106	108

The results show that a value of L=3 results in the lowest total overhead due to the lowest number of queries sent. Also, an increase beyond L=3 is not beneficial since the repair overhead grows without any increase in the success rate of the repair. Note that sender side repair is more flexible and robust since it is performed by a mobile node which can use its graph cache to repair routes aggressively.

Table 4 depicts the effect of varying α on the performance of μRP. In the table, PQuery is the total number of pre-emptive Query packets transmitted. The results show that a value of α =0.75 provides the best tradeoff between routing overhead, path length, and delay. As α increases, the number of pre-emptive queries sent decreases at the expense of higher path length and more route breaks. Increasing α beyond 0.75 results in increased delays and path lengths while not significantly reducing the overhead. This occurs due to the increased route errors due to longer paths with α =1 which offset the savings in pre-emptive queries. This result indicates that repairing paths for a longer period of time (using a larger value of a) can be counter productive. μRP achieves a good tradeoff between the routing overhead and the path length by using pre-emptive queries.

Table 4

Effect of pre-emptive request control factor α · K=2 and L=3

α	0.25	0.5	0.75	1
Overhead	161,467	134,996	128,450	128,035
PDR	99.9	99.9	99.9	99.9
Delay	0.15	0.16	0.15	0.17
PQuery	85	43	25	18
Avg. Path Len.	11.4	11.5	11.7	12.5

Table 5

Capacity of microrouters

Mobiles	10	20	30
overhead	109,731	128,450	326,732
PDR	99.88	99.9	99.9
Delay	0.22	0.15	0.3
Energy	522.1	620.5	1605.94

C. Effect of Local Repairs

In this section, we evaluate the effectiveness of the three local repair mechanisms in μRP: sender side repair, intermediate repair, and destination side repair. The evaluation scenario consists of 20 mobile nodes continuously moving in terrains with varying areas ranging from 1 to 36 km². Microrouters are deployed with a density of 10 microrouters per radio range.

Figure 4 depicts the performance of various versions of μRP. The basic version of μRP depicted has no repair whereas the final version of μRP has all three local repair techniques. The three other curves depict the performance of μRP with each feature individually turned on. The following important observations can be made from the results. Firstly, μRP with all features turned on significantly reduces the overhead (e.g. by 80% in 36km²) and energy consumption (e.g. by 72% in 36km²) while always delivering 99% of the packets as the size of the microrouting network increases. This high data delivery rate is essential in critical military and disaster relief applications. The results show that stateless repair techniques used in μRP can significantly reduce the overhead and energy consumption in microrouting networks while keeping the microrouters as simple as possible. Secondly, destination side repair using node trails is the single feature that improves the performance of μRP_basic the most. This technique is effective in spite of using a small fixed size cache (to store trails) and not using any packet buffers (for salvaging packets). Thirdly, all versions of μRP have an acceptable delay which grows slowly as the network size increases. Delays are increased due to the limited bandwidth of microrouters (200Kbps) and large distances traveled by the packets. However, these delays are acceptable compared to reactive mobility-assisted schemes which may have unbounded delays.

Figure 4

Effect of local repair techniques on routing overhead, PDR, delay, and energy consumption. The x-axis corresponds to the side length of the square terrain in meters, e.g., 5000m corresponds to an area of 25 km².

D. Path Length Behavior

A side effect of the local repair mechanisms used by μRP is that routes between nodes may grow longer and longer as more and more sender side and destination side repairs are carried out without a global route discovery. However, the graph cache used by μRP can naturally discover shortcuts in routes. Additionally, μRP pre-emptively generates route queries when path lengths grow too large as explained in the design. These two mechanisms help to ensure that path lengths remain close to the current physical proximities of the sources and destinations.

Figure 5 shows the evolution of the path lengths (number of hops) for successfully delivered packets over the duration of the simulation with and without the local repair features. Three different connections are randomly chosen out of the 20 connections, and the path lengths of the packets that travel over each of these connections are depicted. The results show that although μRP uses slightly longer path lengths because of its repair features, it is able to adapt to changes in the proximities of the connection endpoints due to its pre-emptive queries and graph cache based route shortening. For example, in both connection 2 and connection 3, the path lengths initially grow significantly larger than the shortest path between the endpoints. However, μRP quickly detects such changes and reduces the path length pre-emptively to better reflect the physical proximity of the connection endpoints. Note that although longer path lengths cost more energy to deliver packets, μRP reduces the overall energy consumption by limiting costly flooding-based route discoveries.

Figure 5

Variation of the path length when MRP repair feature is enabled as a function of simulation time.

E. Effect of Deployment Area and Density

This section evaluates the performance of μRP under varying microrouter density and deployment scenarios. These results are useful in determining the number of microrouters required for a given area. We vary the microrouter density d in a given area as 2, 5, 10, and 15 microrouters per radio range. As before, we vary the area of deployment from 1 to 36 km². In each chosen area, 20 mobile nodes are randomly distributed.

Figure 6 depicts the performance metrics for μRP as the terrain area is varied and the network becomes increasingly sparse. The results show that as expected with increased network area and minimal microrouting support (d = 2), the PDR falls quickly as the network area grows. The results show that a density of 10 microrouters per radio range is sufficient for adequate packet delivery with low overhead. Increasing d to 15 does not improve packet delivery bit increases the overhead and energy consumption. Interestingly, a d of 5 also provides good PDR with low overhead. However, this density is not as resilient to failures as we show in Section VI-F. We also show what the performance would be when no microrouters exist. This scenario involves running DSR on each mobile node in a sparse ad hoc network. As expected, due to the sparse connectivity and frequent partitions, DSR has the lowest PDR. The slightly higher PDR of DSR compared to MRP (d = 2) in the smallest network size is because the density of mobile nodes is high enough that they can form multi-hop routes.

Figure 6

Effect of microrouter density on routing overhead, PDR, delay, and energy consumption. The x-axis corresponds to the side length of the square terrain in meters, e.g., 5000 corresponds to an area of 25km².

Thus, the provisioning of microrouters should be based on both the connectivity required as well as the failure rate. Although a reduced density of microrouters may provide adequate connectivity, the resilience of the microrouting network to failure reduces as well.

F. Resilience to Failures

In this section, we evaluate the resilience of μRP to failure of microrouters. Such failure could be due to the hostile environment, physical destruction, or depletion of energy. In the absence of repair and recovery techniques in μRP, such failures would significantly affect packet delivery. We denote failure rate β as the percentage of microrouters that will fail on average over the simulation duration. For example, β=10% means that on average 10% of the microrouters will fail at random times in the simulation duration (15 minutes). A failure rate of 100% means on average all nodes will fail by the end of the simulation duration. We assume that a failure renders a microrouter unusable.

Figure 7 depicts the performance of μRP deployed with two microrouter densities (5 and 10) for a terrain of 16 km². The results show that PDR for a density of 10 drops gradually as the number of failure increases and only drops significantly for a massive number of microrouter failures in the network. A lower density of 5 performs worse because the connectivity is affected more in sparser networks. Overall, μRP is quite resilient to failures. The stateless design of μRP ensures that such failures do not significantly degrade data delivery since μRP routing and repair techniques do not rely on any specific microrouter to ensure data delivery. Packets can be forwarded by neighboring functioning microrouters without incurring extra overhead.

Figure 7

Effect of microrouter failures on routing overhead and PDR.

G. Scalability of Microrouting Networks

In this section, we evaluate the scalability of microrouting by varying the number of mobile nodes deployed in an area. We consider an area of 25 km² and vary the number of mobile nodes deployed from 10 to 30 in that area. Table 4 depicts the performance results. Note that increasing the number of mobile nodes increases the data traffic volume in the network.

The results show that as the number of mobile nodes in the network increases from 10 to 30, μRP routing overhead increases superlinearly. This happens due to the increased number of Query packets and increased congestion, caused by the low bandwidth available in the microrouters and higher data traffic volumes in the network. However, the PDR is maintained at close to 100%, suggesting that μRP scales well with higher loads due to its low overhead which leaves sufficient network capacity for data packets. With future increases in bandwidth capability of Mote-like devices, the scalability of microrouting networks are expected to improve.

7. Conclusions and Future Work

In this paper, we proposed microrouting as a new paradigm for real-time communication in sparse mobile ad hoc networks without imposing any controlled mobility on the participating nodes. Microrouting employs microrouting networks consisting of low cost and easy to deploy microrouters that are similar to sensors but without transducers to provide the connectivity in a geographic area in which a small number of mobile hosts will be sparsely deployed. We designed a new routing protocol to demonstrate the viability of the resulting hybrid microrouting network architecture. The microrouting protocol for the microrouting network takes advantage of the immobility of microrouters to improve the robustness of the routes, while maintaining minimal state at the microrouters to satisfy their energy and memory constraints. Our evaluation results showed that microrouting networks running the microrouting protocol effectively extend the connectivity of sparse ad hoc networks.

Currently, we are investigating several uses of and issues in deploying microrouting networks. We plan to study how to use cross-layer techniques to efficiently integrate μRP and other lower layer energy conserving protocols such as SMAC [28] to further increase the lifetime of microrouting networks. We are studying security and trust extensions to μRP to enable its deployment in hostile environments such as battlefields. Since critical applications can benefit from group communications (e.g. between all medics in an area), we plan to study multicast and anycast extensions to μRP. We are also looking at whether localization and position estimation techniques in microrouters can improve the performance of microrouting networks and provide location-aware services to mobile nodes without using GPS. In such situation geographic routing and location service schermes tailored for microrouting networks are an interesting issue of research. Another interesting convergence area is whether a microrouting network can also be used for sensing. Many scenarios can be envisioned in which both functionalities may be required. A key question is whether a single integrated protocol can efficiently provide many-to-one and any-to-any communication in such an integrated network.

References

, and Rus

, “Sending messages to mobile users in disconnected ad-hoc wireless networks,” Proc. of ACM MobiCom, August, 2000.

Vahdat

, and Becker

, “Epidemic routing for partially connected ad hoc networks,” Duke University Tech. Rep. CS-200006, 2000.

Davis

J. A.

Fagg

A. H.

, and Levine

B. N.

, “Wearable computers as packet transport mechanisms in highly-partitioned ad-hoc networks,” Proc. of IEEE ISWC, 2001.

Goldenberg

D. K.

Lin

Morse

A. S.

Rosen

B. E.

, and Yang

Y. R.

, “Towards Mobility as a Network Control Primitive,” Proc. of ACM MobiHoc, 2004.

Zhao

Ammar

, and Zegura

, “A message ferrying approach for data delivery in sparse mobile ad hoc networks,” Proc. of ACM MobiHoc, May, 2004.

Ramanathan

, and Hain

, “Topology control of multihop wireless networks using transmit power adjustment,” Proc. of IEEE INFOCOM, March, 2000.

Wattenhofer

Bahl

, and Wang

, “Distributed topology control for power efficient operation in multihop wireless ad hoc networks,” Proc. of IEEE INFOCOM, April, 2001.

Lloyd

Liu

Marathe

Ramanathan

, and Ravi

, “Algorithmic aspects of topology control problems for ad hoc networks,” proc. of ACM MobiHoc, 2002.

Beaufour

Leopold

, and Bonnet

, “Smart-tag based data dissemination,” Proc. of ACM WSNA, 2002.

10.

Shah

Roy

Jain

, and Brunette

, “Data MULEs: Modeling a Three-Tier Architecture for Sparse Sensor Networks,” Proc. of IEEE SNPA, 2003.

11.

Kahn

Katz

, and Pister

, “Emerging challenges: Mobile networking for smart dust,” J. Comm. Networks, 2, 3, 188–196, Sept., 2000.

12.

Crossbow Technology Inc. , www.xbow.com, Founded 1995, retrieved January 2006.

13.

Savvides

Han

C.-C.

, and Strivastava

M. B.

, “Dynamic fine-grained localization in ad-hoc networks of sensors,” Proc. of ACM MobiCom, July, 2001.

14.

Luo

Cheng

, and Zhang

, “A two-tier data dissemination model for large-scale wireless sensor networks,” Proc. of ACM MobiCom, September, 2002.

15.

S.-Y.

Tseng

Y.-C.

Chen

Y.-S.

, and Sheu

J.-P.

, “The Broadcast Storm Problem in a Mobile Ad Hoc Network,” Proc. of ACM MobiCom, August, 1999.

16.

Perkins

C. E.

, and Royer

E. M.

, “Ad hoc on-demand distance vector routing,” Proc. of IEEE WMCSA, February, 1999.

17.

Perkins

C. E.

, and Bhagwat

, “Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers,” Proc. of ACM SIGCOMM, August, 1994.

18.

Y.-C.

, and Johnson

D. B.

, “Caching Strategies in On-Demand Routing Protocols for Wireless Ad Hoc Networks,” Proc. of ACM MobiCom, August, 2000.

19.

Johnson

D. B.

, and Maltz

D. A.

, Dynamic Source Routing in Ad Hoc Wireless Networks. Kluwer Academic, 1996.

20.

Park

V. D.

, and Corson

M. S.

, “A highly adaptive distributed routing algorithm for mobile wireless networks,” Proc. of IEEE INFOCOM, April, 1997.

21.

Marina,t

M. K.

and Das

S. R.

, “Routing performance in the presence of unidirectional links in multihop wireless networks,” Proc. of ACM MobiHoc, September, 2002.

22.

Zeng

Bagrodia

, and Gerla

, “Glomosim: A library for parallel simulation of large-scale wireless networks,” Proc. of PADS Workshop, May, 1998.

23.

Intanagonwlwat

Govindan

, and Estrin

, “Directed diffusion: a scalable and robust communication paradigm for sensor networks,” Proc. of ACM MobiCom, August, 2000.

24.

Blum

Nagaraddi

Wood

Abdelzaher

Son

, and Stankovic

, “An Entity Maintenance and Connection Service for Sensor Networks,” Proc. of MobiSys, May, 2003.

25.

Yoon

Liu

, and Noble

, “Random waypoint considered harmful,” Proc. of IEEE INFOCOM, April, 2003.

26.

Broch

Maltz

D. A.

Johnson

D. B.

Y.-C.

, and Jetcheva

, “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols,” Proc. of ACM MobiCom, October, 1998.

27.

Das

S. R.

Perkins

C. E.

, and Royer

E. M.

, “Performance comparison of two on-demand routing protocols for ad hoc networks,” Proc. of IEEE INFOCOM, March, 2000.

28.

Heidemann

, and Estrin

, “An Energy-Efficient MAC Protocol for Wireless Sensor Networks,” Proc. of IEEE INFOCOM, June, 2002.

MicroRouting: A Scalable and Robust Communication Paradigm for Sparse Ad Hoc Networks

Abstract

Keywords

I. Introduction

3. Microrouting Networks

A. Microrouter Architecture

Table 1 Comparison of the three network architectures Feature Ad-Hoc Sensor μRouting Size small-medium large large Range medium small small Density medium high high Communication any-to-any many-to-one any-to-any (mobiles) Addressing global ID no global IDs global ID Aggregation No Yes No

4. Microrouting Protocol Design

A. Node Addressing

B. Transmission Range

C. Route Discovery

1) Source local repair

2) Destination local repair

E. Pre-emptive Route Discovery

F. Handling Microrouter Failures

G. Memory Requirement

5. ANALYSIS

a) Route Discovery

b) Source Side Repair

c) Destination Side Repair

d) Microrouter Failure Repair

e) Comparison

6. Performance Evaluation

A. Simulation Methodology

1) Microrouter Model and Deployment

2) Traffic and Mobility Models

3) Energy Model

4) Metrics

B. Effect of Local Repair Ranges

Table 2 Effect of destination repair parameter K · L=3 K 0 1 2 3 Overhead 391,890 408,979 128,450 158,446 Dest. repair 0 1800 20,327 49,421 PDR 97.7 97.7 99.9 99.9 Delay 0.16 0.17 0.15 0.18 Drops (Mn → D) 371 372 3 4

7. Conclusions and Future Work

References

Table 1
Comparison of the three network architectures

Feature Ad-Hoc Sensor μRouting

Size small-medium large large

Range medium small small

Density medium high high

Communication any-to-any many-to-one any-to-any (mobiles)

Addressing global ID no global IDs global ID

Aggregation No Yes No

Table 2
Effect of destination repair parameter K · L=3

K 0 1 2 3

Overhead 391,890 408,979 128,450 158,446

Dest. repair 0 1800 20,327 49,421

PDR 97.7 97.7 99.9 99.9

Delay 0.16 0.17 0.15 0.18

Drops (M_n → D) 371 372 3 4