9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # A Mobility Based Framework for Adaptive Clustering in Wireless Ad-Hoc Networks

A Mobility Based Framework for Adaptive Clustering in Wireless Ad-Hoc Networks

A. Bruce McDonald and Taieb Znati

Abstract| This paper presents a novel framework for dynamically orga

nizing mobile nodes in wireless ad-hoc networks into clusters in which the probability of path availability can be bounded. The purpose of the ( ; t)?Cluster is to help minimize the far-reaching e ects of topological changes while balancing the need to support more optimal routing. A mobility model for ad-hoc networks is developed and is used to derive expressions for the probability of path availability as a function of time. It is shown how this model provides the basis for dynamically grouping nodes into clusters using an e cient distributed clustering algorithm. Since the criteria for cluster organization depends directly upon path availability, the structure of the cluster topology is adaptive with respect to node mobility. Consequently, this framework supports an adaptive hybrid routing architecture that can be more responsive and e ective when mobility rates are low and more e cient when mobility rates are high. Keywords| ad-hoc networks, routing algorithms, mobility models, dynamic clustering, hierarchical routing, wireless networks, mobile computing.

ronments, mobile patient monitoring for improved critical care, distributed command and control systems, and mobile access to the global Internet. Furthermore, ad-hoc networks have the potential to serve as a ubiquitous wireless infrastructure capable of interconnecting many thousands of devices 31] with a wide range of capabilities and uses. In order to achieve this status, however, ad-hoc networks must evolve to support large numbers of heterogeneous systems with a wide range of application requirements 21, 5]. Communication between arbitrary end-points in an adhoc network requires routing over multiple-hop wireless paths. The main di culty arises because without a xed infrastructure these paths consist of wireless links whose end-points are likely to be moving independently of one another. Consequently, node mobility causes the frequent failure and activation of links, leading to increased network congestion while the network's routing algorithm reacts to the topology changes. Unlike xed infrastructure networks where link failures are comparatively rare events, the rate of link failure due to node mobility is the primary obstacle to routing in ad-hoc networks. The e ectiveness of adaptive routing algorithms depends upon the the timeliness and detail of the topology information available to them. However, minimizing the exchange of information is crucial for e cient operation. In an ad-hoc network signi cant rates of topological change are expected; consequently, the distribution of up-to-date information can easily saturate the network. Furthermore, information arriving late due to latency can drive network routing into instability. Since the rate of link failure is directly related to node mobility, greater mobility increases both the volume of control tra c required to maintain routes and the congestion due to tra c backlogs. Thus, a crucial algorithm design objective in order to achieve routing responsiveness and e ciency is the minimization of reaction to mobility 27]. Existing schemes for routing in ad-hoc networks can be classi ed according to four broad categories, namely, proactive routing, ooding, reactive routing and dynamic clusterbased routing. Pro-active routing protocols periodically distribute routing information throughout the network in order to pre-compute paths to all possible destinations. Although this approach can ensure higher quality routes in a static topology, it does not scale well to large, highly dynamic networks. By contrast, ooding based routing requires no knowledge of network topology. Packets are broadcast to all destinations with the expectation that they

1 Introduction

Advances in wireless technology and portable computing along with demands for greater user mobility have provided a major impetus toward development of an emerging class of self-organizing, rapidly deployable network architectures referred to as ad-hoc networks 2, 12]. An adhoc network is comprised of wireless nodes and requires no xed infrastructure. Any device with a microprocessor, whether highly mobile or stationary, is a potential node in an ad-hoc network. This includes mobile telephones, motor vehicles, roadside information stations, satellites, and desktop or hand-held computing devices. Unlike existing commercial wireless systems and xed infrastructure networks, ad-hoc networks cannot rely on specialized routers for path discovery and tra c routing. Consequently, mobile end-systems in an ad-hoc network are expected to act cooperatively to route tra c and adapt the network to the highly dynamic state of its links and its mobility patterns. Ad-hoc networks evolved largely from the DARPA packetradio network (PR) program 20, 16, 1]. They are expected to play an important role in future commercial and military settings where mobile access to a wired network is either ine ective or impossible. Potential applications for this class of network include instant network infrastructure to support collaborative computing in temporary or mobile enviA. B. McDonald is with the Dept. of Information Science and Telecommunications, University of Pittsburgh and the Dept. of Neurophysiology, Children's Hospital of Pittsburgh. T. Znati is with the Dept. of Computer Science with joint appointments in Telecommunications and Computer Engineering, University of Pittsburgh.

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999 will eventually reach their intended target. Under light tra c conditions ooding can be reasonably robust. However, it generates an excessive amount of tra c in large networks, and it is di cult to achieve ooding reliably 30] when the topology is highly dynamic. Consequently, it does not seem that a routing strategy based exclusively on pro-active routing or ooding can achieve the objectives required for ad-hoc routing. In a reactive routing strategy, the design objective is accomplished by maintaining paths on a demand-basis using a query-response mechanism. This limits the total number of destinations to which routing information must be maintained, and, consequently, the volume of control tra c required to achieve routing. The shortcomings of this approach include the possibility of signi cant delay at route setup time, the large volume of far reaching control tra c required to support the route query mechanism, and lower path quality relative to pro-active routing. Furthermore, despite the objective of maintaining only desired routes, the route query could propagate to every node in a network during the initial path setup causing each node to establish paths even when they are only required by certain sources. In dynamic cluster-based routing, the network is dynamically organized into partitions called clusters with the objective of maintaining a relatively stable e ective topology 21]. The membership in each cluster changes over time in response to node mobility and is determined by the criteria speci ed in the clustering algorithm. In order to limit far reaching reactions to topology dynamics, complete routing information is maintained only for intra-cluster routing. Inter-cluster routing is achieved by hiding the topology details within a cluster from external nodes and using hierarchical aggregation, reactive routing, or a combination of both techniques. The argument made against dynamic clustering is that the re-arrangement of the clusters and the assignment of nodes to clusters may require excessive processing and communications overhead, which outweigh its potential bene ts. If the clustering algorithm is complex or can not quantify a measure of cluster stability, these obstacles may be di cult to overcome. A desirable design objective for an architectural framework capable of supporting routing in large ad-hoc networks subject to high rates of node mobility incorporates the advantages of cluster-based routing and balances the tradeo between reactive and pro-active routing while minimizing the shortcomings of each. Furthermore, the consequences of node mobility suggest the need to include a quantitative measure of mobility directly in the network organization or path selection process. Speci cally, a strategy capable of evaluating the probability of path availability over time and of basing clustering or routing decisions on this metric can help minimize the reaction to topological changes. Such a strategy can limit the propagation of far reaching control information while supporting higher quality routing in highly mobile environments. The purpose of this paper is to present the ( ; t)?Cluster framework, which de nes a strategy for dynamically organizing the topology of an ad-hoc network in order to adap-

2

tively balance the tradeo between pro-active and demandbased routing by clustering nodes according to node mobility. This is achieved by specifying a distributed asynchronous clustering algorithm that maintains clusters which satisfy the ( ; t)-criteria that there is a probabilistic bound, , on the mutual availability of paths between all nodes in the cluster over a speci ed interval of time, t. In order to evaluate the ( ; t)-criteria, a mobility model is proposed which characterizes the movement of nodes in large ad-hoc networks. It is shown how this model is used to determine the probability of path availability when links are subject to failure due to node mobility. Based on the ( ; t)?Cluster framework, intra-cluster routing requires a pro-active strategy, whereas inter-cluster routing is demand-based. Consequently, the framework speci es an adaptive-hybrid scheme whose balance is dynamically determined by node mobility. In networks with low rates of mobility, ( ; t)?Clustering provides an infrastructure which is more pro-active. This enables more optimal routing by increasing the distribution of topology information when the rate of change is low. When mobility rates become very high, cluster size will be diminished and reactive routing will dominate. The ( ; t)?Cluster framework decouples the routing algorithm speci cation from the clustering algorithm, and, thus, it is exible enough to support evolving ad-hoc network routing strategies 13, 27, 29, 15] in both the intra and inter-cluster domains. The remainder of the paper is organized as follows: Section 2 presents a review of the signi cant contributions in the area of dynamic clustering for ad-hoc networks. The characterization of the ( ; t)?Cluster and the cluster routing methodology is described in Section 3. Details of the the ( ; t)?Cluster algorithm are presented in Section 4. The mobility model used to characterize link and path availability is developed in Section 5, and simulation results demonstrating the e ectiveness of the ( ; t)?Cluster framework are presented in Section 6. Finally, conclusions of this work are presented in Section 7.

2 Related Work

Several dynamic clustering strategies have been proposed in the literature 31, 25, 21, 10]. While these strategies differ in the criteria used to organize the clusters and in the implementation of the distributed clustering algorithms, none of the proposed schemes uses prediction of node mobility as a criteria for cluster organization. Clustering decisions in each of these schemes are based on static views of the network at the time of each topology change. Consequently, they do not provide for a quantitative measure of cluster stability. In contrast, the ( ; t)?Cluster strategy forms the cluster topology using criteria based directly on node mobility. According to 31], the ability to predict the future state of an ad-hoc network comprised of highly mobile nodes is essential if the network control algorithms are expected to maintain any substantive quality-of-service (QoS) guarantees to real-time connections.

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999 The Multimedia Support for Wireless Network (MMWN) system proposed by Ramanathan and Steenstrup 31] is based upon a hybrid architecture which includes the characteristics of ad-hoc and cellular networks. Their framework uses hierarchical routing over dynamic clusters which are organized according to a set of system parameters that control the size of each cluster and the number of hierarchical levels. Aggregation of routing information is used to achieve scalability and limit the propagation of topological change information. A multilevel strategy is used to repair virtual-circuit (VC) connections which have been disturbed due to node mobility. MMWN does not predict node movement. Consequently, it is unable to provide a quantitative bound on the stability of its cluster organization. Krishna, Vaidya, Chatterjee and Pradhan 25] proposed a scheme which dynamically organizes the topology into k-clusters, where nodes in a cluster are mutually reachable via k-hop paths. The algorithm considers k = 1, and reduces to nding cliques in the physical topology. Using a rst- t heuristic, the algorithm attempts to nd the largest cliques possible. Although the algorithm does not form optimal clusters, it still requires a three-pass operation each time a topology change occurs: one for nding a set of feasible clusters; a second for choosing the largest of the feasible clusters that are essential to maintain cluster connectivity; and a third to eliminate any existing clusters which are made super uous by the new clusters. The objective of the scheme proposed by Lin and Gerla 21] di ers signi cantly from the previous examples. Rather than using clustering to minimize the network's reaction to topological changes, their scheme is intended to provide controlled access to the bandwidth and scheduling of the nodes in each cluster in order to provide QoS support. Hierarchical routing and path maintenance were a secondary concern. The proposed algorithm is very simple and uses node ID numbers to deterministically build clusters of nodes that are reachable by two-hop paths. The Zone Routing Protocol (ZRP) proposed by Haas and Perlman 13] is a hybrid strategy which attempts to balance the tradeo between pro-active and reactive routing. The objective of ZRP is to maintain pro-active routing within a zone and to use a query-response mechanism to achieve inter-zone routing. In ZRP each node maintains its own hop-count constrained routing zone; consequently, zones do not re ect a quantitative measure of stability, and the zone topology overlaps arbitrarily. These characteristics di er from ( ; t)?Clusters, which are determined by node mobility and do not overlap. Both strategies assume a proactive routing protocol for intra-zone/cluster routing, and each organizes its topology based upon information maintained by that protocol. ZRP also de nes the query control scheme to achieve inter-zone routing. Although ZRP is not a clustering algorithm and the ( ; t)?Cluster framework is not a routing protocol, the comparison demonstrates a close relationship which could be leveraged by incorporating the ( ; t)?Cluster into ZRP. The use of ( ; t)?Clusters in ZRP could achieve more e cient and adaptive hybrid routing without signi cantly increasing its complexity.

3

3

(

; t)?Cluster Framework

Hierarchical routing has been shown to be essential in order to achieve at least adequate levels of performance in very large networks 17, 18]. In xed infrastructure networks, hierarchical aggregation achieves the e ect of making a large network appear much smaller from the perspective of the routing algorithm. Cluster-based routing in ad-hoc networks can also make a large network appear smaller, but, more importantly, it can make a highly dynamic topology appear much less dynamic. Unlike the cluster organization of a xed network, the organization of an ad-hoc network cannot be achieved o -line. The assignment of mobile nodes to clusters must be a dynamic process; wherein, the nodes are self-organizing and adaptable with respect to node mobility. Consequently, it is necessary to design an algorithm which dynamically implements the self-organizing procedures in addition to de ning the criteria for building clusters. The objective of the ( ; t)?Cluster framework is to maintain an e ective topology which adapts to node mobility, so that routing can be more responsive and optimal when mobility rates are low and more e cient when they are high. This is accomplished by a simple distributed clustering algorithm using a probability model for path availability as the basis for clustering decisions. The algorithm dynamically organizes the nodes of an ad-hoc network into clusters where probabilistic bounds can be maintained on the availability of paths to cluster destinations over a speci ed interval of time. The ( ; t)?Cluster framework can also be used as the basis for the development of adaptive schemes for probabilistic QoS guarantees in ad-hoc networks. Speci cally, support for QoS in time-varying networks requires addressing (1) connection-level issues related to path establishment and management to ensure the existence of a connection between the source and the destination, and (2) packet-level performance issues in terms of delay bounds, throughput, and acceptable error rates. Ideally, it is desirable to guarantee that the QoS requirements of on-going connections are preserved for their entire duration. Unfortunately, this is not possible in a time-varying network environment as connections may fail randomly due to user mobility. A more realistic and practical approach is to provide some form of probabilistic QoS guarantees by keeping connection failures below a pre-speci ed threshold value, and by ensuring, with high probability, that a minimum level of bandwidth is always available to on-going connections. Based upon the intra-cluster routing model proposed in Subsection 3.2 and using the estimates of path availability and other link status metrics provided through the routing algorithm, a connection admission control algorithm could determine, with high probability, whether or not su cient resources are available to support the requirements of an intra-cluster connection over a speci c period of time. In order to achieve similar QoS guarantees across the intercluster domain, the ( ; t)?Cluster framework could be ex-

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999 tended to support a dynamic hierarchical architecture in which resource information within each cluster is aggregated and a second level of clustering algorithm maintains ( ; t)-paths between clusters using virtual-links 1 . Hierarchical QoS based routing and admissions control schemes are not considered further in this paper. The remainder of this section is organized as follows: The ( ; t)?Cluster is formally characterized in Subsection 3.1. The implementation of routing is discussed in Subsection 3.2. Finally, a methodology for selecting the system parameters, and t, is presented in Subsection 3.3. The basic idea of the ( ; t)?Cluster strategy is to partition the network into clusters of nodes that are mutually reachable along cluster internal paths 2 that are expected to be available for a period of time t with a probability of at least . The union of the clusters in a network must cover all the nodes in the network. k De nition 3.1 Let Pm;n(t) indicate the status of path k k from node n to node m at time t. Pm;n(t) = 1 if all the k links in the path are active at time t, and Pm;n (t) = 0 if one or more links in the path are inactive at time t. The path availability k (t) between two nodes n and m at m;n time t t0 is given by the following probability expression: k (t) Pr(P k (t0 + t) = 1 j P k (t0 ) = 1) m;n m;n m;n De nition 3.2 Let k (t) be the path availability of path m;n k from node n to node m at time t. Path k is de ned as an ( ; t)-path i : k (t) m;n De nition 3.3 Node n and node m are ( ; t)?available if they are mutually reachable over ( ; t)?paths. De nition 3.4 An ( ; t)?cluster is a set of ( ; t)?available nodes. De nition 3.4 states that every node in an ( ; t)?cluster has a path to every other node in the cluster that will be available at time t0 + t with a probability . The cluster characterization, as de ned above, requires a model which quanti es the ( ; t)-path availability as given in De nition 3.1. Path availability is a random process, which depends upon the mobility of the nodes which lie along a given path. Consequently, the mobility characteristics of the nodes play an important role in the characterization of this process. In Section 5, a mobility model for large ad-hoc networks is proposed, and the probability distributions for the aggregate distance and trajectory covered by a node over time are derived. These distributions provide the basis for developing analytical models for link availability. It is also shown how this model can be used to derive expressions for path availability which can be e ciently evaluated by the ( ; t)?Cluster algorithm.

1 A virtual-link represents the set of physical-links which connect nodes in one cluster to nodes in another cluster. 2 A cluster internal path consists exclusively of nodes which are members of the cluster.

4

Routing Protocol Routing Table

PSfrag replacements

( ; t)?Cluster Algorithm Protocol

Network-Layer Network-Interface Layer Logical Entities

MANET Encapsulation Protocol

3.1 ( ; t)?Cluster Characterization

Internet Protocol

Figure 1: Logical Relationships Among MANET NetworkLayer Entities.

3.2 ( ; t)?Cluster Routing Methodology

The logical relationship between the ( ; t)?Cluster algorithm, the routing algorithm, and the other network-layer entities is depicted in Figure-1. The cluster algorithm resides logically between the routing-layer and the Internet MANET 3 Encapsulation Protocol (IMEP) 4 6]. As such, the cluster algorithm presents a logical topology to the routing algorithm, and it accepts feedback from the routing algorithm in order to adjust that logical topology and make clustering decisions. To support the ( ; t)?Cluster framework, IMEP or an equivalent protocol must identify a node's cluster identi er number (CID) to neighboring nodes, and include the CID in the encapsulation of the routing information packets. A protocol which provides the functionality of IMEP along with these enhancements will be referred to in this paper as a network-interface layer protocol. A two-level routing algorithm adaptively subdivides the task of establishing and maintaining routes to mobile destinations. Intra-cluster routing uses a pro-active strategy, whereby each node in a cluster maintains topology information and routes to every cluster destination for the duration of the time that the node remains in a given cluster. Routes to destinations outside of a node's cluster are established on a demand basis only. Consequently, a reactive routing strategy must be implemented to setup inter-cluster routes.

Intra-cluster Routing: Intra-cluster routing can be implemented with any distributed routing algorithm which can pro-actively maintain routes to a set of mobile destinations. Similar to ZRP, which uses hop-count 11], the ( ; t)?Cluster uses a path availability based membership

entities such as link status sensing, neighbor discovery, one-hop neighbor broadcast, control packet aggregation, and address resolution.

3 A MANET is a mobile ad-hoc network. 4 The IMEP layer is designed to provide services to upper-layer network

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999 to limit the propagation of routing updates. Those MANET protocols which have been designed speci cally to operate as reactive protocols can still function as intra-cluster protocols in which the demand for a route is produced by the cluster algorithm. However, because the ( ; t)-criteria establishes a lower bound on the availability of cluster paths, preference is given to those algorithms capable of incorporating link and path availability information as a routing metric and of using maximum availability as an optimization criteria when establishing paths. Arguments have been made against path optimization in ad-hoc networks 7, 27]; however, these arguments are based upon the assumption of a monolithic network without clustering. ( ; t)?Clusters gradually adapt the cluster topology to maintain a consistent level of path stability such that path optimization becomes e ective. In Subsection 5.3, it is shown how the path availability can be calculated from the individual link availabilities along the path. This can be accomplished based on aggregated path information using a modi ed Bellman-Ford algorithm to nd the maximum availability path or using Dijkstra's algorithm if complete link status information is available. Because path availability is a time-varying quantity which depends on the individual link properties, it is more e cient if the characteristics of the links are known at each node. To overcome the shortcomings of link-state protocols, several alternatives which provide complete link status information along selected paths have been proposed for use in highly dynamic environments. Examples which are well adapted for intra-cluster routing include the Link Vector Algorithm (LVA) 9] and the Wireless Routing Protocol (WRP) 24]. Based on complete link status information, it is possible to estimate the current link availability anywhere in the cluster without periodic routing updates. If aggregated routing information is used, the path availability information will become outdated without periodically updating the path status. A node's membership in a cluster is implied by the contents of the routing tables distributed among the active nodes in that cluster. No distinct cluster table is required since it is the routing algorithm as modulated by the cluster algorithm which determines the set of nodes that are in the cluster. Consequently, a node's routing table gives a complete picture of its current view of the cluster. Accordingly, cluster convergence is simply a matter of the convergence of the routing tables in the cluster.

5

Inter-cluster Routing: Inter-cluster routing is achieved using a demand-based protocol that establishes paths by executing a path-search query and response algorithm. With respect to this process, each node can be considered as a route cache for the set of nodes in its cluster. In the worst case, the response phase will begin as soon as the rst node in the target destination's cluster receives the route query. Queries will never be propagated further into the cluster in which the target destination resides. One methodology for maintenance of end-to-end routing between destinations in di erent clusters is direct imple-

mentation of a at-routed reactive routing protocol such as the Temporally Ordered Routing Algorithm (TORA) 26, 27] or the Ad-Hoc On-Demand Distance Vector Algorithm (AODV) 28]. Speci cally, each node requiring a route rst searches for the desired destination in its cluster routing table which is maintained pro-actively by the intracluster routing protocol. If the destination is not found, the node initiates a route discovery process if it is the source node, or it propagates the request if it is processing another node's route query. As such, every node will participate in two routing protocols: one within a cluster and one for non-cluster destinations. Consequently, each node will be able to maintain routes to any connected destination. The problem with the at-routed reactive approach is that it fails to take advantage of the cluster topology, which could be used to more e ciently manage the route discovery and maintenance processes. To address this shortcoming, an improved methodology for ( ; t)?Cluster interconnection is proposed which leverages the cluster topology in order to more e ciently discover and maintain end-to-end routing between nodes in di erent destinations by adapting the ZRP IntErzone Routing Protocol (IERP). IERP assumes a topology comprised of a sequence of overlapping zones and speci es a bordercasting technique which is used to e ciently construct routes across multiple zones. However, IERP as de ned for ZRP cannot be directly applied to the interconnection of ( ; t)?Clusters since these clusters are designed not to overlap. To bridge the di erences between the requirements of IERP and the properties of the ( ; t)?Clusters, the following adaptations are required: 1. The border nodes of an ( ; t)?Cluster consist of the set of nodes which are adjacent to nodes that are not members of the same cluster. Each border node treats adjacent clusters 5 as super-nodes and advertise reachability to those super-nodes within their ( ; t)?Cluster. Consequently, each node in a cluster has knowledge of and pro-actively maintains routes to the set of adjacent clusters identi ed by the border nodes. 2. The bordercasting process de ned by IERP must be modi ed to allow the exchange of the route query from the egress border node of one cluster to the ingress border node of its adjacent clusters. 3. Each ( ; t)?Cluster egress border node processing an IERP route query will append its CID to the route query and forward one copy of the query to those neighboring nodes which are ingress border nodes in adjacent clusters. Consequently, a sequence of CIDs is accumulated, which represents an inter-cluster route to the desired destination. 4. Each ( ; t)?Cluster ingress border node searches its routing table for the destination. If the destination is found, the node appends its CID to the accumulated sequence of CIDs in the route query and returns it in the response message which is sent back along the accumulated sequence of clusters in reverse order.

5 An adjacent cluster to a node n, is one with a border node that is adjacent to a border node in the node n's cluster.

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999 Unlike ZRP, this modi ed scheme builds a route as a sequence of clusters rather than nodes. The speci c paths across each cluster are determined dynamically by the intracluster routing algorithm. Since each node in a cluster maintains routes to the set of adjacent clusters, this methodology provides a strategy which is robust in that routes will remain viable so long as the cluster adjacencies remain intact|even if the speci c border nodes change. Thus, it is highly adaptive with respect to node mobility and requires less reactive route maintenance. Evaluation of ( ; t)-paths requires speci cation of two system parameters, and t. The e ects of these parameters are tightly coupled, making it di cult to select optimal values. Large values for t seem desirable as they imply more cluster stability and reduce the computational requirements of cluster maintenance. However, large t will drive down the path availability between nodes of the cluster for the same mobility patterns|making it more di cult to achieve the required lower bound, . Consequently, large values of t will tend to result in smaller clusters, whereas, small values of t will increase the cluster size which results in more optimal routing with increased routing overhead. Since establishes a lower bound on the probability that a given cluster path will remain available for time t, it controls the cluster's inherent stability. Thus, for a given level of stability the role of t is to manage the cluster size, which controls the balance between routing optimality and e ciency. Given that no single pair of values for and t can be optimal or even su cient in all situations, at least one of the parameters should be adaptive. In particular, appropriate bounds on path availability should consider the level of tra c and possibly the QoS requirements of connections routed through the cluster in order to ensure a su cient level of cluster stability which will support those connections with high probability. In the remainder of this section a methodology is proposed for adaptive maintenance of the system parameter . The above observations suggest that the value chosen for should re ect tra c conditions. Assuming that path availability is an ergodic process, it represents the average proportion of time an ( ; t)-path is available to carry data. Consequently, places a lower bound on the e ective capacity of the path over an interval of length t. This bound must be su cient to support the current tra c load. If QoS support is considered, the bound must be high enough to support the bandwidth which has been allocated to realtime connections. If the average packet delay at a node along an ( ; t)?path exceeds the availability of that path, excessive queuing delays may be incurred in the network. Consequently, a necessary condition for satisfying the tra c requirement is to establish an e ective capacity over any interval of length t, which results in average delays that are signi cantly less than t. Based on this observation, queuing models can be used to determine a lower bound for path availability.

6

3.3 ( ; t)?Cluster Parameters

The development of complete queuing models is beyond the scope of this paper; however, a simpli ed model is presented next in order to illustrate this concept. Assume, without loss of generality, that t is identical at every node in a cluster. If the cluster's topology remains stable over the interval of length t, then routing will be deterministic during this interval, and standard assumptions 18] permit the ad-hoc network to be modeled as a network of Jackson queues 19]. Let the link capacity be C bits-per-second, and the mean packet length be 1= bits. The e ective packet service rate, eff , over the interval t can be determined based upon the path availability according to Equation-1. Based on the Jackson model, each node can be treated as an independent M/M/1 queue. Using knowledge of the current aggregate arrival rate, , and the e ective service rate, eff , the M/M/1 results can be applied to nd the mean total packet delay T . Since this delay must be less than t, this approach establishes a lower bound on the path availability as shown in Equation 4:

eff =

C

T = t

eff

1 1

?

(1) (2) (3) (4)

An e ective adaptive strategy for determining the value of controls the minimum level of cluster stability required to support the tra c load and QoS requirements of established connections. The choice of the parameter t is a system design decision which determines the maximum cluster size achievable for di erent rates of mobility when no tra c exists in the network.

C ? (1 + t) tC

4

(

; t)?Cluster Algorithm

Two key requirements motivate the design of a successful dynamic clustering algorithm: (1) The algorithm should achieve a stable cluster topology, and (2) it should do so with minimal communications overhead and computational complexity. Consequently, in a highly dynamic environment the algorithm should be distributed, operate asynchronously, and require minimal coordination among the nodes. Furthermore, it is highly unlikely that an optimal cluster topology will be achievable. Therefore, optimal clustering should not be a concern|rather an egalitarian view of clustering should be adopted with the objective of achieving good clusters. This means that clusters are stable relative to the overall topology, that clustering decisions are made fairly, and that the cluster topology converges to meet the clustering criteria. Finally, the algorithm should be self starting and robust, in that after nite periods of network instability it eventually converges to a stable and e cient clustered topology.

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999 Clearly, if the underlying topology is so unstable that ooding is the only viable routing strategy, then no algorithm will be able to achieve the key requirements. Furthermore, if the topology is static or quasi-static, then the nature of clustering, and thus the design criteria, will be substantially di erent. In this case optimal clustering can be achieved either with o -line approaches or using centralized algorithms based on complete topological information. Somewhere in between these two extremes lies the domain for dynamic clustering. This is where the ( ; t)?Cluster algorithm is designed to operate. ( ; t)?Clusters are dynamic entities which are created, expanded, contracted and eventually terminated based upon routing information which is maintained on a set of cooperating mobile nodes. Other than the dissemination of topology information by the intra-cluster routing protocol, the cluster algorithm does not require any additional message types; however, it must be able to trigger a routing update when joining or leaving a cluster. The strength of the ( ; t)?Cluster algorithm is that it is minimal and requires no far-reaching inter-nodal coordination when initiating clustering activity. Its role is to modulate the actions of the intra-cluster routing algorithm by e ectively ltering its view of the network. This is achieved by manipulating the node's CID and exploiting functionalities which already exist or can easily be incorporated into existing protocols at the routing and network-interface layers. A distributed asynchronous algorithm is speci ed for maintaining ( ; t)?Clusters. The algorithm is simple, efcient, and self starting. Every node in a cluster participates in a pro-active routing protocol wherein the scope of routing information propagation is controlled by the nodes' view of their cluster membership. A node neither processes nor propagates routing information from nodes which are not identi ed as belonging to its own cluster. However, routing information from nodes which do belong to its cluster is processed and disseminated. No centralized control over the clustering process is required. Nodes can asynchronously join, leave, or create clusters. The algorithm is event driven, and its actions depend upon the nodes' ability to satisfy the ( ; t)-criteria with respect to their current cluster or the cluster they are attempting to join. The ( ; t)?Cluster algorithm is driven by both hardstate and soft-state events. Speci cally, topological changes, which are detected locally or learned through routing updates, trigger speci c actions by the algorithm. Hard-state events include node activation, node deactivation, link activation, and link failure. In general, the algorithm requires clustered nodes to determine whether or not the ( ; t)-criteria continues to be satis ed following a topological change. Additionally, soft-state is maintained at each node through the use of a timer referred to as the -timer. This timer determines the maximum time, t, for which the node can guarantee path availability to each cluster destination with probability . The expiration of the -timer is treated by the algorithm as a topological change requiring the node to re-evaluate the ( ; t)-criteria with respect to its cluster.

7

All cluster actions are implied by information received through routing and network-interface layer protocol information. In the remainder of this section, the ve events which drive the ( ; t)?Cluster algorithm, namely, node activation, link activation, link failure, expiration of the timer and node deactivation, and the actions taken by a node in response to each of these events are described. The section concludes with a discussion of the major properties of the ( ; t)?Cluster algorithm.

4.1 Node Activation

The primary objective of an activating node 6 is to discover an adjacent node and join its cluster. In order to accomplish this, it must be able to obtain topology information for the cluster from its neighbor and execute its routing algorithm to determine the ( ; t)-availability of all the destination nodes in that cluster. The source node can join a cluster if and only if all the destinations are reachable via ( ; t)-paths. Such a cluster is referred to as a feasible cluster. The source node will continue checking each neighbor in sequence until it nds a feasible cluster or runs out of neighbors. If the source node is unable to join a cluster, it will create its own cluster, referred to as an orphan cluster, and wait for another opportunity to cluster with other nodes. The rst step upon node activation is the initialization of the source node's CID to a pre-de ned value which indicates its unclustered status. The network-interface layer protocol is required to advertise the node's CID as part of the neighbor greeting protocol 23] and in the header of the encapsulation protocol. This enables nodes to easily identify the cluster status and membership of neighboring nodes and of the source of the routing updates|a necessary function to control the dissemination of routing information. When its network-interface layer protocol identi es one or more neighboring nodes, the source node performs the following actions. First, the source node identi es the CIDs associated with each neighbor. Next, it evaluates the link availability associated with each neighbor according to either a system default mobility pro le or mobility information obtained through the network-interface layer protocol or physical-layer sensing. The precise methodology and the information required for the evaluation of link availability is described in Subsection 5.3. Finally, the neighbors, having discovered the unclustered status of the source node, automatically generate and transmit complete cluster topology information, which they have stored locally as a result of participating in the cluster's intra-cluster routing protocol. This topology synchronization function is a standard feature of typical pro-active routing protocols when a router discovers the activation of a link to a new router. The source node does not immediately send its topology information to any of the neighbors. Having completed the above actions, the source node proceeds according to the cluster status of the identi ed

6 The activating node will be referred to as the source node.

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999 neighbors. If none of the neighbors are clustered, the source node sets a randomized back-o -timer during which time it delays any further clustering activity. The purpose of this timer is to e ectively spread out the clustering of nodes which have activated more or less simultaneously. This minimizes the probability that each of these nodes is forced to create an orphan cluster. If the source node has identied one or more adjacent clusters it will evaluate each such cluster's feasibility in turn. The precise algorithm steps for evaluating cluster feasibility depend upon the nature of the topology information|distance-vector or link-state| and the routing algorithm. If the source node determines that a cluster is feasible, it joins that cluster. The cluster join action is achieved asynchronously without any additional inter-nodal coordination. The source node sets its CID to equal the CID of the cluster it is joining, and it generates its own routing update, which is broadcast to its neighbors. Recognizing their own CIDs in the routing update, those neighbors which are members of the target cluster process the source node's routing update. In doing so, the routing protocol automatically adds the source node as a destination in their respective routing tables, which infers cluster membership.

Procedure Node Activation(node) begin if (node has no neighbors)

f g f

8

Procedure Link Activation(node) begin if (node is an orphan)

f

tmp CID = CID; CID = UNCLUSTERED; node status = UNCLUSTERED; for (each neighbor N) f if (N's CID != UNCLUSTERED) f if (Cluster Is Feasible(N's cluster)) f Join Cluster(N's cluster); node status = CLUSTERED; break;

g g g if (node status == UNCLUSTERED) f

end

g

g

CID = tmp CID; node status = CLUSTERED;

Figure 3: Outline of Link Activation Algorithm. A link activation detected by a clustered node which is not an orphan is treated as an intra-cluster routing event. Hence, the topology update will be disseminated throughout the cluster. Unlike reactive routing which respond after path failure, the dissemination of link activation updates is a key factor to an ( ; t)?Cluster node's ability to nd new ( ; t)-paths in anticipation of future link failures or the expiration of the -timer. The objective of an orphan node is to either have its own cluster expanded through the actions of other nodes or to join an existing cluster unless node mobility is very high. Link activation triggers an orphan node's attempt to join a cluster. In order to receive cluster topology information from its new neighbor, the orphan node must temporarily reset its CID to indicate its unclustered status. Only information received from nodes which are in the same cluster as a destination or in the unclustered state are passed by the cluster algorithm protocol to the routing-layer (See Figure1). Thus, by changing its CID the orphan node triggers the transmission of routing updates from its neighbor. Upon receiving the cluster topology information, the node evaluates cluster feasibility and either joins the cluster or returns to its orphan cluster status depending upon the outcome of the evaluation. Figure-3 shows the pseudo-code for the algorithm executed by an orphan node upon detecting a link activation. The objective of a node detecting a link failure is to determine if the link failure has caused the loss of any ( ; t)paths to destinations in the cluster. A node's response to a link failure event is two-fold. First, each node must update its view of the cluster topology and re-evaluate the path availability to each of the cluster destinations remaining in the node's routing table. Second, each node forwards information regarding the link failure to the remaining cluster destinations. This second action is a function of the routing protocol. Each node receiving the topology update re-evaluates its ( ; t)-paths as if it had directly expe-

4.2 Link Activation

else

Initiate Cluster(); node status = CLUSTERED ;

for (each neighbor N) f if (N's CID != UNCLUSTERED)

f

node status = UNCLUSTERED; found clustered = false ;

found clustered = true; if (Cluster Is Feasible (N's cluster)) f Join Cluster(N's cluster); node status = CLUSTERED; break;

g

g

if (node status == UNCLUSTERED) f if (found clustered == true)

f Initiate Cluster(); g

g

else

f

end

g

g

g

Sleep(random backoff time); Node Activation(node);

Figure 2: Outline of Node Activation Algorithm. If the source node's network-interface layer protocol detects no adjacent nodes, or its attempts to join an adjacent cluster fail due to cluster infeasibility, the cluster algorithm generates and sets a globally unique CID which will be used in subsequent neighbor greeting exchanges. In this orphaned state the ( ; t)-criteria is trivial because the path availability of the source node to itself is always 1:0. In order to periodically re-attempt to join a neighboring cluster, the node's -timer is set to the value of the system parameter t. Figure-2 shows pseudo code for the algorithm executed by the source node upon activation.

4.3 Link Failure

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999

Procedure Link Failure(node) begin t = time remaining on(alpha timer); if (Cluster Is Feasible(my cluster))

f g f

9

else

/* status quo */

Leave Cluster(my cluster); node status = UNCLUSTERED; CID = UNCLUSTERED; found cluster = flase; for (each neighbor N) f if (N's CID != UNCLUSTERED) f found cluster = true; if (Cluster Is Feasible(N's cluster) f Join Cluster(N's cluster); node status = CLUSTERED; break;

g

if (node status == UNCLUSTERED) f if (found cluster == true)

f Initiate Cluster(); g

g

g

else

f g

Sleep(random backoff time); Node Activation(node);

end

g

g

Figure 4: Outline of Link Failure Algorithm. rienced the link failure. When evaluating path availability to destination nodes within the cluster following a topology change, it is necessary to adjust the timing parameter to re ect that the -timer has not yet expired. Use of the full value of t would unnecessarily penalize the nodes by requiring a path availability which is higher (further out in time) than required by the cluster criteria. Thus, the estimated availabilities will re ect the probabilities evaluated at the maximum time for which this node has already made its probabilistic guarantee. Using the topology information available at each node, the current link availability information is estimated and maximum availability paths are calculated to each destination node in the cluster. If the node detects that a destination has become unreachable, then the node assumes that the destination has deactivated or otherwise departed from the cluster. In this case, the destination is removed from the node's routing table and will not be considered further in the evaluation of ( ; t)-paths. If a node detects that any of the remaining cluster nodes are connected within the cluster but not ( ; t)-reachable, it will voluntarily leave the cluster. A node leaves a cluster by sending a routing update to its neighbors indicating that the status of all its links are down or equivalently in nite distance to itself. It then resets its own CID to the unclustered value and proceeds according to the rules for node activation. No further action is required following a link failure if the node successfully evaluated ( ; t)-paths to each destination in the cluster. Figure-4 presents pseudo code of the algorithm executed by a node which detects a link failure through the services of the network-interface layer protocol or receives a topology update which re ects a link failure.

The -timer controls cluster maintenance through periodic execution of the intra-cluster routing algorithm at each node in a cluster. Using the topology information available at each node, the current link availability information is estimated and maximum availability paths are calculated to each destination node in the cluster. If any of the paths are not ( ; t)-paths, then the node leaves the cluster. -timer based cluster maintenance is asynchronous and requires no inter-nodal communications other than the action required for a node's departure from its cluster. The precise actions taken by a node upon the expiration of its -timer are virtually identical to the actions taken by a node when it detects a link or node failure, with the exception that the -timer triggers an orphan node to re-attempt to join a cluster in a manner which is identical to link activation. Cluster maintenance based on -timer expiration accomplishes two fundamental objectives in the ( ; t)?Cluster framework. First, it provides the mechanism by which nodes pro-actively seek to extend their path availability guarantees|thereby providing the basis for achieving cluster stability. Nodes which are unable to do this leave the cluster|with the objectives of shrinking the cluster in order to improve its stability for the remaining nodes and nding a better cluster for itself. Secondly, -timer maintenance leads to topological synchronization, which provides the basis for cluster convergence. The issue of cluster convergence is discussed further in Subsection 4.6. Since each node in a cluster maintains an independent -timer, which is started when a node joins the cluster, a natural phase shift exists across the nodes in a cluster, which produces the desirable e ect of distributing the collective reactions to changes in path availability. This allows for gradual adjustments in cluster routing and membership. Because it is treated as a topology change, the pseudo-code in Figure-4 also applies to -timer expiration. The event of node deactivation encompasses four related events, namely, graceful deactivation, sudden failure, cluster disconnection, and voluntary departure from the cluster. In general, each of these events trigger a response by the routing protocol. As a result, nodes determine that the node which has deactivated is no longer reachable. In the cases of graceful deactivation and voluntary departure, the deactivating node announces its departure by disseminating a topology update to all the nodes in the cluster, which indicates the failure of all its incident links. Nodes receiving this status update e ectively erase the node from their own view of the cluster. If a node becomes disconnected from the cluster due to mobility, or the node fails suddenly, the response of the nodes will depend on the speci c sequence of events which lead to the convergence of routing in the cluster. A node can recognize for itself that is has become cluster disconnected by virtue of losing paths to the entire set of nodes in the cluster. Hence, it becomes an orphan node and pro-

4.4 Expiration of -timer

4.5 Node Deactivation

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999 ceeds according to the rules previously described for an activating node. However, the remaining nodes in its original cluster may not immediately be able to determine that this node is unreachable and will attempt to re-evaluate their ( ; t)-paths to the destination. In this case, these nodes may determine that the destination is no longer reachable via an ( ; t)-path, and, consequently, they will also leave the cluster voluntarily, which is a recoverable, although sub-optimal, response. Each node receiving a topology update which re ects the node deactivation in the cluster uses the new topology information in order to evaluate ( ; t)?paths to the remaining cluster-connected destinations in the cluster. Should the node fail to nd an ( ; t)?path to any of the destination nodes in the cluster, it leaves the current cluster and proceeds according to the rules of node activation previously described. These actions are also re ected by the pseudo-code in Figure-4.

10

4.6 Discussion

The design of the ( ; t)?Cluster algorithm was predicated upon two basic tenets: (1) Optimality is inherently di cult or impossible to achieve in highly dynamic environments which are constrained by the limitations of the physical media, and (2) e ciency is more important than optimality in these environments in order to achieve acceptable levels of performance. Consequently, the overriding design principle was based on this fundamental tradeo . Speci cally, two observations can be made about the ( ; t)?Cluster algorithm with respect to the aforementioned design tradeo s. First, no attempt was made to maintain or specify the criteria for optimal cluster organization. This is a di cult problem even in a xed topology network in which cluster size is typically used as the basis for optimization. Second, minimization of inter-nodal coordination and communications was substantially more important than ensuring complete consensus at all times with respect to each clustering decision, so long as the cluster topology converges under stable conditions. Furthermore, the rate of topology change and network latency make synchronization of each clustering action through distributed consensus protocols infeasible|even if bandwidth and processing resources are plentiful. The remainder of this section presents discussion of the properties of the ( ; t)?Cluster algorithm with respect to cluster convergence and partitioning. ( ; t)?Cluster Convergence: As a consequence of the design tradeo s, cluster convergence with respect to the requirements of De nition 3.4 is not guaranteed at every instant. Rather, each node asynchronously, and without far-reaching coordination with any other nodes, makes its own clustering decisions based upon the most recent information it has or can obtain directly from an adjacent node. Achieving a-priori consensus is prohibitively complex particularly because the asynchronous property of the ( ; t)?Cluster algorithm permits any number of nodes to join a cluster simultaneously. Consequently, nodes make

clustering decisions based on their ability to establish ( ; t)paths in the forward direction without attempting to ensure that ( ; t)-paths exist in the reverse direction from all the nodes in the cluster. As a result of latency, it is therfore possible for a node to make a clustering decision without complete knowledge of the set of nodes that are in the cluster. Figure-5 illustrates these two concepts and demonstrates how cluster convergence is achieved. In Figure-5(a), node m is depicted within range of node a at time t0 . Having received topology information from node a, node m has evaluated ( ; t)-paths to nodes a,b,c, and d, which are in a cluster together. The dashed lines in the gure represent the ( ; t)-paths. Node m now joins the cluster by setting its CID and disseminating its own routing information update to the existing nodes in the cluster. Note that at time t0 no ( ; t)-paths have been con rmed from the existing nodes in the cluster back to node m. In Figure-5(b), node n is shown at time t1 , just after having come into range of node d. Node d still has not established that node m has joined this cluster. Consequently, when node n evaluates ( ; t)-paths it does not include node m in the process. Assuming node n nds ( ; t)-paths to nodes a,b,c, and d, it joins the cluster. Convergence is achieved when all nodes in the cluster have a common view of cluster membership. Assuming that no more nodes join the cluster after time t1 , and that all the nodes' -timers expire in the interval t1 < t < t such that each node executes cluster maintenance during that interval, then Figure-5(c) depicts the cluster state at time t when the cluster is guaranteed to be converged. ( ; t)?Cluster Partitioning: The most basic form of cluster partitioning involves the disconnection of a single node from its cluster. As discussed in Subsection 4.5, when a single node recognizes that it has become cluster disconnected it leaves the cluster. The response of the remaining nodes in the cluster depends upon the precise timing of events. These nodes will either logically remove the disconnected node from their views of the cluster or depart from the cluster if the remaining nodes are no longer reachable via an ( ; t)-path. However, if a partitioning exists with more than one node in each partition, it is possible for the nodes in each of these partitions to decide that the nodes in the other partitions have e ectively deactivated. Consequently, they will continue to operate under the assumption that their partition is the cluster. Under these circumstances it is possible for more than one cluster to exist with the same CID. However, it is essential to prevent duplicate CIDs from persisting because ambiguous CIDs can lead to inter-cluster routing con icts. To resolve the problem of duplicate CIDs a renaming strategy is required. Speci cally, it must be possible to detect that a cluster has partitioned and for each partition to adopt unique CIDs. The strategy for achieving this is based upon embedding a globally unique node identi er (NID) into each CID. Consequently, each node in a cluster can determine the NID of the node which generated the cluster's current CID. This node will be referred to as the

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999 PSfrag replacements

t0 a b C c d t0 t t1 a m

Range

(a) Node m Joins Cluster C . (b) Node n Joins Cluster C .

11

ag replacements

t1 t n

PSfrag replacements

b C c d t0 t1 t a m

Range

(c) Cluster C Converges.

b

C

c d

m Range

n

n

Figure 5: Convergence of ( ; t)?Cluster Algorithm.

parent of the cluster, although it carries no other functional responsibility. Partition detection requires each node to detect when the cluster's parent node is removed or removes itself from the cluster. Renaming involves selection of a new parent and assignment of a new CID to a subset of nodes in a cluster following detection of a partition. Cluster renaming is achieved as follows: Upon detection of a cluster partition, each node determines if its NID is the lowest NID among the nodes in its cluster routing table. The node with the lowest NID generates a new CID, adopts that CID itself, and broadcasts a Cluster Rename message, which includes the previous and the new CIDs, to the nodes in its connected partition of the cluster. Each node receiving a Cluster Rename message adopts the new CID, e ectively joining a new cluster. If more than one node believes it has the lowest NID due to inconsistencies in the cluster routing tables, only the rst received Cluster Rename message will be accepted. In the worst case, the cluster partition may be subdivided into multiple new clusters. If a node does not have the lowest CID and does not receive a Cluster Rename message within a pre-speci ed timeout interval, the node leaves the cluster and proceeds according to the rules of node activation previously described.

termine the conditional probability that the nodes will be within range of each other at time t0 + t, given that they are located within range of each other at time t0 . Assuming that link failures are independent, and the rate of node deactivation is small relative to the rate of link failure, this model shows how to evaluate path availability|providing the basis for ( ; t)?Cluster management. The model described in this section characterizes the aggregate behavior of nodes in a large network. In these environments, any correlation is assumed to be insigni cant due to the large number of independent nodes. In addition, recent performance studies of ad-hoc network routing protocols have adopted random uniform models 11, 8] or modi ed random models which include pause-times 4] in order to model node mobility. Pause-time random models are supported inherently by the model proposed in this paper because the speed of a mobile unit can be from any distribution, so long as it has a mean and standard-deviation. Furthermore, in a large ad-hoc network with many transient users, information which accurately re ects the detailed mobility characteristics of individual users is likely to be di cult or impossible to maintain. Consequently, in these types of environments the random assumption is reasonably optimal.

5 Ad-Hoc Mobility Model

In this section, a random walk-based mobility model is developed for ad-hoc networks, and expressions are derived which characterize the distribution of aggregate distance and direction covered by a node over a speci c interval of time. Based upon this model, and assuming that a link is active if the distance between two nodes is less than a system dependent threshold 7 , the objective is to characterize their mobility and use this characterization to de7 The e ective distance threshold, also referred to as the range, is a function of numerous system dependent factors including but not limited to signal power, fading, noise immunity and receiver sensitivity.

5.1 Random Ad-Hoc Mobility

The random ad-hoc mobility model proposed in this section is a continuous-time stochastic process, which characterizes the movement of nodes in a two-dimensional space. Based on the random ad-hoc mobility model, each node's movement consists of a sequence of random length intervals called mobility epochs during which a node moves in a constant direction at a constant speed. The speed and direction of each node varies randomly from epoch to epoch. i Consequently, during epoch i of duration Tn, node n moves i T i in a straight line at an angle of i . a distance of Vn n n The number of epochs during an interval of length t is the discrete random process Nn (t). Figure-6(a) illustrates the

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999 movement of node n over six mobility epochs, each of which i i is characterized by its direction, n , and distance, Vni Tn . The mobility pro le of node n moving according to the random ad-hoc mobility model requires three parameters: 2 n ; n and n . The following list de nes these parameters and states the assumptions made in developing this model: The epoch lengths are IID exponentially distributed with mean 1= n . The direction of the mobile node during each epoch is IID uniformly distributed over (0; 2 ) and remains constant only for the duration of the epoch. The speed during each epoch is an IID distributed random variable (e.g. IID Normal, IID Uniform) with 2 mean n and variance n and remains constant only for the duration of the epoch. Speed, direction and epoch length are uncorrelated. Mobility is uncorrelated among the nodes of a network and links fail independently.

12

PSfrag replacements

R6 n

6

n0

R5 n

5

R4 n Rn (t) R1 n

3 4

R2 n

2

1 1 = Vn Tn 1

n

Nodes with limited transmission range are assumed to experience frequent, random changes in speed and direction with respect to the length of time a link remains active between two nodes. Furthermore, it is assumed that the distributions of each node's mobility characteristics change slowly relative to the rate of link failure. Consequently, the distribution of the number of mobility epochs is stationary and relatively large while a link is active. Since the epoch lengths are IID exponentially distributed, Nn (t) is a Poisson process with rate n . Hence, the expected number of epochs experienced by node n during the interval (0; t) while a link is active is n t 1. These assumptions re ect a network environment in which there are a large number of heterogeneous nodes operating autonomously in a ad-hoc fashion, which conceptually re ects the environment considered in the design of the ( ; t)?Cluster framework. That is, while some nodes may share similar objectives and move together, there is a large enough population of nodes and frequency of events 8 that the overall correlation is insigni cant and the aggregate e ective movement can be modeled by a random process. In order to characterize the availability of a link between two nodes over a period of time (t0 ; t0 + t), the distribution of the mobility of one node with respect to the other must be determined. To characterize this distribution, it is rst necessary to derive the mobility distribution of a single node in isolation. The single node distribution is extended to derive the joint mobility distribution which accounts for the mobility of one node with respect to the other. Using this joint mobility distribution, the link availability distribution is derived. If the link availability metric is known for each link along a path between two mobile nodes, assuming that links fail independently, the path availability is easily determined as the product of the individual link availability metrics.

PSfrag replacements

(a) Epoch Random Mobility Vectors

Single Node Mobility: Two de nitions are central to

1 2 3 4 5 6

n0

Rn (t)

R1 n

1 1 = Vn Tn

R2 n R4 n R5 n R6 n

n

(b) Random Mobility Vector (0; T )

the development of the single node mobility model. They de ne two random vectors that characterize the direction and distance moved by a mobile node during a single epoch and over an interval of length t respectively. ~ De nition 5.1 The epoch random mobility vector Rin represents the direction and distance moved by node n during i ~n mobility epoch i. It has magnitude Ri = jRi j = Vni Tn n which is the distance covered by node n during epoch i, and i phase n which is the direction of node n during epoch i. ~ De nition 5.2 Rn (t) is the random mobility vector for node n. The magnitude Rn (t) is equal to the distance from (X (t0 ); Y (t0 )) to (X (t0 + t); Y (t0 + t)), where (X ( ); Y ( )) is the position of the node at time . The phase angle n is the angle of the line joining the two points. The random mobility vector can be expressed as a random sum of the P1 ~n ~ epoch random mobility vectors: Rn (t) = Nn (t) Ri .

8 Events include the activation of a link or node, and changes in speed and direction of a node.

Figure 6: Ad-hoc mobility model node movement.

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999 Figure-6(a) shows a sample path for the movement of an arbitrary node n, over an interval of length t. For each ~ epoch, the gure shows the epoch vector Rin with magnii T i and direction i of the node during the epoch. tude Vn n n ~ The resulting random mobility vector Rn (t) is shown in Figure-6(b), and it can be seen that it is the vector sum of the individual epoch vectors. The following lemma charac~ terizes the magnitude and phase distributions of Rn (t). Lemma 5.1 Consider a mobile node which is located at postion (X (t0 ); Y (t0 )) at time t0 and moves according to a 2 ~ random ad-hoc mobility pro le, < n ; n ; n >. Let Rn (t) be the resulting random mobility vector. The phase angle, ~ n , of Rn (t) represents the aggregate direction of the mobile node and is uniformly distributed over (0; 2 ), and the magnitude Rn (t) represents the aggregate distance moved by the node and is approximately Raleigh distributed with 2 parameter n = (2t= n )( n + 2 ): n

13

Pr(Rn (t) r) 1 ? exp( ?r ) 0 r 1

2

Pr( n

) = 21

0

2

(5) (6)

n

The derivation of these distributions is an application of the theory of uniform random phasor sums 3]. The basic idea is to decompose the distance moved during each i mobility epoch, Ri = Vni Tn , into X and Y components, n i Xn = Rin cos i and Yni = Rin sin i . According to the random ad-hoc mobility model, n t 1. For the Poisson distribution this is a su cient condition for the Central Limit Theorem (CLT) to hold with respect to the summations of the X and Y components over all the epochs during P1 i an interval of P length t. Consequently, Xn (t) = Nn (t) Xn i and Yn (t) = Nn (t) Yn are approximately normally dis1 tributed and are shown to have zero mean and variance 2 = (t= n ) ( n + 2 ). Furthermore, Xn (t) and Yn (t) are n shown to be uncorrelated; therefore, the product of the two normal distributions gives the joint distribution of X and Y. This is transformed using standard methods into polar coordinates to produce the joint distribution with respect to Rn (t) and n . The results of the lemma follow by taking the marginal distributions with respect to these random variables. Simulation results reported in 22] validate these analytical results. The results of this section show that if a mobile node moves in a random uniform direction during each mobility epoch, the random nature of the mobile's direction is preserved over several direction and speed changes. Along with the distribution of the aggregate distance, this allows for the characterization of the joint mobility of two mobile nodes by considering the relative movement of one node with respect to the other.

movement of a single node with respect to a xed point of reference 14, 32]. Based on the assumption of random link failures, the ad-hoc problem can be transformed into the cellular problem by considering the mobility of two nodes at a time and xing the frame of reference of one node with respect to the other. This transformation is accomplished by treating one of the nodes as if it were the base station of a cell, keeping it at a xed position. For each movement of this node, the other node is translated an equal distance in the opposite direction. These concepts are re ected in the following de nitions and lemmas: De nition 5.3 The vector R~ (t), representing the equivm;n alent random mobility vector of node m with respect to node n, is obtained by xing m's frame of reference to n's position, and moving m relative to that point. Lemma 5.2 Let two mobile nodes m and n move accord2 ing to random ad-hoc mobility pro les, < m ; m ; m > and 2 >, respectively. By Lemma-5.1 the random mo< n; n; n ~ ~ bility vectors for each node are Rm (t) and Rn (t) with uniformly distributed direction and Raleigh distributed magnitude. Let m and n be the parameters of the Raleigh distributions. Rm;n (t) is the magnitude of the di erence ~ ~ Rm (t) ? Rn (t), and is Raleigh distributed with parameter m;n = m + n and the phase is uniformly distributed over (0; 2 ). The X and Y components of the two uniformly dis~ ~ tributed Raleigh phasors Rm (t) and Rn (t) are each approximately normal with zero mean and variance = (t= m ) 2 2 ( m + 2 ) and (t= n ) ( n + 2 ), respectively. Since the two m n nodes move independently according to the random ad-hoc model, the distributions of Xm;n (t) = Xm (t) ? Xn (t) and Ym;n (t) = Ym (t) ? Yn (t) are also normal with zero mean and variance = (t= m ) ( m 2 + m 2 ) + (t= n ) ( n 2 + n 2 ). The result follows by taking the joint distribution of Xm;n(t) and Ym;n (t), transforming into polar coordinates and taking the marginal distributions. ~ ~ Lemma 5.3 R~ (t) = Rm(t) ? Rn(t) is the equivalent m;n random mobility vector of node m with respect to node n. Corollary 5.1 By Lemma-5.2 and Lemma-5.3, the equivalent random mobility vector node m with respect to node n is approximately Raleigh distributed and has a uniformly distributed direction.

In this section, the distributions for mobile node distance and direction are used to derive expressions for link availability based upon di erent initial conditions. Assuming that link failures are independent, and the rate of node deactivation is small relative to the rate of link failure, it is shown how the expression for link availability can be used to derive the path availability metric. how the joint mobility problem Joint Node Mobility: In cellular networks the charac- beCorollary-5.1 showsan equivalent problem involving can transformed into the 9 relies on the analysis of the terization of mobility metrics movement of a single node. In this section, the result of 9 Residence time and hando rate are examples of mobility metrics. Corollary-5.1, along with the distribution of the distance

5.2 Random Ad-Hoc Link Availability

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999

14

PSfrag replacements

m0

Rm (t)

C0 C n

n0

Rn (t)

m

Rm;n (t)

(a) Joint Node Case

PSfrag replacements

C0 ) n0 Rm;n (t) Rm (tC n

m0

Rn (t)

m

(b) Single Node Transformation

Figure 7: Joint Mobility Transformation. covered by a single node as it moves across a cell prior to a hando 14], is used to derive the distribution of the availability of a link between two nodes. De nition 5.4 Let Lm;n(t) indicate the state of the link between nodes n and m at time t. Lm;n (t) = 1 if the link is active, Lm;n (t) = 0 if the link is inactive. De nition 5.5 Link availability is the probability that there is an active link between two mobile nodes at time t0 + t, given that there is an active link between them at time t0 . Note that a link is still considered available at time t even if it experienced failures during one or more intervals (ti ; tj ): t0 < ti < tj < t0 + t. More speci cally, for nodes n and m, link availability is de ned as:

separated by a distance C . The transformation from single node random mobility vectors to the equivalent random mobility vector can be derived by noting how the progression of the distance between the nodes proceeds in an identical manner in both cases. The movement of m relative to n is shown for each epoch, along with the resulting equivalent random mobility vector R~ (t). If m lies within m;n the circular region of radius Req 10 centered at n, the link between the two nodes is considered to be active. Depending on the initial status and location of nodes m and n, two distinct cases of link availability can be identied. In the rst case, the link activation is caused by the activation of an adjacent node at time t0 . In the second case, the link activation is caused by node mobility, specifically, the nodes move into range of each other at time t0 . Assuming node n is active at time t0 , the link availability models re ect the following initial conditions: 1. Node Activation: Node m becomes active at time t0 , and is assumed to be at a random location within range of node n. 2. Link Activation: Node m moves within range of node n at time t0 by reaching the boundary de ned by Req and is assumed to be located at a random point around the boundary. Theorems 5.1 and 5.2 characterize the link availability between two mobile nodes, m and n, as re ected by the initial conditions stated above. Proofs are presented in Appendix-A, and simulation results reported in 22] demonstrate excellent agreement with these analytical models. Theorem 5.1 Node Activation: If node n moves accord2 ing to a random ad-hoc mobility pro le, < n ; n ; n >, and node m activates at time t0 within a uniform random distance from node n and moves according to a random ad2 hoc mobility pro le, < m ; m ; m >, then the distribution of the link availability over time is given approximately by the following expression, where (a; b; z ) is the KummerCon uent Hypergeometric function 11 :

Am;n (t)

2 1 ?4Req ) 1 ? ( 2 ; 2; m;n 2 + 2 2 2 m + n + n) m;n = 2t( m m n

(7) (8)

n

2

Theorem 5.2 Link Activation: Let < n ; n;

2 m ; m >,

> and < m; be the random ad-hoc mobility pro les of node n and node m, respectively and assume that and a link activates between n and m at time t0 such that m is located at a uniform random point exactly Req from n, then

the link availability is distributed according to the following expression, where I0 is a modi ed Bessel function of the rst kind, and m;n is de ned in equation 8:

Am;n (t) Pr(Lm;n (t0 + t) = 1jLm;n (t0 ) = 1)

.

Figure-7 demonstrates the mobility of two nodes initially

10 The transmission range of a mobile node is assumed to be bounded by an area with a hexagonal shape of radius R. Req 0:91R is the radius of the approximating circle with the same area 14]. 11 In equation 7, a = 1 and b = 2, consequently, the expression reduces 2 2 to 1 ? e z (I0 ( z ) ? I1 ( z )). 2 2

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999 1 Am;n (t) = 2 (1 ? I0 ( ?2Req ) exp( ?2Req ))

2 2

15

m;n

m;n

(9)

5.3 Random Ad-Hoc Path Availability

Lemma-5.4 completes the model developed in this section by relating path availability to individual link availabilities according to the de nition of path availability given in De nition 3.1, and the assumption of independent link failures. Lemma 5.4 Let Ai;j (t) be the availability for link (i; j ) 2 path k between nodes n and m as de ned in De nition5.5. The path availability at time t0 + t is denoted k (t). m;n According to the assumption of independent link failures, path availability is given by:

k (t) m;n

can be used to quantify the probability that a link will be available between two nodes after an interval of duration t. Lemma-5.4 shows how this model can be extended to completely characterize the availability of multi-hop paths across an ad-hoc network depending upon the initial status of each link in the path and assuming independent failures of each link. Although it was not considered directly in these models, the extension to include node failure or deactivation can be made by considering the link failure probabilities conditioned on the status of the nodes. The total probability of link failure will then consist of the weighted contribution due to mobility and to the failure of at least one of the nodes.

6 Simulation

col with respect to cluster stability and protocol e ciency, and those which characterize the packet level performance such as delay and throughput. The dynamic packet level performance depends substantially upon the properties of the underlying routing protocols and medium access control schemes, whereas, the inherent stability and e ciency of the ( ; t)?Cluster protocol can be evaluated by considering the following objectives: The ( ; t)?Cluster protocol should (1) adapt to node mobility by dynamically changing the cluster size according to the ( ; t)-criteria, (2) provide an e ective infrastructure which is more stable than the unclustered network, and (3) achieve cluster maintenance with minimal communications overhead. Based on the routing methodology discussed in Subsection 3.2, the ( ; t)?Cluster strategy reduces to a atrouted, reactive strategy when node mobility is very high on a persistent basis. The dynamic tra c performance in this worst case scenario is characterized by the performance of the inter-cluster routing protocol which has previously been reported in the literature 11]. However, network dynamics will not always be this severe. Furthermore, it is reasonable to expect that communications among nodes which are physically close together will be typical in many ad-hoc network applications. Consequently, the probability of communications among nodes in the same or nearby clusters is expected to be high. As demonstrated by the simulation results reported in this section, the control message overhead required to achieve clustering is insigni cant even at very high link failure rates. Therefore, the clustering overhead is expected to have little e ect upon delay and throughput characteristics. Thus, the ( ; t)?Cluster strategy will be able to provide improved tra c-level performance relative to a reactive routing strategy|without requiring signi cant control overhead. Based upon the above observations, a simulation model was developed to evaluate the inherent stability and e cieny of the ( ; t)?Cluster protocol. Speci cally, the sim-

The performance of the ( ; t)?Cluster strategy can be ask k Pr(Pm;n (t0 + t) = 1jPm;n(t0 ) = 1) sessed according to a variety of measures which broadly Y A (t + t) (10) fall into two distinct categories, namely, those which cap= i;j 0 ture the dynamic properties of the ( ; t)?Cluster proto(i;j )2k

Path Availability Cost Calculation: Theorems 5.1 and 5.2 demonstrate how the link availability can be calculated, thereby providing a link metric which represents a probabilistic measure of path availability. This metric can be used by the routing algorithm in order to construct paths which support a lower bound, , on availability of a path over an interval of length t as speci ed in De nition 3.2. Based on Lemma-5.4 and De nition 3.2, the availabilities of each of the links along a path are used by the ( ; t)?Cluster protocol to determine if the path is an ( ; t)?path and, consequently, if a cluster satis es the ( ; t)-criteria. In order to support this functionality in an ad-hoc network, the routing protocol must maintain and disseminate the following status information for each link: The initial link activation time: t0 . The mobility pro les for each of the adjacent nodes: < i ; i ; i2 >, i = m; n. The transmission range of each of the adjacent nodes: Req . The event which activated the link: (1) Node activation at time t0 , or (2) nodes moving into range of each other at time t0 . Based on this information, any node in an ( ; t)?Cluster can estimate, at any time , the availability of a link at time t + . This can be achieved because each node knows the initial link activation time t0 , hence, link availability is evaluated over the interval (t0 ; t + ). Nodes can use conditional probability to evaluate the availability of their own links because they have direct knowledge of such a link's status at time , whereas, remote nodes do not. Speci cally, for an incident link which activated at time t0 , a node will evaluate the availability at time t, given that it is available at time t0 . In this section the random ad-hoc mobility model was developed and Theorems-5.1 and 5.2 show how this model

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999 ulation was used to measure the strategy's e ectiveness in terms of mean performance metrics including the mean cluster size, the probability of a node being clustered, the mean node residence time within a given cluster, the mean cluster survival time, and the per-node control message processing rate. The remainder of this section discusses the simulation model and presents analysis of the results. The simulation was developed to model an ad-hoc network in which nodes activate and deactivate according to exponential distributions. Once active, each node moved according to the mobility model presented in Section 5 of this paper. A range of node mobility with mean speeds between 5:0 to 25:0 kilometers-per-hour (kph) were simulated. The speeds during each mobility epoch were Normally distributed, and the direction was uniformly distributed over (0; 2 ) 11]. Each node changed its speed and direction at random times. Although the simulation and the analytical models for link availability support distributions which include random pause-times 4], this performance evaluation assumed nodes to be in constant motion. Thus, extreme node mobility was used to produce a maximally dynamic environment. Link activations and failures were detected through a process running on each node that modeled a periodic link-sensing function. This was achieved by adjusting the new positions of all the nodes in the simulation according to their current position, speed and direction, and checking the distance between the sensing node and all other nodes. The results reported in this section were based upon a node activation rate of 250 nodes-per-hour. The mean-time to node deactivation was 1 hour. Using an approach similar to 11], nodes were initially randomly activated within a bounded region of 5x5 kilometers (km). Nodes which moved beyond this boundary were no longer considered to be part of the ad-hoc network and were e ectively deactivated. Each node's actions within the boundary were determined according to the ( ; t)?Cluster algorithm described in Section 4. An ideal link-state protocol was assumed for the distribution of topology information within each cluster; topology updates were sent to every node in the cluster following any link activation or failure detected by a clustered node according to the requirements of Subsection 5.3. Link availability was estimated for the entire cluster topology by each node following link failures or the expiration of the node's -timer according to the methodology presented in Subsection 5.3. Finally, ( ; t)?path availability was evaluated using Dijkstra's algorithm. For each simulation run, data was collected by sampling the network status once per second over an observation interval of 1 hour. The rst 2 hours of each run were discarded to eliminate transient e ects, and each simulation was re-run 10 times with new random seeds. Results are shown for two cases of transmission range, namely, Req = 1:0 km, and Req = 0:5 km. For the case of Req = 1:0 km, results are shown for = 0:4 using two values of t, 1 minute and 5 minutes. For the case of Req = 0:5 km, results are shown for t = 1 minute using two values of , 0:4 and 0:2. These values, although not comprehensive,

16

demonstrate a wide range of possible values for the system parameters. Furthermore, the node mobility model is intended to demonstrate the behavior of clustering under the worst case scenario as typi ed by the totally random movement of nodes over a wide range of speeds. Subject to these harsh conditions, it is physically impossible to achieve signi cantly high probabilities of path availability. Consequently, relatively low values were used for in the simulations. While this limits the path availability bound which can be guaranteed, the simulation results show that it does not e ect cluster stability. Figure-6(a) and (b) show the e ects of mobility on mean cluster size. The results show the adaptive property of the ( ; t)?Cluster algorithm, and, also, the signi cant effect due to the nodes' e ective transmission range. It is worthwhile to point out that it is unlikely that very low range transmitters could e ectively be used in ad-hoc networks with nodes moving at high rates of speed, unless the nodes are moving together. These results demonstrate a desirable feature of the ( ; t)?Cluster protocol, namely, that it adapts cluster size to node mobility. Speci cally, it maintains larger clusters under lower mobility to bene t from more optimal routing, while reducing cluster size in response to greater mobility. Figure-6(c) and (d) show the e ects of mobility on the probability that a node is clustered. The results demonstrate a desirable property of the ( ; t)?Cluster protocol, namely, that nodes still remain clustered with high probability even at high rates of mobility. It is interesting to observe the e ects of the system parameters on this metric. Speci cally, for the case of Req = 1 km, and the value of t = 1 minute, nodes remain clustered with probability :90 even at the highest mobility rates. However, if the ( ; t)-criteria demands ( ; t)?paths over a 5 minute interval, then the node's ability to achieve clustering collapses above 20 kph. For the case of Req = :5 km, a similar e ect is observed for variations in . Lower values of permit nodes to cluster more easily, although, referring to Figure6(b), the clusters are signi cantly smaller. Figures-6(e) through (h) demonstrate additional stability properties of the ( ; t)?Cluster . Residence time is de ned as the time a node remains resident in a given cluster. Longer residence times are desirable, although taken in conjunction with the probability of being clustered, smaller residence times can still be acceptable in terms of system performance. This is true because the overhead of clustering in the ( ; t)?Cluster strategy is minimal. The enormous jump in residence time at 25 kph observed in Figure6(e) is due to the very low probability of a node actually being clustered at that rate; therefore, the number represents a very small portion of the nodes in the network. Had the simulation included pause-times, it is likely that cluster residence times would increase substantially. Cluster survival time was measured by taking, at each sampling instant, the amount of elapsed time each currently active cluster had existed. Thus, it represents a measure of cluster lifetime. A stable cluster topology should have relatively long cluster lifetimes. The link failure rates

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999

17

Cluster Size vs. Mobility Rate 25

6

Cluster Size vs. Mobility Rate 1

Probability of Being Custered vs. Mobility Rate

20 Mean Cluster Size (number?of?nodes)

Mean Cluster Size (number?of?nodes)

15

4

Probability Node is in a Cluster

t = 1 min + t = 5 min

5.5

5

4.5

= 0:4 + = 0:2

0.9

0.8

0.7

0.6

Sfrag replacements

= 0:4 + = 0:2

10

PSfrag replacements

t = 1 min + t = 5 min

20 25

3.5

3

PSfrag replacements

= 0:4 + = 0:2

20 25

0.5

0.4

t = 1 min + t = 5 min

2.5

0.3

5

2

0.2

1.5

0.1

0

0

5

10 15 Mean Mobile Node Speed (kph)

1

0

5

10 15 Mean Mobile Node Speed (kph)

0

0

5

10 15 Mean Mobile Node Speed (kph)

20

25

(a) Cluster Size (Req = 1000m)

Probability of Being Custered vs. Mobility Rate 1

(b) Cluster Size (Req = 500m)

Node Residence Time vs. Mobility 20 12

(c) Cluster Prob. (Req = 1000m)

Node Residence Time vs. Mobility

18

0.9

10 16

Node Residence in Cluster (min)

Node Residence in Cluster (min)

Probability Node is in a Cluster

14

= 0:4 + = 0:2

0.8

12

Sfrag replacements

0.7

t = 1 min + t = 5 min

0.6

= 0:4 + = 0:2

0 5

PSfrag replacements

= 0:4 + = 0:2

20 25

10

8

t = 1 min + t = 5 min PSfrag replacements t = 1 min + t = 5 min

20 25

8

6

4

6

4

0.5

2

2

0.4

10 15 Mean Mobile Node Speed (kph)

0

0

5

10 15 Mean Mobile Node Speed (kph)

0

0

5

10 15 Mean Mobile Node Speed (kph)

20

25

(d) Cluster Prob. (Req = 500m)

Cluster Age vs. Mobility 90

(e) Residence Time (Req = 1000m)

Cluster Age vs. Mobility 45

(f) Residence Time (Req = 500m)

Rcv. Message Rate vs. Mobility 0.22

80

Node Received Message Rate (msg?per?sec/per?node)

t = 1 min + t = 5 min

Cluster Age (min)

40

= 0:4 + = 0:2

0.2

70

35

0.18

60 Cluster Age (min)

30

0.16

0.14

Sfrag replacements

= 0:4 + = 0:2

50

40

PSfrag replacements

t = 1 min + t = 5 min

20 25

25

20

PSfrag replacements

= 0:4 + = 0:2

20 25

0.12

0.1

30

15

0.08

20

10

t = 1 min + t = 5 min

0 5 10 15 Mean Mobile Node Speed (kph) 20 25

0.06

10

5

0.04

0

0

5

10 15 Mean Mobile Node Speed (kph)

0

0

5

10 15 Mean Mobile Node Speed (kph)

0.02

(g) Cluster Survival (Req = 1000m)

(h) Cluster Survival (Req = 500m)

(i) Message Rate (Req = 1000m)

Figure 8: Simulation Results. that were observed in these simulations range from less than 1 failure-per-second at the lower mobility, to upwards of 2 to 3 failures-per-second at the higher rates. Similar rates were observed for link activations. Given the high rates of link failure that were observed, the cluster survival times shown in Figure-6(g) and (h) are reasonable. Finally, the rate of control messages processed per-node, as depicted in Figure-6(i) for Req = 1 km (Similar results were seen for Req = :5 km), provides a measure of the e ciency of the ( ; t)?Cluster algorithm. This was measured by counting the number of routing updates, including those required to join and leave clusters, that were processed by each node every second. It is interesting to observe that the algorithm essentially protects the nodes from the effects of topology changes as node mobility increases. The shape of the curve can be explained as follows: The initial increase in the received message rate is due to the substantial increase in topology changes. Although the cluster size is diminished, it is more than compensated for by the increased rate of node clustering activity and topology changes. Finally, the algorithm's adaptive property drives the message rate down by reducing the cluster size signi cantly as mobility increases beyond 10 kph. In this section a simulation model was developed in order to show the e ectiveness of the ( ; t)?Cluster strategy in terms of its inherent properties, namely, adaptiveness to

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999 node mobility, cluster stability, and protocol e ciency. The results demonstrate the scheme performs well and is well adapted to meet its stated objectives in the environments for which it has been designed to operate.

18

7 Conclusions

The ( ; t)?Cluster framework de nes a strategy for adaptively organizing ad-hoc networks into clusters in which the probability of path availability between nodes is bounded over time. The purpose of this dynamic arrangement is to support an adaptive hybrid approach to routing that is e cient under all conditions, yet can achieve more optimal routing when mobility patterns favor it. The concept of the ( ; t)-path was introduced and analytical models were developed that show how these paths can be evaluated. The ( ; t)-criteria was de ned which speci es the conditions required for the management of ( ; t)?Clusters. Finally, an algorithm was described which e ciently maintains the cluster topology with very little additional processing or inter-nodal coordination. Simulation results show the inherent adaptive properties and stability of the ( ; t)?Cluster protocol. Based upon the proposed routing methodology it was argued that existing reactive routing strategies provide a lower bound on the tra c-level performance of the ( ; t)?Cluster strategy and that in most cases the performance will be improved. Future work includes detailed analysis of tra c-level performance, and adaptation of admission and connection control algorithms to support probabilistic QoS guarantees using the ( ; t)?Cluster framework.

Acknowledgment

The authors wish to thank Dr. Robert J. Sclabassi of the Departments of Electrical Engineering and Neurosurgery at the University of Pittsburgh for his support and continuing guidance in the completion of this work. They also wish to thank Mark Stover of Siemens ICN, the anonymous referees and editors for their valuable comments that greatly improved the content and readability of this paper.

References

1] A. Ephremides, J. E. Wieselthier and D. Baker. A design concept for reliable mobile radio networks with frequency hopping signaling. Proc IEEE, 75(1), 1987. 2] A. Alwan, R. Bagrodia, N. Bambos, M. Gerla, L. Kleinrock, J. Short, and J. Villasenor. Adaptive mobile multimedia networks. IEEE Personal Communications Magazine, 3(2), April 1996. 3] Petr Beckmann. Probability in Communication Engineering. Harcourt, Brace & World, Inc., New York, 1967. 4] J. Broch, D. Maltz, D. Johnson, Y. Hu, and J. Jetcheva. A performance comparison of multi-hop wireless ad hoc routing protocols. In Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking, October 1998. 5] C. Barnhart and J. E. Wieselthier and A. Ephremides. Admission-Control policies for multihop wireless networks. Wireless Networks, 1(4), 1995.

6] M. S. Corson, S. Papademetriou, P. Papadopoulos, V. Park, and A. Qayyum. An internet MANET encapsulation protocol (IMEP) speci cation. Internet Draft, August 1998. 7] M. Scott Corson and Anthony Ephremides. A distributed routing algorithm for mobile wireless networks. Wireless Networks, (1995)(1):61{81, 1995. 8] S. Das, R. Castaneda, J. Yan, and R. Sengupta. Comparative performance evaluation of routing protocols for mobile, ad hoc networks. In Proceedings of 7th Annual ICCCN, October 1998. 9] J. J. Garcia-Lunes-Aceves and Jochen Behrens. Distributed, scalable routing based on vectors of link states. IEEE Journal on Selected Areas in Communications, 13(8):1383{1395, October 1995. 10] M. Gerla and J. T. Tsai. Multicluster, mobile, multimedia radio network. Wireless Networks, 1, October 1995. 11] Z. J. Haas and M. Perlman. The performance of query control schemes for the zone routing protocol. In Proceedings of ACM Sigcomm'98, October 1998. 12] Z. J. Haas. "Panel report on ad hoc networks". Mobile Computing and Communications Review, 2(1), 1997. 13] Z. J. Haas and M. Pearlman. The zone routing protocol (ZRP) for ad hoc networks. Technical report, Internet Draft, November 1997. 14] D. Hong and S. Rappaport. Tra c models and performance analysis for cellular mobile radio telephone systems with prioritized and nonprioritized hando procedures. IEEE Transactions on Vehicular Technology, 35(3), August 1986. 15] D. Johnson and D. Maltz. Dynamic source routing in ad hoc wireless networks. In T. Imielinski and eds. H. Korth, editors, Mobile Computing. Kluwer Academic Publi, 1996. 16] J. Jubin and J.D. Tornow. The DARPA packet radio network protocols. Proc. IEEE, 75(1), 1987. 17] F. Kamoun and L. Kleinrock. Hierarchical routing for large networks: performance evaluation and optimization. Computer Networks, (1977)(1):155{174, 1977. 18] F. Kamoun and L. Kleinrock. Stochastic performance evaluation of hierarchical routing for large networks. Computer Networks, (1979)(3):337{353, 1979. 19] L. Kleinrock. Queueing Systems Volume 1: Theory. John Wiley and Sons, New York, 1975. 20] G. Lauer. Packet-radio routing. ed. M. Steenstrup (PrenticeHall, Englewood Cli s, N.J.), 1995. 21] C. R. Lin and M. Gerla. Adaptive clustering for mobile wireless networks. IEEE Journal on Selected Areas in Communications, 15(7), September 1997. 22] A. B. McDonald and T. Znati. Link availability models for mobile ad-hoc networks. Tech-Report 99-07, Computer Science Department, University of Pittsburgh, 1999. 23] A. B. McDonald and T. Znati. Performance Evaluation Of Neighbor Greeting Procotols: ARP Versus ES-IS. The Computer Journal, Volume 39, Number 10, 1996. 24] Shree Murthy and J. J. Garcia-Lunes-Aceves. An e cient routing protocol for wireless networks. ACM Balzer Mobile Networks and Applications Journal, Special Issue on Routing in Mobile Communications Networks, 1996. 25] N. H. Vaidya P. Krishna, M. Chatterjee and D. K. Pradhan. A cluster-based approach for routing in dynamic networks. ACM Computer Communications Review, 27(2), April 1997. 26] V. Park and S. Corson. Temporally-ordered routing algorithm (TORA) version 1. Internet Draft, August 1998. 27] V. D. Park and M. S. Corson. A highly adaptive distributed routing algorithm for mobile wireless networks. In IEEE Infocom, April 1997. 28] C. Perkins and E. Royer. Ad hoc on demand distance vector (AODV) routing. Internet Draft, November 1998. 29] C. R. Perkins and P. Bhagwat. Highly dynamic destination sequenced distance vector routing (DSDV) for mobile computers. In ACM SIGCOMM, pages 234{244, October 1994. 30] Radia Perlman. Fault-tolerant broadcast of routing information. Computer Networks, (1983)(7):395{405, 1983. 31] R. Ramanathan and M. Steenstrup. Hierarchically-organized, multihop mobile wireless networks for quality-of-service support. Mobile Networks and Applications, 3, 1998. 32] M. Zonoozi and P. Dassanayake. User Mobility modeling and characterization of mobility patterns. IEEE Journal on Selected Areas in Communications, 15(7), September 1997.

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999

19

A Appendix

This probability can be evaluated using the result of Corollary-5.1 and the distribution of Z by conditioning on This appendix presents proofs of Theorems 5.1 and 5.2 Z = z . The integral is evaluated by expanding the coe which characterize the link availability between two mo- cients of the exponential and integrating term-by-term. In 2 bile nodes. Refer to Subsection 5.2 for statements of the what follows, let a = 1=2; b = 2; z = (?4Req )=( m;n ) and theorems. (a)k ; (b)k are Pochhammer symbols: (a)k = a(a + 1)(a + 2) : : : (a + k ? 1). m;n is de ned in Equation-8.

A.1 Proof of Theorem 5.1

The analysis in 14] presents the derivation of the the distance, Z , a mobile node must travel before reaching the boundary of a cell when the mobile moves in a random uniform direction over (0; 2 ). If the cell has an e ective radius of Req , and the mobile is initially located anywhere within the cell with equal probability, then the pdf of the distribution of this distance is: 2 q 2 fZ (z ) = R2 Req ? (z=2)2 eq 0 z 2Req

Pr(Rm;n (t) < Z ) Z1 = Pr(Rm;n (t) < Z jZ = z )fZ (z )dz

= =

m Req

0

m;n

2

n PSfrag replacements

Rm;n (t)

Z

(12) = 1 ? (1 + a z + b(b + 1)2! + ((a)k z ! ) b k=3 b)k k The expression in Equation-12 is the Hypergeometric Series, which is the series expansion for the Con uent Hypergeometric function: (a; b; z ).

2 2 2 Req Req ? (z=2) ( i=0 (?1) i! im;n )dz R2 R4 5R6 = 1 ? (1 ? eq + 2eq ? 6 3eq + : : :) 0

= 1?

Z?1 1 Pr(Rm;n (t) < z )fZ (z )dz ?1 Z 2Req 2 2 q 2 (1 ? exp( ?z )) R2 Req ? (z=2)2dz m;n 0 eq Z 2Req 2 q 1 X i z2i

m;n

a(a + 1)z 2

m;n

m;n

1 X

k

QED

A.2 Proof of Theorem 5.2

Node Activation Case

Figure 9: Node Activation Model. According to the analysis in Subsection 5.1 of this paper, the joint mobility problem can be transformed into a single node mobility problem. Assume that node n is located at the center of a circular region of radius Req , and that node m is located within a uniform random distance 0 C Req along a uniform random trajectory angle over (0; 2 ). The equivalent direction of m is uniform over (0; 2 ), and the distance, Rm;n (t), moved in time t is approximately Raleigh distributed. In the node activation case, m is assumed to activate at time t0 anywhere within a distance of Req from n with equal probability. Figure-9 illustrates the relationship among these variables. Consequently, the probability that m is still within a distance of Req at time t is the probability that the equivalent distance it travels in that time is less than the distance to the boundary of the approximating circle given by the distribution of Z . This probability is equivalent to the link availability as expressed in De nition-5.5:

The analysis in 14] presents the derivation of the the distance, Z , a mobile node entering a cell must travel before reaching the boundary of the cell when the mobile moves in a random uniform direction. Re ecting the assumption that the mobile is entering the cell, the direction of Z is random uniformly distributed over (0; ). The value for Z along any other trajectory must be 0 since the mobile would never enter the cell. Consequently, the pdf of the distribution of Z is conditional with respect to 0 m;n and is given by:

fZ j0

m;n

(z ) = 1 q

2 Req ? (z=2)2

1

0 z 2Req

Am;n (t) Pr(Rm;n (t) < Z )

In transforming the joint node mobility problem into a single node, xed reference mobility problem, node m moves in an equivalent direction which is uniform over (0; 2 ), and node n remains in a xed position. Over an interval of length t, the distance, Rm;n (t), moved by node m relative to node n is approximately Raleigh distributed. Figure-10 illustrates the relationship among Req ; Z; Rm;n (t) and m;n . Proceeding in the same manner as in the derivation of (11) Theorem-5.1, the link availability is determined according

Appears in IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999

20

0

m;n 2

Z

Rm;n (t)

m Req

n PSfrag replacements

Link Activation Case

B.S. degree in Electrical Engineering from Northwestern University in 1986, and the M.S. degree in Telecommunications from the University of Pittsburgh in 1994. He is currently working toward the Ph.D. degree at the University of Pittsburgh. His research interests are in routing algorithms, ad-hoc networks, mobility management, communications protocols, and distributed systems. He has worked in industry as both a Systems and Network Engineer, and is currently a Sr. Computer Engineer in the Dept. of Neurophysiology at Children's Hospital of Pittsburgh. Prior to his current position he completed an Internship in the Applied Network Research Group at Bellcore in Redbank, New Jersey. His email address is: tudball@neuronet.pitt.edu.

A. Bruce McDonald (S '94) received the

Figure 10: Link Activation Model. to Equation-11. However, the direction of node m is uniform over (0; 2 ); whereas, the direction of Z is uniform over (0; ). Consequently, conditional probability must be used to solve the link availability problem as follows:

Pr(Rm;n (t) < Z ) = Pr(Rm;n (t) < Z j0 Pr(Rm;n (t) < Z j

m;n m;n

)Pr(0 2 )Pr(

(13) )+ m;n m;n 2 )

The conditional distribution of Rm;n (t) for 0 m;n can be determined as follows, where m;n is de ned in Equation-8:

Pr(Rm;n (t) < Z j0 m;n ) Z1 Pr(Rm;n (t) < Z jZ = z )fZ j0 =

= =

Taieb F. Znati (A' 91) obtained a Ph.D. Degree in Computer Science at Michigan State University, East Lansing, in April 1988, and a Master of Science Degree at Purdue University, West Lafayette, Indiana. In 1988, he joined the University of Pittsburgh where he currently holds an associate professor position in the Department of Computer Science with a joint appointment in Telecommunications in the Department of Information Science and a joint appointment in Computer Engeneering. His current research interests focus on the design of network protocols for wired and wireless communication networks to support multimedia applications' QoS requirements, the design and analysis of medium access control protocols to support distributed real-time systems, and the investigation of fundamental design issues related to distributed systems. He served as the general chair of CNDS'99 and the 32nd Annual Simulation Sysmposium and as a program chair of numerous conferences and workshops in networking and distributed multimedia systems. He is also member of the Editorial Board of the International Journal of Parallel and Distributed Systems and Networks. His email address: znati@cs.pitt.edu.

Z?1 1

?1

m;n

(z )dz

Z 2Req 1 (1 ? exp( ?m;n )) z2 q2 dz 2 0

Req ? (z=2) 2 2 ?2Req ?2Req

m;n

Pr(Rm;n (t) < z )fZ j0

m;n

(z )dz

= 1 ? I0 (

) exp(

m;n

)

(14)

The distribution of node m's trajectory is uniform over (0; 2 ). Consequently, the probability that the trajectory is in the range (0; ) is exactly 0:5. Furthermore, since the value of Z over ( ; 2 ) is 0, the conditional probability, Pr(Rm;n (t) < Z j m;n 2 ), is equal to 0. Based on these observations, Equation-13 reduces to the following expression which, combined with Equation-14, yields the nal result which, according to Equation-11 is the link availability: 1 Pr(Rm;n (t) < Z ) = 2 Pr(Rm;n (t) < Z j0

m;n

)

QED

- A mobility based metric for clustering in mobile ad hoc networks
- Distributed and mobility-adaptive clustering for ad hoc networks
- Mobility Framework for Ad Hoc Wireless Networks
- Mobility-based d-Hop Clustering Algorithm for Mobile Ad Hoc Networks
- Independent Zone Routing An Adaptive Hybrid Routing Framework for Ad Hoc Wireless Networks
- Cluster-Based Framework in Vehicular Ad-Hoc networks
- A General Framework for the Capacity Analysis of Wireless Ad Hoc Networks
- CLTC A Cluster-Based Topology Control Framework for Ad Hoc Networks
- A MAC Layer Protocol for Priority-based Reliable Broadcast in Wireless Ad Hoc Networks
- Mobility-Adaptive Protocols for Managing Large Ad Hoc Networks
- Group Mobility and Partition Prediction in Wireless Ad-Hoc Networks
- Energy Conserving Routing in Wireless Ad-hoc Networks
- An application-specific protocol architecture for wireless microsensor networks
- Mobility Framework for Ad Hoc Wireless Networks
- Dynamic source routing in ad hoc wireless networks

更多相关文章：
*ad-hoc* 网络

4)个人通信:个人局域网 (PAN, P ersonal Area*Network* )是 *Ad Hoc* 网络技术...( Multip le Access with Collision Avoidanc e) MACAW( MACA *for* *Wireless*) ...*Ad hoc*网络

*Ad hoc*网络_信息与通信_工程科技_专业资料。摘要 ...自适 应网络(SURAN,SURvivable *Adaptive* *Network*)项目...因此它也被称为多跳无线 网(MultiHop *Wireless* ...**移动***Ad Hoc*网络研究与发展现状

这项工作开辟了移动自组网(Mobile*Ad Hoc* *Network*,简称 *Ad Hoc* 网络或 MANET)...(*Wireless* *Adaptive* *Mobility*) ( Lab,http://www.cs.ucla.edu/NRL/*wireless*/...**浅谈***Ad Hoc*网络的应用

浅谈*Ad Hoc*网络的应用_计算机硬件及网络_IT/计算机_专业资料。关于计算机的论文 ...(survivable *adaptive* *network*) 项目,研究如何将 PRNET 的研究成果加以扩展,以...*Ad Hoc*网络路由协议的研究

关键词:无线自组网,*Ad Hoc*网络,路由协议 Abstract:*Wireless* *Ad Hoc* *networks* ...*network* topology, the routing protocols such as RIP, OSPF etc used *in* ...**陈远筑博士简历**

*Clustering* Algorithms *for* *Ad Hoc* *Wireless* *Networks*,...*A* Hierarchical Energy-Efficient *Framework* *for* Data ...WiMAX *Network* Planning Using *Adaptive*-Population-...*Ad Hoc*网络路由协议的比较

*network* is *a* *wireless* *mobile* communication *network* made of *a* group of ...These characters of *Ad Hoc* *networks* make routing protocol *based* on ...**开题报告(基于区域划分的LEACH算法研究)**

distributed*clustering* approach *for* *ad hoc* sensor ...coverage problem *in* *a* *wireless* sensor *network* [*A*...IEEE Computer Society 2002 *in* *Cluster*-*Based* [14]...**基于OMNeT的***Ad*+*hoc*网络仿真

( MF,*Mobility* *Framework* )组成原理进行了系统的讲解...*Ad hoc* *network* *for* the simulation test *based* on...*wireless* and mobile *network* simulation, and free ...**基于Dijkstra算法的***Ad Hoc*网络的动态仿真优化

关键词:*Ad Hoc* 网络;Dijkstra 最短路径算法;MTLAB 的仿真测量 I Abstract *In* recent years, *mobile* *Ad Hoc* *networks* as emerging - *wireless* communication *network*... 更多相关标签：

4)个人通信:个人局域网 (PAN, P ersonal Area

这项工作开辟了移动自组网(Mobile

浅谈

关键词:无线自组网,

distributed

( MF,

关键词: