Implementation With Mobile Ad-Hoc Network Routing Protocols

The term ubiquitous computing was coined by Mark Weiser to describe a state of computing in which users are no longer aware of computation being done [28]. The emergence of smart environments, where devices are embedded pervasively in the physical world, has sparked many new research areas and represents a step towards ubiquitous computing. To this end, researchers have begun to outline plans to achieve ubiquitous computing. For example, Basu et al. [3] advocate the vision of power-up-n-play for smart environments in which no predefined infrastructures are installed and, when powered up, the devices "intelligently" configure and connect themselves to other devices. Bhagwat et al. [4] also focus on the interoperability of sensor devices and present three research issues: (1) distributed algorithms for self-organizing devices, (2) packet forwarding, and (3) Internet connectivity. Mobile ad-hoc network (MANET) routing protocols play a fundamental role in a possible future of ubiquitous devices. Current MANET commercial applications have mainly been for military applications or emergency situations[25]. However, we believe that research into MANET routing protocols will lay the groundwork for future wireless sensor networks and wireless plug-n- play devices. The challenge is for MANET routingprotocols to provide a communication platform that issolid, adaptive and dynamic in the face of widelyuctuating wireless channel characteristics and nodemobility. The paper discusses our experience whileimplementing and deploying two distance vectorMANET routing protocols. We examined both a publicdomain implementation of the Ad Hoc On-DemandDistance Vector (AODV) [21] routing protocol andimplemented our own version of the Destination-Sequenced Distance Vector (DSDV) [20] routingprotocol. The choice of routing protocols was pragmaticallybased on what (little) was available at the time thiswork was carried out. The AODV implementation wasthe freely available MAD-HOC implementation [15].This implementation was based on an earlier draft ofthe AODV protocol and includes some MAD-HOCspecific extensions. Where AODV is referred to in thispaper we mean the MAD-HOC implementation unlessotherwise stated. At the time our work was carried outthis was the only public domain MANET routingprotocol implementation that had a license suitable forour use and that we could get to compile, run and work on our network. Faced with no other available public

Available online at www.ignited.in Page 2

domain code and reluctant to base our work solely on one protocol implementation we coded an alternative. DSDV was chosen due to it's relative simplicity and the fact that it is a table based protocol rather than an "on demand" protocol like AODV. Our implementation was based largely on the paper by Perkins et al. [20]. Both protocols were deployed on a five hop, four node test bed based on Linux workstations and 802.11b wireless LAN cards configured to use the Lucent ad hoc mode. We found that neither protocol could provide stable multihop network routes. The main cause was the failure of the route discovery processes in provisioning for unreliable links which are inherent in wireless channels. The route discovery process was fooled by transient link availability with nodes that were too distant for reliable communication to take place. A couple of routing packets sent over this link is enough to temporarily fool the routing protocol into assuming a more direct (lower hop count) route exists to the desired destination. To test the assertion that transient link availability was the cause of the failure of the routing protocols we developed a signal quality based neighbor selection program called powerwave. The inclusion of powerwave for neighbor selection stabilized multi-hop routes for both routing protocols to the point where they could carry useful amounts of user data. A number of extensive simulation studies on various MANET routing protocols have been performed by various researchers [25][5][16][8][7]. However, there is a severe lacking in implementation and operational experiences with existing MANET routing protocols. Previous implementation experiences include wireless Internet gateways (WINGS) [11], implementation of ODMRP [2], AODV implementation by Royer et al. [24] and ABR implementation by To hetal. [27]. These studies only highlighted performance issues specific to the protocol being used. By far the most extensive implementation study to date was conducted by Maltz et al. [17] in describing their implementation of DSR. Unlike previous work, our work reports on the experience of building an operational ad-hoc network that is capable of carrying useful data. We report several interesting observations not reported elsewhere for the use of MANET protocols within pico-cell environments. It is worthwhile noting that this paper's objective is to report on the operational feasibility of existing routing protocols and efforts undertaken to create a reliable ad-hoc network. In many ways this is a step back towards fundamental issues and away from the MANET routing protocol aspects usually examined in simulation studies. Whereas simulation studies commonly report onperformance metrics such as throughput, latency andpacket loss this paper reports on the fundamentalissue of \do MANET routing protocols work". Theanswer is yes but, in the case of the two distancevector protocols we examined, only if the inherentunreliable and transient nature of wireless networklinks are taken into account. This paper is organized as follows. In Section 2 weprovide a brief summary of AODV and DSDV. This isfollowed by implementation details of both theseprotocols in Section 3. In Section 4 we describe thetestbed used for our experiments. Section 5 presentsthe problems and observations gained from setting upthe testbed and running the routing protocols over it. InSection 6, we present the workings of powerwave.Based on our experience with MANET routingprotocols, we discuss issues and problemsencountered in relation to existing routing protocolsand propose some future directions in Section 7.Finally, the conclusions are presented in Section 8.

In this section we review the workings of the AODVand DSDV MANET routing protocols. Comprehensivereviews of other routing protocols are available in[25],[12] and [5]. AODV is characterised as an on-demand (also called reactive) routing protocol. Routesare created as needed at connection establishmentand are maintained for the duration of thecommunication session. During route discovery a nodebroadcasts a route request (RREQ) message for agiven destination address. Nodes that have a route tothe destination respond to the RREQ by sending aroute reply (RREP) message to the source and recordthe route back to the source. Nodes that do not have aroute to the destination rebroadcast the RREQmessage after recording the return path to the source.In the event of link breakage a route error (RERR)message is sent to the list of nodes (referred to asprecursors) that rely on the broken link. Upon receipt ofa RERR message, the corresponding route isinvalidated and a new RREQ may be initiated by thesource to reconstruct the route [21]. The time-to-live(TTL) held is used in RREQs for an expanding ringsearch to control ooding. Successive RREQs uselarger TTLs to increase the search for destinationnode. Unlike AODV, DSDV [20] is a table-driven (orproactive) routing protocol and is essentially based onthe basic distributed Bellman-Ford routing algorithm[1]. Each node in the network maintains a routing tableconsisting of the next hop address, routing metric and

Available online at www.ignited.in Page 3

sequence number for each destination address. To guarantee loop free operation, routing updates from a given node are tagged with a monotonically increasing sequence number to distinguish between stale and new route update messages. Nodes periodically broadcast their routing tables to neighbouring nodes. Given sufficient time, all nodes will converge on common routing tables that list reachability information to each destination in the network. Route updates are generated and broadcast throughout the network when nodes discover broken network links. Nodes that receive a route update check to see if the sequence number specified in the route update message is higher than the sequence number recorded in their own routing table before accepting the update. DSDV reduces routing messages overheads by supporting both full and incremental updates of routing tables. The main characteristic of table-driven protocols is that a route to every node in the network is always available regardless of whether or not it is needed. This results in substantial signaling overhead and power consumption [25]. Furthermore, table driven protocols transmit route updates regardless of network load, size of routing table, bandwidth and number of nodes in the network [5]. Interested readers are referred to Toh et al. [25] for a qualitative comparison based on simulation experiments between avors of both ondemand and table-driven routing protocols.

It was found that transient radio links resulted in poor operation of both the routing protocols examined where no reliable routes could be established. The poor operation was due to the creation and maintenance of routes without taking the stability, or quality, of the network links comprising the route into account. The fundamental problem was that successful transmission of a datagram over a wireless network link is probabilistic, regardless of lower level protocols. In practice this probabilistic effect became evident in two ways; occasional dropped packets on a normally \good quality" network link and occasional successful packet transmissions on a normally \poor quality" network link. We found that the occasional dropped packet did not present much of a problem for either of the routing protocols examined. On a \good" network link the link layer acknowledgements in 802.11 replaced lost unicast packets and the routing protocols appeared to be able to handle the occasional lost broadcast, or multicast, packet. In contrast the occasional appearance of a channel between two nodes that could not normally communicate was disruptive to the routing protocols on our testbed. The problem manifested itselfin the creation of network routes that were not suitable for the reliable transmission (and reception) of userdata. These routes were chosen over other routeoptions by the protocols selecting for lowest hoproutes, regardless of any sort of measure of routequality. As stated in the introduction a similar effect forthe DSR routing protocol has been observed onanother testbed [18]. We found that it was practically impossible to establisha stable telnet session between nodes over a three orfour hop route on our testbed. For example when usingthe topology described in Figure 4, we found thatNode1 could still detect Node3's signal occasionallydespite careful placement and orientation. As a resultwe observed that both nodes would randomly receive apacket from the other. If AODV was engaged in a routebuilding process it would use the unreliable one hoproute from Node1 to Node3 in preference to the twohop alternative. DSDV would replace the existing twohop route between the nodes with the unreliable onehop route. Very little user data would be transmittedover this unreliable route and user sessions wouldhang pending the reestablishment of the more reliabletwo hop route. In a related work, Maltz et al. [17] reported similarbehavior while building a MANET testbed andexperimenting with Dynamic Source Routing (DSR)routing protocol. The following modifications to DSRwere suggested to overcome the problem of routingover unreliable links: (1) monitor route error on links,(2) use the geographic positioning system (GPS) todetermine the neighbor proximity (assuming physicalproximity will provide the best channel) and (3)combine GPS with route error monitoring. Reliabilitywas tested over a three node, two hop network with thenodes arranged in a line. The network included packetfiltering software to prevent packets from beingtransmitted directly from one end node to the other.They found that an FTP _le transfer between the endnodes was more reliable when the packet filteringsoftware was enabled. Ramanathan et al. [22] alsoreported problems with transmission range whentesting out their quality of service (QoS) based routingprotocols. However, no solutions to unreliable links weresuggested. Published articles reporting on MANETrouting protocol performance often rely on simulationexperiments. Experiments run on our testbeduncovered considerable difference in the probability ofsuccessfully receiving packets on a MANET nodeversus the probability of successful packet reception insome simulation environments. In a simulation

Available online at www.ignited.in Page 4

environment, such as ns-2 [10], it is generally assumed that the probability of receiving a packet is effectively one (pending collisions etc) and once a node moves out of another node's signal range, or a given distance, this drops to zero. However, our experiments have shown that this is unrealistic; signals tend to decay slowly and there is no cutoff point. We suspect that the use of simplistic radio propagation models in MANET simulation environments has led to inaccurate assessments of the performance of various routing protocols, especially those which utilize hop count as the dominant route selection metric. Thus, one area for future work is the incorporation of better radio propagation models that support channel fading and other inputs to the probabilistic nature of wireless channels. For example, Rappaport [23] lists a number of factors that affect fading in an in-door environment such as multi-path propagation, mobile node speed, surround object speed and signal bandwidth.

In conventional cellular networks, the signal-to-noise ratio (SNR) of the connection between mobile phone and base stations is monitored to determine when to hand o_ from one base station to another. In a MANET, current protocols do not predict when a link's SNR will fall below a threshold. The periodic HELLO messages in AODV and route update timers in DSDV are not used to anticipate hand o_, they indicate presence or absence of a neighbor node. Consequently, the route maintenance process at both AODV and DSDV is only initiated after link breakage already ocurred. DSDV behaves differently depending on the mobile nodes direction of movement. DSDV pro-actively changed to a lower hop count route if one was available, but hung on to a route until it is explicitly broken should a lower hop count route not be available. The effect with DSDV was smooth handover when MH2 (in Figure 4) was moving downstream but no handover in the upstream direction. In the upstream direction two things would prompt a new (higher hop count) route to be used. First, the connection to the previous fixed node would have to timeout prompting a switch to the next best available route being advertised by the new neighbor. Or second, the link between the previous fixed node would have to break along with a route advertisement being received from the new neighbor with a higher hop count and a higher sequence number. The new sequence number would then invalidate the old route and cause the new route to be used instead.

A problem encountered were AODV's defaultparameters. Since the transmission range of each nodewas reduced in our testbed to less than 5m, we had ineffect constructed a network with pico sized cells. Inthis environment the default MAD HOC AODV timersunnecessarily prolonged route construction andrequired tunning before an acceptable performancecould be achieved. The parameters we changed arelisted on Table 1. AODV's parameters as specified in[21] are left to the implementors, however recent draftshave used more conservative parameters than those inthe MAD-HOC implementation shown in Table 1. BCAST ID SAVE is used to prevent over ooding ofRREQ messages. When a new RREQ is intercepted,the information within the RREQ is recorded and theinformation is added to an interval queue along with atime interval (current time plus BCAST ID SAVE). Inthe event of another RREQ appearing within this timeinterval, the RREQ is discarded. RREQ RETRIESbounds the number of RREQs for a given destination.The default value is two. We found this value to be tooconservative, and found that five was more appropriatevalue. ACTIVE ROUTE TIMEOUT is used to determine thelifetime of a given route. The lifetime of each routemaintained by a given node is refreshed afterobserving data packets or HELLO messages on thatroute. In a pico-cell environment, the default valueneeds to be small. In our testbed where nodes movedat slow walking pace, the time for a node to traversegiven cell was around five and we found a routetimeout value of one second was appropriate. Both NODE TRAVERSAL TIME and NET DIAMETERhad to be modified to suit our network topology. TheNODE TRAVERSAL TIME was modified to increasethe route construction time. The default value of NETDIAMETER was set to 35 nodes and this was changedto five to reect the number of nodes in our test bed. The last parameter to be modified was ALLOWEDHELLO LOSS which determines how many HELLOmessages are lost before a link is considered broken.Routes were timing out frequently in our testbed andwe set the ALLOWED HELLO LOSS parameter to fiveto increase stability. The optimization of AODV bychanging the parameters to suit our testbed was doneon a trial and error basis. To date there are nopublished guidelines or heuristics for setting AODV'sparameters or adapting them to a given network.

Available online at www.ignited.in Page 5

The parameters shown in Table 1, and the other AODV parameters that have been defined in the AODV specification [21], would most likely have to be modified for use in other networks.

The reliance of the MAD-HOC AODV implementation on sniffing ARP packets to signal the need for route construction led to two problems. The first problem was that packets were not buffered while the route was being built. As mentioned in Section 3 this led to packets being dropped and the need to start an application such as telnet a number of times before a route was actually built. The second problem was that a route will never be constructed if there is an entry in the ARP cache. Spurious ARP cache entries exist for one or more reasons. Either the two nodes in question had once been adjacent, and the ARP cache entry had yet to time out, or an ARP reply was un-expectedly received from a remote node (over an unreliable link) and the cache then prevented a more reliable route being found. One work around to these problems was to regularly push the ARP cache and to start applications multiple times while waiting for the route building process to complete. In practice this would be achievable by using ping and waiting for a successful reply before starting the intended application. A better solution is the one proposed in [24] that uses a netlink socket to communicate routing information with the kernel space and a dummy route for buffering data packets pending route construction.

The first thing we noticed about our DSDV implementation was its relative stability compared to the MAD-HOC's AODV implementation. DSDV was less affected by unreliable connections to distant nodes. This was mainly due to the use of the SEEN metric (requiring a handshake before the link would be used in routes) and less interaction with the ARP cache as the routing table was pre-populated with host routes (negating the need to ARP). However DSDV was adversely affected by transient link availability. Even when all the network nodes were stationary the routing table would slowly "churn" as routes were constructed to distant nodes and then timeout.

The majority of MANET routing protocols described inthe literature were designed to handle topologychanges and do not take unreliable links into account.Currently, only signal stability based adaptive routing(SSA) [9], ABR [26], and longest life routing protocol(LLRP)[29] support the notion of reliable routes. Theroute metrics use by SSA are average signal strengthand route stability. By using these route metrics,packets will always be routed through the most reliableroute (possibly closest node). Thereby routereconstruction cost is reduced and reliability ofestablished route increases [9]. Unlike SSA, ABR only use route stability as the routingmetric. Route stability is defined as the number ofHELLO messages observe from a given neighbor.Hence, a neighbor with a given HELLO message countis considered stable. In both SSA and ABR, thedestination has to choose the best route to take from anumber of alternatives recorded from the various routerequests received [29]. Further, once a route is setupthere are no considerations for degraded links alongthe route. Routes are only rebuilt once they are broken.The immediate future work is to re-evaluate existinghop based routing protocols with the addition ofunreliable links.

The notion of smooth handoff in MANET routingprotocols has generally been overlooked.Improvements may be made by intelligently monitoringsurrounding neighbors and determining whether agiven node is able to prime an upstream/downstreamnode with a route to the destination. We found that arelatively smooth handover could be achieved bygenerating regular RREQs from MH2. In other words,when a node detects a new neighbor a specialmessage could be sent to prime the new neighbor, withroutes to other new receiver nodes without waiting forexisting routes to break. Pro-active route constructionwill cause unnecessary traffic and duplicate routeswhich may then lead to the difficulty of removinginvalidated routes. Further, the problem becomes morecomplicated if mobility is taken into account. Unliketraditional one hop wireless networks (e.g., cellular)where base-stations are fixed, the handoff decisions inMANETs are much more complicated. It is interesting to note that the powerwave neighborselection process had the side-effect of enabling adegree of handoff. The neighbor selection processfiltered out neighbors before the network linkdisappeared entirely. User datagrams could still be

Available online at www.ignited.in Page 6

forwarded over the link while the routing policy engine was finding a new route. It worked in our implementations because the routing parameters and the rate at which MH2 moved matched.

Our experiments showed that the protocol parameters in both MAD-HOC's AODV and DSDV required some tuning before they would work properly. The determination of suitable timer values depended on channel rates, network topologies and mobility patterns [8]. The impact of these parameters on the performance of upper layer protocols is left for future work. One method to allow for adaptive parameters is to introduce additional information. Protocols may rely on GPS, for example location aided routing protocols, to gather more information such as network topology and nodes proximity. Once the range of adjacent nodes are estimated, parameters may be adjusted accordingly.

The Internet MANET encapsulation protocol (IMEP) [6] is a mechanism to aggregate and encapsulate control messages. Also, IMEP provides a generic multi-purpose layer containing various common functionalities for MANET routing protocols. However, in the IMEP specification no consideration for signal strength was presented. It may be possible to use IMEP for filtering neighbors based on link stability rather than just to list neighbors that are in range. Given the observations obtained from our experiments, one possible area of work is to extend upon IMEP's functionalities to incorporate mechanisms to shield wireless defects, and also over various routing metrics which could be used by routing protocols.

In this paper we have outlined our implementation and deployment experiences with MAD-HOC's AODV and DSDV. Our experiments have provided insights into the real world deployment of MANETs and highlight issues that require further investigation. These are: 1. Handling unreliable/Unstable links. 2. Minimizing the dependacy on topology specific parameters. 3. Mechanisms for handoff and reducing packet loss during handoff. 4. Incorporating neighbor discovery and filteringinto a neighbor selection sub-layer. The first issue is a result of the current prevailingMANET protocol development/testing environmentswhich appear to consist almost entirely of simulationexperiments using ns- 2 and Glomosim. Inimplementing two MANET routing protocols, ratherthan simulating them, we discovered that the variabilityof networking conditions in the radio environment wassuch that the routing protocols did not work as reportedin the literature. This led to the development ofpowerwave, and it was found that neighbor selection iscrucial in the operation of MANET routing protocols.We believe our observations pertaining tounreliable/unstable links are not restricted to MAD-HOC's AODV implementation given that current AODVspeci_cation relies on hop count and does not take intoaccount the reliability of a given route or link. The second issue is specific to a given routingprotocol. As argued, having pre-configured parametersfor a given topology is inappropriate given the inherentdynamic nature of MANETs, and affects the operationof routing protocols. Therefore, methods for adaptiveadjustment of these parameters are required. On the third issue, current MANET routing protocols do not appear to consider pre-emptive route constructionbased on signal strength in a similar way to howhandoffs are done in cellular networks. We haveobserved that knowing whether a node is goingupstream or downstream has added benefit. Theconcept of handoff, from one route that has a highprobability of near term breakage to another routewhich is more stable is a possible area for futureresearch. Finally, there is scope for the development of aneighbor selection sub-layer like IMEP thatincorporates a range of metrics that could be used byrouting protocols. Various filters and heuristics couldbe developed which will be beneficial to MANETrouting protocols.

[1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin.Network Flows, theory, Algorithms, andApplications. Prentice-Hall, 1993. [2] S. H. Bae, S.-J. Lee, and M. Gerla. Unicastperformance analysis of the ODMRP in amobile ad-hoc network testbed. In Proceedingsof IEEE ICCCN'2000, Las Vegas, USA, 2000.

Available online at www.ignited.in Page 7

[3] P. Basu and T. D. C. Little. Task-based self-organisation in large smart spaces:issues and challenges. In DARPA/NIST/NSF Workshop on Research: Issues in Smart Computing Environment, Atlanta, USA, 1999. [4] P. Bhagvat, C. Bisdjikian, P. Kermani, and M. Naghshineh. Smart connectivity for smart spaces. In DARPA/NIST/NSF Workshop on Research: Issues in Smart Computing Environment, Atlanta, USA, 1999. [5] J. Broch, D. A. Maltz, D. B. Johnson, Y.-C. Hu, and J. Jetcheva. A performance comparison of multi-hop wireless ad-hoc network routing protocols. In Proceedings of the 4th ACM/IEEE Internation Conference on Mobile Computing and Networking (MOBICOM'98), Dallas, Texas, Oct. 1998. [6] M. S. Corson and V. Park. An internet MANET encapsulation protocol (IMEP) specification. Internet Draft: draft-ietf-manet-imep-spec-00.txt, Nov. 1997. [7] S. R. Das, R. Castaneda, and J. Yan. Simulation based performance evaluation of mobile, ad hoc network routing protocols. In Proceedings of Seventh International Conference on Computer Communications and Networks (ICCCN'98), 1998. [8] S. R. Das, C. Perkins, and E. M. Royer. Performance comparison of two on-demand routing protocols for ad-hoc networks. In Proceedings of IEEE INFOCOM'200, Tel-Aviv, Israel, 2000. [9] R. Dube, C. D. Rais, K.-Y. Wang, and S. K. Tripathi. Signal stability based adaptive routing (SSA) for ad-hoc mobile networks. IEEE Personal Communications, 4(2):36{45, Feb. 1997. [10] K. Fall and K. Varadhan. The VINT project. ns notes and documentation. http://www.isi.edu/nsnam/ns/. [11] J. J. Garcia-Luna-Aceves, D. Beyer, and T. Frivold. Wireless internet gateways (WINGS). In Proceedings IEEE Milcom'97, Monterey, CA, 1997. [12] M. Gerla, G. Pei, and S. J. Lee. Wireless, mobile ad-hoc routing. In IEEE/ACM FOCUS, New Brunswick, USA, May 1999. [13] H. Hashemi. The indoor radio propagationchannel. Proceedings of the IEEE, 81(7), July1993. [14] Lawrence Berkeley National Lab. Libpcap:User-level packet capture library.ftp://ftp.ee.lbl.gov/libpcap-0.4.tar.Z, Feb. 1997. [15] F. Lilieblad, O. Mattsson, P. Nylund, D.Ouchterlony, and A. Roxenhag. MAD-HOCAODV Implementation. TelecommunicationsSystems Lab, Techical Report.http://.ssvl.kth.se/. [16] D. A. Maltz, J. Broch, J. Jetcheva, and D. B.Johnson. The effects of on-demand behavior inrouting protocols for multi-hop wireless ad-hocnetworks. IEEE Journal on Selected Areas inCommunications special issue on mobile andwireless networks, Aug. 1999. [17] D. A. Maltz, J. Broch, and D. B. Johnson.Experiences designing and building a multi-hopwireless ad-hoc network testbed. TechicalReport, CMU-CS-99-11, Mar. 1999. [18] D. A. Maltz, J. Broch, and D. B. Johnson.Lessons from a full-scale multihop wireless adhoc network testbed. IEEE PersonalCommunications, 8(1), Feb. 2001. [19] Merit Network Inc. Multi-threaded routingtoolkit. MRT Programmers Guide.http://www.merit.edu/mrt/mrt doc/. [20] C. Perkins and P. Bhagvat. Highly dynamicdestination-sequenced distance-vector routing(DSDV) for mobile computers. ACM ComputerCommunications Review, pages 234{244, Oct.1994. [21] C. E. Perkins, E. M. Royer, and S. R. Das. Adhoc on-demand distance vector (AODV)routing. draft-ietf-manet-aodv-06.txt, July 2000. [22] R. Ramanathan and R. Hain. An ad hocwireless testbed for scalable, adaptive QoSsupport. In Proceedings of IEEE WCNC'2000,Chicago, IL, USA, 2000. [23] T. S. Rappaport. Wireless Communications:Principles and Practice. Prentice-Hall, 1996. [24] E. M. Royer and C. Perkins. An implementationstudy of the AODV routing protocol. InProceedings of the IEEE WirelessCommunications and Networking Conference,

Available online at www.ignited.in Page 8

Chicago,IL, Sept. 2000. [25] E. M. Royer and C.-K. Toh. A review of current routing protocols for ad-hoc mobile wireless networks. IEEE Personal Communications, 6(2):4 6{55, Apr. 1999. [26] C.-K. Toh. Associativity-based routing for ad-hoc mobile networks. Wirelss Personal Communications Journal, 4(2), Dec. 1997. [27] C.-K. Toh and M. Delawar. Implementation and evaluation of an adaptive routing protocol for infrastructureless mobile networks. In IEEE International Conference on Computer Communications and Networks (ICCCN'2000), Las Vegas, USA, Oct. 2000. [28] M. Weiser. The computer for the 21st century. Scienti_c American, 265(3):94{104, Sept. 1991. [29] S.-C. M. Woo and S. Singh. Longest life routing protocol (LLRP) for ad hoc networks with highly mobile nodes. In Proceedings of IEEE WCNC'2000, Chicago, IL, USA, 2000.