In mobile ad hoc and sensor networks, greedy-face-greedy (GFG) geographic routing protocols have been a topic of active research in recent years. Greedy routing is applied first and may fail at concave nodes, in which case, face routing is applied to recover from the greedy fail. This may cause extra hops in routing and decrease the routing efficiency in networks containing voids. In this paper, we propose a Hill-Area-Restricted (HAR) routing protocol. It avoids the extra hops as in the original GFG routing, which makes it more efficient in hop count. Compared with the previous work of Node Elevation Ad hoc Routing (NEAR), the proposed HAR guarantees the packet delivery and decreases the communication cost largely. Our simulation results show that the communication cost in bytes of all messages sent by each node in the proposed HAR is 99.2% less than that in NEAR. This makes the HAR more desirable for mobile ad hoc and sensor networks.

In mobile ad hoc and sensor networks, since all nodes are mobile and there is no fixed infrastructure, the design of routing protocols becomes one of the most challenging issues. In recent years, geographic routing protocols have been widely used. Most of them, e.g., greedy-face-greedy routing protocols, need nodes to construct planar graphs as the underlying graphs. In this paper, we propose an edge constrained localized Delaunay graph, denoted by ECLDel, as the underlying graph for geographic routing. We prove that the ECLDel is a planar t-spanner of the unit-disk graph. Geographic routing on ECLDel is as efficient as on the previous work of PLDel in terms of path length (hop count). However, the construction of ECLDel graph is far more simple and it converges faster. This is due to the following two reasons: First, we significantly reduce the number of messages broadcast by each node from five rounds (each round may contain several messages) to only two messages; second, we define two new types of edges, the intersecting Gabriel (IG) edges and the unaware intersection (UI) edges, which are constrained in the ECLDel graph. These edges help significantly reduce the size of messages broadcast by each node. The decrease of both the number and the size of messages broadcast by each node reduces the communication cost, and saves the network bandwidth and node power, which are desirable for mobile ad hoc and sensor networks. Our simulation results show that the average number of messages and the average size of messages broadcast by each node are, respectively, 65 and 42 percent less in the construction of ECLDel than that in PLDel.

In this paper, we present an asynchronous consistent global checkpoint collection algorithm which prevents contention for network storage at the file server and hence reduces the checkpointing overhead. The algorithm has two phases: In the first phase, a process initiates consistent global checkpoint collection by saving its state tentatively and asynchronously (called tentative checkpoint) in local memory or remote stable storage if there is no contention for stable storage while saving the state; in the second phase, the message log associated with the tentative checkpoint is stored in stable storage (checkpoint finalization phase). The tentative checkpoint together with the associated message log stored in the stable storage becomes part of a consistent global checkpoint. Under our algorithm, two or more processes can concurrently initiate consistent global checkpoint collection. Every tentative checkpoint will be finalized successfully unless a failure occurs. The finalized checkpoints of each process is assigned a unique sequence number in ascending order. Finalized checkpoints with same sequence number form a consistent global checkpoint.

In this paper, we propose an edge constrained localized Delaunay graph, ECLDel, as the underlying graph for geographic routing in mobile ad hoc networks. We prove that the ECLDel is a planar t-spanner of the original unit-disk graph. We give an algorithm to construct the ECLDel, which can be run by each node distributively with 1-hop neighborhood information. We define two new kinds of edges, the intersecting Gabriel (IG) edges and the unaware intersection (UI) edges, which are constrained in the ECLDel. This makes the construction of ECLDel more efficient and converges faster with less communication cost, compared to the previous work of constructing a planarized localized Delaunay graph, PLDel. The simulation results show that the average number of messages and the average size of messages (the number of neighbor nodes in the messages) broadcast by each node in construction of ECLDel is 65% and 42% less than that in construction of PLDel, respectively.

In cellular networks, it is vital to allocate communication channels efficiently because the bandwidth allocated for cellular communication is limited. If channels are statically allocated, as is the case in current cellular networks, a cell may run out of channels when a large number of mobile hosts move to the cell. To overcome this problem, dynamic channel allocation approaches have been proposed. Under dynamic channel allocation, channels are allocated to cells on demand, thus increasing channel utilization. Such channel allocation approaches fall under two categories, namely, centralized and distributed. Centralized approaches are neither scalable nor reliable, while distributed approaches have the potential to be both reliable and scalable. In the distributed approaches, a mobile service station is responsible for allocating channels to mobile hosts in the same cell. In cellular networks, mobile service stations may fail. In addition, the network may encounter intermittent network congestion and/or link failures. It is desirable for a channel allocation algorithm to work well, even in the presence of network congestion, link failures, and/or mobile service station failures. In this paper, we present a distributed dynamic channel allocation scheme for cellular networks that is fault-tolerant. Our approach can tolerate the failure of mobile service stations, link failure, and network congestion, and make efficient reuse of channels. We also provide results of the performance evaluation of our algorithm.

Sensor networks are emerging as a new tool for habitat monitoring in nature reserves, monitoring and gathering events in hazardous environments, surveillance of buildings, and surveillance of enemy activities in a battlefield environment. Nodes in a sensor network are severely constrained by energy, storage capacity and computing power. To prolong the lifetime of the sensor nodes, designing efficient routing protocols is critical. Even though sensor networks are primarily designed for monitoring and reporting events, since they are application dependent, a single routing protocol cannot be efficient for sensor networks across all applications. We first analyze the requirements and similarities of MANETs (mobile ad hoc networks) and sensor networks. Then, we describe the existing routing protocols for sensor networks and present a critical analysis of these protocols. Finally, we compare and contrast these protocols. This comparison reveals the important features that need to be taken into consideration while designing and evaluating new routing protocols for sensor networks.