ABSTRACT Title of Document: SELF-ORGANIZING DIRECTIONAL WIRELESS BACKBONE NETWORKS Jaime Llorca, Doctor of Philosophy, 2008 Directed By: Professor Christopher C. Davis, Department of Electrical and Computer Engineering Directional wireless communications is emerging as a viable, cost-effective technology for rapidly deployable broadband wireless communication infrastructures. This technology provides extremely high data rates through the use of narrow-beam free space optical (FSO) and/or radio-frequency (RF) point-to-point links. The use of directional wireless communications to form flexible backbone networks, which provide broadband connectivity to capacity-limited wireless networks or hosts, promises to circumvent the scalability limitations of traditional wireless networks. The main challenge in the design of directional wireless backbone (DWB) networks is to assure robustness and survivability in a dynamic wireless environment. DWB networks must assure highly available broadband connectivity and be able to regain connectivity in the face of loss or degradation. This dissertation considers the use of topology control to provide assured connectivity in dynamic environments. Topology control is defined as the autonomous network capability to dynamically reconfigure its physical topology. In the case of DWB networks, the physical topology can be reconfigured through 1) redirection of point-to-point links and/or 2) reposition of backbone nodes. Coverage and connectivity are presented as the two most important issues in DWB-based networks. The aim of this dissertation is to provide initial designs for scalable self-organized DWB networks, which could autonomously adapt their physical topology to maximize coverage to terminals or hosts while maintaining robust backbone connectivity. This dissertation provides a novel approach to the topology control problem by modeling communication networks as physical systems where network robustness is characterized in terms of the system?s potential energy. In our model, communication links define physical interactions between network nodes. Topology control mechanisms are designed to mimic physical systems? natural reaction to external excitations which drive the network topology to energy minimizing configurations based on local forces exerted on network nodes. The potential energy of a communications network is defined as the total communications energy usage for a given target performance. Accurate link physics models that take into account the variation of the wireless channel due to atmospheric attenuation, turbulence-induced fading, node mobility, and different antenna patterns have been developed in order to characterize the behavior of the potential energy stored at each wireless link in the network. The net force at each backbone node is computed as the negative gradient of the potential energy function at the node?s location. Mobility control algorithms are designed to reposition backbone nodes in the direction of the net force. The algorithms developed are completely distributed, show constant time complexity and produce optimal solutions from local interactions, thus proving the system?s self- organizing capability. This dissertation provides: 1) An improved understanding of the physical nature of next generation wireless networks; 2) Applicability and feasibility studies of topology control for performance improvement in dynamic wireless networks; and 3) Initial designs for self-organizing DWB networks through topology control. SELF-ORGANIZING DIRECTIONAL WIRELESS BACKBONE NETWORKS By Jaime Llorca Dissertation submitted to the Faculty of the Graduate School of the University of Maryland, College Park, in partial fulfillment of the requirements for the degree of Doctor of Philosophy 2008 Advisory Committee: Professor Christopher C. Davis, Chair Professor Mark Shayman Professor Gregory B. Baecher Associate Professor Tomas E. Murphy Faculty Research Professor Stuart D. Milner Faculty Research Professor Mehdi Kalantari Kandani ? Copyright by Jaime Llorca 2008 ii Dedication To my family for their unconditional love and support iii Acknowledgements I gratefully thank my advisor and co-advisor, Professor Christopher C. Davis and Dr Stuart D. Milner, for their continuous guidance, friendship, and support throughout my graduate studies at the University of Maryland. I also want to thank the members of the dissertation committee for their time and service. I want to thank Professor Uzi Vishkin, Professor Steven Gabriel and Dr Mehdi Kalantari for our helpful technical discussions and fruitful collaborations. I am thankful to all of my colleagues in the Maryland Optics Group and the Center for Infrastructure Sensors at the University of Maryland for the valuable discussions we have held and assistance we have exchanged throughout my years of graduate study at the University of Maryland. I am particularly thankful to Aniket Desai, Shawn Ho, Sugianto Trisno, Eswaran Baskaran, Yohan Shim, Ruud Egging, Heba Yuksel and Clint Edwards for the technical and non-technical discussions we continuously held. Finally, I want to thank my family and friends. I can not thank enough my parents, Federico Llorca and Clemencia Sanz, my sister, Raquel Llorca, and my brother Mario Llorca, for their continuous love, patience, and support throughout my entire educational path. I truly appreciate my parents? devotion in helping me to always enjoy, progress and succeed, and providing all of the necessary support, even when being so far apart during most of my graduate studies. I would also like to thank my unconditional friends Antonio Trias and Jesus Bengoechea, who have become my iv family away from home, being with me throughout my entire stay at the University of Maryland. I really appreciate the unforgettable time we have spent together, their friendship, love and support. I could not have done it without them. v Table of Contents Dedication..................................................................................................................... ii Acknowledgements......................................................................................................iii Table of Contents.......................................................................................................... v List of Tables .............................................................................................................. vii List of Figures............................................................................................................viii Chapter 1: Introduction................................................................................................. 1 1.1 Motivation..................................................................................................... 1 1.1.1 Ubiquitous broadband connectivity ...................................................... 1 1.1.2 Directional wireless backbone (DWB) networks ................................. 3 1.1.3 Self-organization................................................................................... 6 1.2 Dissertation Contributions ............................................................................ 9 1.3 Organization................................................................................................ 11 Chapter 2: Topology Control...................................................................................... 13 2.1 Introduction and background ...................................................................... 13 2.2 Topology control in DWB networks........................................................... 17 2.3 Coverage and connectivity.......................................................................... 20 Chapter 3: A Physics-based approach to topology control in dynamic wireless networks...................................................................................................................... 22 3.1 Introduction................................................................................................. 22 3.2 Network robustness and potential energy................................................... 23 3.3 Problem statement....................................................................................... 26 Chapter 4: Physical layer characterization.................................................................. 29 4.1 Introduction and background ...................................................................... 29 4.2 Communication cost model ........................................................................ 35 4.3 Turbulence induced fading ......................................................................... 37 4.4 Path loss ...................................................................................................... 42 4.4.1 Free space path loss ................................................................................... 42 4.4.2 Atmospheric attenuation ............................................................................ 47 4.5 Dynamic network model............................................................................. 51 Chapter 5: Topology Reconfiguration ........................................................................ 55 5.1 Introduction................................................................................................. 55 5.2 Topology Optimization............................................................................... 56 5.2.1 Introduction................................................................................................ 56 5.2.1 Problem Statement..................................................................................... 58 5.2.2 Heuristics for ring networks....................................................................... 60 5.2.3 Heuristics for 3-degree networks............................................................... 68 5.3 Bootstrapping.............................................................................................. 73 Chapter 6: Mobility Control........................................................................................ 77 6.1 Introduction................................................................................................. 77 6.2 Potential energy minimization .................................................................... 79 vi 6.3 Coverage and connectivity optimization .................................................... 81 6.4 Force-driven mobility control..................................................................... 85 6.4.1 Communication-defined forces.................................................................. 85 6.4.2 Force-driven optimization algorithm ......................................................... 91 6.5 Spring System ............................................................................................. 95 6.5.1 Quadratic optimization............................................................................... 95 6.5.2 SPRING algorithm..................................................................................... 98 6.5.3 Simulation results..................................................................................... 100 6.6 Mobility control under atmospheric obscuration...................................... 124 6.6.1 Convex optimization................................................................................ 125 6.6.2 FORCE algorithm .................................................................................... 127 6.6.3 Simulation results..................................................................................... 129 6.7 Power constraints............................................................................................ 149 6.7.1 Exponential constraint force .................................................................... 149 6.7.2 Simulation results..................................................................................... 151 Chapter 7: Conclusions............................................................................................. 153 Bibliography ............................................................................................................. 157 vii List of Tables Table 4.1: Typical cloud attenuation values at different atmospheric layers??...57 Table 6.1: Average percentage improvement in total average power usage using the SPRING mobility control algorithm versus using the AVG algorithm and versus no mobility control, for networks with 10 and 20 backbone nodes???????.120 Table 6.2: Atmospheric attenuation pattern. Average attenuation coefficient (?) in km-1 for the backbone FSO links, for each minute of a 20 min scenario................143 Table 6.3: Average percentage improvement in total average power usage using the FORCE mobility control algorithm versus using the SPRING algorithm and versus using the AVG algorithm, for networks with 10 and 20 backbone nodes???..145 Table 6.4: Average percentage improvement in SD connections using the additional constraint force for networks using the FORCE mobility control algorithm with maximum transmitted power of 5W, 10W and 15W???????????..149 viii List of Figures Figure 1.1: Backbone-based wireless network architecture?..????????..11 Figure 1.2: Rapidly deployable, flexible broadband communications using directional wireless technologies??????????????...?????????..109 Figure 2.1: Power control in ad-hoc wireless networks???????????..21 Figure 4.1: BER of an FSO system at different intensity variance values????..40 Figure 4.2: Wireless link model parameters????????????????44 Figure 4.3: Weak and Strong Variances compared with the Rytov value [18]. Circles shown represent the path of a composite curve that is predicted to be valid over all turbulence strengths?????????????????????????.46 Figure 4.4: Rytov variance versus propagating distance (1310nm beam) for different Cn2 values?????????????????????????????47 Figure 4.5: Directional wireless beam illustration?????????????..51 Figure 4.6: Spring model for wireless links????????????????.54 Figure 4.7: Illustration of the path loss model for a directional wireless link going through atmospheric obscuration????????????????????.58 Figure 4.8: Snapshot of a dynamic 3-dimensional scenario with cloud layers at different altitudes and a 10 node directional wireless network using FSO and directional RF communication technologies..???????????????.60 Figure 4.9: Modeling the network?s communication cost. The atmospheric conditions of the 3D space determine the 3D obscuration matrix ? and the 3D turbulence strength matrix Cn2. Given the location of the network nodes, the NxN path loss matrix L and the NxN link margin matrix PR0 are obtained from the 3D matrices ? and Cn2 respectively. Finally, the potential energy matrix U, which contains the power needed at every potential link in the network is obtained using Eq. 4.28 as the aggregation of L and PR0??..???????????????????????????61 Figure 5.1: The topology reconfiguration process.?????????????..62 Figure 5.2: Autonomous reconfiguration processes?????????????64 ix Figure 5.3: Performance of SR and RSR heuristics (20 nodes)????????..73 Figure 5.4: Average running time of SR and RSR heuristics in ?s (8-60 nodes).?..73 Figure 5.5: Average cost reduction with successive Branch Exchange iterations?..75 Figure 5.6: Histogram of the optimality gap for RSR+BE heuristic...??????76 Figure 5.7: Performance comparison of 3-degree heuristics (20 nodes)?????.81 Figure 5.8: Average running time of 3-degree heuristics (8-60 nodes)?????...81 Figure 5.9: Average total delay of the bootstrapping process?????????.85 Figure 6.1: Trade-off between network coverage and backbone connectivity???76 Figure 6.2: Force-driven mobility control algorithm????????????...91 Figure 6.3: Initial non-optimal configuration (a) and optimal network configurations (b, c, d, e) after running the SPRING mobility control algorithm for different values of ? (10 backbone nodes)??????????????????????100 Figure 6.4: Initial non-optimal configuration (a) and optimal network configurations (b, c, d, e) after running the SPRING mobility control algorithm for different values of ? (20 backbone nodes)??????????????????????101 Figure 6.5: Pareto Optimal set of solutions (10 and 20 backbone nodes)????103 Figure 6.6: Network evolution from initial placement to equilibrium for a fixed terminal nodes? position scenario???????????????????.106 Figure 6.7: Network evolution with terminal clusters moving according to the RPGM model and backbone reacting using the SPRING algorithm?????????118 Figure 6.8: Network evolution with terminal clusters moving according to the RPGM model and backbone reacting using the FORCE algorithm?????????..142 1 Chapter 1: Introduction 1.1 Motivation 1.1.1 Ubiquitous broadband connectivity Directional wireless communications is emerging as a viable, cost-effective technology for rapidly deployable broadband wireless communication infrastructures [1-3]. This technology provides extremely high data rates, as compared to traditional wireless networks, through the use of narrow-beam free-space optical (FSO) and/or radio-frequency (RF) links, which can transmit large amounts of information point- to-point without causing interference [1-3]. In this dissertation, directional wireless communications is presented as a promising technology for the flexible deployment of broadband wireless backbone networks. The internet2 and other optical fiber backbone networks provide very high capacity through the guided transmission of laser beams. The physical topology underlying the fiber infrastructure constitutes a fixed and robust mesh, but its deployment is costly and time-consuming. Hosts within reach of the fiber backbone can have broadband connectivity that allows access to next generation multimedia services. The main problem is that a lot of actual and potential users are not likely to be within reach of the fiber backbone. Indeed, it has been estimated that over 90% of U.S. businesses fall less than a mile short of a fiber backbone [2]. Also, broadband 2 connectivity might be required in remote areas or difficult-to-reach locations. Yet the extension of fiber connectivity to everywhere seems unlikely in the near future. Moreover, as a fixed wired infrastructure, dynamic changes in traffic demands, host mobility, etc, are very hard to handle. The physical topology cannot be dynamically reconfigured and only routing can try to solve problems such as traffic congestion. Thus, ubiquitous broadband connectivity needs flexible extensions to the fiber backbone. Wireless communication technologies, on the other hand, provide connectivity to mobile hosts and/or hosts away from the fiber backbone. Ad-hoc wireless networks are infrastructure-less. Nodes are both hosts and routers and connect to each other in an ad-hoc manner. The physical topology is flexible allowing for node mobility and reconfiguration, but the interference caused by omnidirectional RF transmissions makes these networks not scalable. Gupta and Kumar showed that the throughput capacity of homogeneous wireless networks decreases with the square root of the number of nodes [4]. In cellular telephony or other base-station oriented wireless networks, hosts are organized in limited size clusters and each cluster is assigned a base-station or access point [4]. In this type of architecture, the very devices that provide wireless service to hosts/clients need lots of wiring themselves to connect to private networks and the Internet. This wiring is expensive to install and change, and deployment must be carefully planned and timed to minimize disruption to normal business operations. There is a need for flexible broadband infrastructures that could bridge the gap between capacity-limited wireless networks and fixed high capacity backbone 3 networks. Directional wireless communications combines the high capacity features of point-to-point interference-free communication systems (such as optical fiber networks) with the flexibility of wireless networks. 1.1.2 Directional wireless backbone (DWB) networks In this dissertation, a novel backbone-based wireless network architecture is presented [5]. The concept is similar to the one adopted in base-station oriented networks, but the advantages of directional wireless communications are used to link together the base-station nodes and form a flexible high capacity network at the backbone layer. Fig. 1.1 illustrates this two-tiered architecture. The lower tier consists of clusters of flat ad-hoc networks based on standard diffused RF technology. The higher tier constitutes a mesh backbone network consisting of a set of base station nodes connected using directional wireless technologies. The advantages of directional wireless communications can be very well exploited at the backbone layer, where line of sight constraints are less restrictive, high data rate is a requirement and interference-free point-to-point communications is extremely attractive to provide a scalable broadband wireless mesh backbone. The interface between both layers is achieved by allowing the backbone nodes the capability of an omnidirectional RF antenna. This way, backbone nodes can give coverage to terminal nodes at the host layer through omnidirectional RF (as is the case of cellular base stations) and make use of directional wireless communications to route aggregated traffic from covered users, over the backbone, with very high data rates and without causing interference. Just like having fiber in the sky! 4 Figure 1.1: Backbone-based wireless network architecture. The ability to rapidly deploy a broadband backbone to support limited capability hosts or networks will enable what we refer to as ?broadband connectivity on demand?. A set of directional wireless base-stations can be rapidly deployed in ?demand areas? (demand for broadband connectivity) forming a flexible backbone that will rapidly provide broadband connectivity. Moreover, the fact of being a flexible infrastructure, where base stations can move and links reconfigure, allows for the possibility to adapt to dynamic changes such as host mobility, traffic demands and link state changes. All these issues make directional wireless backbone networks a very promising technology for providing instant broadband communications capabilities in a wide range of situations and scenarios such as: disaster recovery, event response, temporary missions in remote areas, developing or infrastructure-less areas, high-quality real-time video surveillance, monitoring critical infrastructures, Backbone-Aided Wireless Networks Directional Wireless Backbone Peer-to-peer and Base-station RF subnets Terrestrial Near-surface, surface and sub- surface user systems Airborne 5 internetworking, last mile solutions, etc. Fig. 1.2 illustrates some of these applications. Figure 1.2: Rapidly deployable, flexible broadband communications using directional wireless technologies. The main challenge in the design of directional wireless backbone (DWB) networks is to provide assured connectivity in dynamic environments. A backbone network must provide highly available broadband connectivity. In this context, two key metrics are defined: robustness and survivability. Robustness refers to the strength of connectivity and its availability. Survivability refers to the ability of the network to regain connectivity in the face of loss or degradation. Optical fiber or other wireline backbones are inherently robust. They are fixed infrastructures with strong, highly available connections, but lack the flexibility to react to dynamic 6 changes and reach every host in every environment. Ubiquitous broadband connectivity needs broadband wireless backbones. DWB networks put together the high capacity of fiber backbones with the flexibility of wireless networks. The wireless medium, though, has dynamic behavior due to mobility, fading and obscuration. Thus, assuring robustness and survivability in a dynamic wireless environment is a challenging problem. The objective of this dissertation is to: 1) provide a good understanding of the physical nature and dynamics of DWB networks and 2) develop algorithms and protocols for the design of self-organizing DWB networks that could provide assured broadband connectivity in such a dynamic environment. 1.1.3 Self-organization Topology control is presented as the means to provide self-organization in DWB networks. We define self-organization as the network capability to autonomously reorganize its physical topology. Controlling the topology of a directional wireless network is fundamentally different from the case of wireless networks based on omnidirectional transmissions. In ad-hoc and sensor wireless networks, power control is used to create topologies that maintain network connectivity while reducing energy consumption and improving network capacity [31]. In directional wireless networks, power control does not change the physical topology and has a negligible effect on the network capacity. The physical nature of directional wireless networks, where links are formed by physically pointing two directional transceivers at each other, and 7 information is transmitted point-to-point, drives the need to consider new mechanisms for providing self-organization in DWB networks. In this dissertation, topology control is defined in the context of directional wireless networks, where the physical topology can be reorganized through: 1) topology reconfiguration (TR), which refers to the process by which point-to-point links are broken and set-up for creating a new topology; and 2) mobility control (MC), which refers to the process by which backbone nodes are repositioned to adjust actual and potential link states. The potential of these two mechanisms for creating robust backbone topologies will be studied. Coverage and connectivity are perhaps two of the most important issues in DWB-based networks. In our backbone-based architecture, the lower tier determines the service demand. From the backbone perspective, there is no control over the lower tier. Clusters at the host layer move according to their respective missions or tasks. Traffic generated at this layer varies accordingly, etc. The objective of the DWB is to dynamically adjust to the lower layer needs and assure overall connectivity. Two main objectives are considered in this dissertation: terminal coverage and backbone connectivity. That is, the DWB must provide coverage to as many terminal nodes as possible and maintain connectivity or bi-connectivity. These are typically competing objectives. That is, maximizing terminal coverage involves backbone configurations where nodes are spread in regions where clusters are deployed, whereas assuring robust backbone connectivity typically involves bringing backbone nodes together to increase connectivity and/or strength of connectivity. 8 This dissertation presents the design of algorithms and protocols to jointly optimize these two objectives in dynamic environments. Optimal backbone configurations will strongly depend on the cost model of communications. Thus, a good understanding of the physical nature of the wireless channel is needed. DWB-based networks are heterogeneous in terms of their communication capabilities. Wireless communications technologies DWB networks include RF and infrared transmissions with different antenna patterns (directional versus omnidirectional transmissions). Standard wireless channel models are based on homogeneous RF transmissions and do not take into account effects such as atmospheric attenuation and turbulence-induced fading which are shown to be significant in directional wireless communications. Line of sight (LOS) constraints, atmospheric obscuration, turbulence-induced fading and node mobility are the main contributors to the time variation of the directional wireless channel. In this dissertation, we present atmospheric propagation models for both FSO and directional RF communications. These include attenuation models based on scattering of electromagnetic radiation by suspended water particles in the atmosphere and turbulence-induce fading models. These models are used to characterize communication cost (and as a result, strength of connectivity) in DWB networks. Realistic simulation scenarios including moving cloud layers at different altitudes and turbulence effects have been developed for performance analysis of topology control techniques in dynamic DWB-based networks. Our overall topology control scheme is aimed to be self-organized. The inspiration for the system?s self-organizing capability presented in this dissertation 9 comes from the theory of potential fields. We propose to model the network as a system of particles in a potential field. A potential energy function, which is related to the energy used for communications in the network system, is used to characterize the cost of a given backbone configuration. Forces between nodes are defined based on network connectivity. The effects of the host layer (cluster mobility) and of the environment (atmospheric turbulence and obscuration) are modeled as external forces changing the potential energy of the network system. Analogies from physical systems such as spring systems are used to model the reaction of the DWB network, which autonomously adjusts its physical topology based on resulting forces to achieve energy minimizing configurations. Mechanisms to mimic this self-organizing behavior are presented in the context of topology reconfiguration and mobility control. The aim is to design a powerful and self-organizing primitive that can achieve diverse configuration goals and that can be gracefully tuned to ensure desirable network properties such as connectivity, coverage, and power efficiency. 1.2 Dissertation Contributions This dissertation provides a new framework for the modeling, characterization and control of next generation wireless networks. Heterogeneous and dynamic networks are modeled as physical systems where network robustness is characterized by the system?s potential energy. A self-organized topology control capability has been developed that mimics the behavior of analogous physical systems whose topologies are adaptive and robust as a result of internal physical interactions among 10 the nodes forming the network. The algorithms developed are completely distributed, show constant time complexity, achieve optimal solutions from local interactions and ensure desirable network properties such as coverage, connectivity and power efficiency. The contributions of this work can thus be summarized as follows: - Communication networks as physical systems: Heterogeneous and dynamic networks are modeled as physical systems whose topologies are adaptive and robust as a result of internal physical interactions among the nodes forming the network. Network robustness is characterized by the system?s potential energy. The potential energy of a communications network is defined as the communications energy needed to maintain its physical topology at the required target performance. The network dynamics, in the form of node mobility and channel variations, are modeled as external excitations that change the energy of the network system. Topology control strategies have been developed in order to mimic the natural and self-organized reaction of physical systems to external excitations to minimize the energy of the system by reacting to internal forces exerted on network nodes. - Improved link physics models for heterogeneous and dynamic wireless networks: Link physics models that account for the variation of the wireless channel due to atmospheric attenuation, turbulence-induced fading, node mobility, and different antenna patterns, have been developed. The developed link physics models are used 11 to characterize the dynamic behavior of the potential energy stored at the heterogeneous set of wireless links forming the network. - Joint coverage-connectivity optimization: The topology control problem is formulated as a convex energy minimization problem whose solution is shown to jointly optimize coverage and connectivity in highly dynamic scenarios. - Force-driven mobility control: The convex optimization method developed results in force-driven mobility control algorithms which make nodes adjust their position in the direction of the net force acting at the node?s location. The net force is defined as the negative gradient of the potential energy function at the node?s location. Force-driven mobility control algorithms which minimize the energy of the network system are shown to be distributed, scalable, and to ensure desirable global network properties such as coverage, connectivity and power efficiency, from local interactions, thus proving the systems self-organizing capability. 1.3 Organization The remainder of this dissertation is organized as follows: Chapter 2 introduces the concept of topology control. Previous work on topology control in homogeneous networks is presented and the key differences with respect to topology control in heterogeneous networks are described. Chapter 3 presents our novel physics-based approach to topology control in heterogeneous dynamic networks. In 12 Chapter 4, link physics models for characterizing the behavior of the heterogeneous set of wireless links forming the network are described. Chapter 5 presents topology reconfiguration algorithms for degree constraint directional wireless backbone networks. Chapter 6 is the main chapter of this dissertation. In chapter 6, a convex optimization method for joint coverage-connectivity optimization is presented as an energy minimization problem. As a result, force-driven mobility control algorithms that are able to react to the network dynamics by autonomously adjusting its physical topology are described. Simulation results show the effectiveness of the algorithms developed. Chapter 7 states the conclusion, summarizes the main contributions of this dissertation and introduces future work. 13 Chapter 2: Topology Control 2.1 Introduction and background We define topology control as the autonomous network capability to change its physical configuration (arrangement or layout of the nodes in the network and its communication links). The network topology is represented by a communication graph G = (V, E) where the vertex set V represents the network nodes and the edge set E, the links between them. Topology control in ad-hoc wireless and sensor networks has been extensively studied in terms of power control. Energy efficiency [31] and network capacity are perhaps two of the most important issues in wireless ad hoc networks and sensor networks. Topology control algorithms have been proposed to maintain network connectivity while reducing energy consumption and improving network capacity. The key idea to power control is that, instead of transmitting using the maximal power, nodes in a wireless multi-hop network collaboratively determine their transmission power and define the network topology by forming the proper neighbor relation under certain criteria. By enabling wireless nodes to use adequate transmission power (which is usually much smaller than the maximal transmission power), topology control can not only save energy and prolong network lifetime, but 14 also improve spatial reuse (and hence the network capacity) and mitigate MAC-level medium contention [32]. A key feature of the omnidirectional wireless channel is that it is a shared medium. Thus, choosing an excessively high power level causes excessive interference as seen in Fig. 2.1a. This reduces the traffic carrying capacity of the network in addition to reducing battery life. On the other hand, in Fig. 2.1b, having a very small power level results in fewer links and hence network partitioning. When the power level is just right, the network is still connected and there is no excessive interference as shown in Fig. 2.2c. Several topology control algorithms [31-36] have been proposed to create power-efficient network topology in wireless multi-hop networks with limited mobility. Figure 2.1: Power control in ad-hoc wireless networks. Despite all this work, Gupta and Kumar showed that wireless networks based on omnidirectional transmissions are inherently not scalable. Their capacity is constrained by the mutual interference of concurrent transmissions between nodes. 15 The main result shows that as the number of nodes per unit area increases, the throughput per source-to-destination (S-D) pair decreases approximately like n/1 , where n is the number of nodes in the network. This is the best performance achievable even allowing for optimal scheduling, routing, and relaying of packets in the network and is a somewhat pessimistic result on the scalability of such networks, as the traffic rate per S?D pair actually goes to zero [4]. In [38], Grossglauser and Tse introduced mobility into the model and considered the situation in which users move independently around the network. Their main result shows that the average long-term throughput per S?D pair can be kept constant even as the number of nodes per unit area increases. This is in sharp contrast to the fixed network scenario and the dramatic performance improvement is obtained through the exploitation of the time variation of the users? channels due to mobility. The result implies that, at least in terms of growth rate as a function of n, there is no significant loss in throughput per S?D pair when there are many nodes in the network as compared to having just a single S?D pair. A caveat of this result is that the attained long-term throughput is averaged over the time-scale of node mobility and, hence, delays of that order will be incurred. In the fixed ad hoc network model, the fundamental performance limitation comes from the fact that long-range direct communication between many user pairs is infeasible due to the excessive interference caused. As a result, most communication has to occur between nearest neighbors, at distances of order n/1 [4], with each packet going through many other nodes (serving as relays) before reaching the destination. The number of hops in a typical route is of order n . Because much of the traffic carried by the nodes is 16 relayed traffic, the actual useful throughput per user pair has to be small. With mobility, a seemingly natural strategy to overcome this performance limitation is to transmit only when the source and destination nodes are close together, at distances of order n/1 . However, this strategy turns out to be too naive. The problem is that the fraction of time two nodes are nearest neighbors is too small, of the order of n/1 . Instead, the strategy in [38] is for each source node to split its packet stream to as many different nodes as possible. These nodes then serve as mobile relays and whenever they get close to the final destination, they hand the packets off to the final destination. The basic idea is that since there are many different relay nodes, the probability that at least one is close to the destination is significant. On the other hand, each packet goes through at most one relay node and, hence, the throughput can be kept high. Although the basic communication problem is point-to-point, this strategy effectively creates multi-user diversity by distributing packets to many different intermediate nodes that have independent time-varying channels to the final destination. In the model used in [38], mobility is a random uncontrolled parameter, but the fact that the node mobility changes the network topology is used to improve communication performance. Thus, controlling the mobility of some nodes in the network could be very promising to further improve network performance. However, using controlled node mobility to improve communication performance is a capability that the mobile networking community has not yet paid much attention. In [39], Goldenberg et al. studied mobility as a network control primitive. They presented a completely distributed mobility control scheme where relay nodes align themselves to 17 provide power-efficient routes for one flow, multiple flows, and many-to-one concast flows. They provided evaluations of the feasibility of mobility control and showed that there are many scenarios where controlled mobility can provide substantial performance improvement. 2.2 Topology control in DWB networks Next generation wireless networks, and in particular DWB-based networks, are becoming increasingly complex systems due to their heterogeneous architecture and their dynamic behavior. Diverse communication technologies are used at different layers of the architecture in order to provide end-to-end broadband connectivity. The use of directional wireless communication technologies at the backbone layer and its unique behavior compared to traditional omnidirectional RF transmissions needs to be studied in the context of topology control. In directional wireless communications energy is transmitted point-to-point. Changing transmitted power or moving a node does not necessarily change the actual connections between nodes. Power and mobility control can be used to change potential connectivity and actual energy usage, but in order to establish a new connection a reconfiguration process must occur, where two directional transceivers (one from each node) are pointed to each other so that communication can occur. This makes topology control in directional wireless networks a fundamentally new problem. In the context of DWB networks: 18 ? Power control is used to determine communication cost. The higher the transmitted power needed to maintain a given link BER, the higher the communication cost. ? Mobility control is used to change the communication cost of actual and potential links in the network. ? Topology reconfiguration is used to break and set up point-to-point links to create a new backbone topology. Topology control strategies need to address two fundamental questions: 1) what defines a ?good? topology (or communication graph), and 2) how to configure such ?good? topologies. With respect to the first question, in DWB networks we seek the formation of robust backbone topologies. That is, topologies that provide the network with the continued ability to perform its function in the face of loss or degradation. A main advantage of directional wireless communications is that the channel is not shared. Directional wireless links are dedicated point-to-point links. Therefore, dense communication graphs do not translate into excessive interference with the resulting reduction in network capacity, as is the case in omnidirectional wireless networks. In DWB networks, on the other hand, dense mesh topologies lead to high network robustness. Constraints come from the limitation on the number of directional transceivers per node and power usage. The cost of a mesh network in terms of number of transceivers and power usage is higher the denser the topology. In this work, TR algorithms to find degree-limited minimum cost topologies in polynomial time are presented. Algorithms have been developed for ring and 3-degree networks 19 [42]. Also, for a given topology structure, communication cost can be different based on the location of the nodes forming that topology. MC algorithms have been developed to provide power-efficient topologies without breaking or creating new point-to-point links [55, 56]. With respect to the second question above, the process by which a new DWB topology is formed requires 1) the physical redirection of directional transceivers and/or 2) the physical reposition of backbone nodes. The hardware process that achieves the formation of a new directional wireless link is referred to as pointing acquisition and tracking or PAT [29]. A lot of work has been done in this area and it still remains a very challenging problem, especially when nodes are mobile [29]. This process requires the joint coordination of two nodes for: ? Agreeing in making a connection. ? Identifying each other (location, distance, potential connectivity, etc). ? Coordinating their hardware executions. Moreover, when several links are changed during the reconfiguration process the network goes into a state of degraded connectivity (which may involve network partitions). Thus, the reconfiguration process has a cost associated with it that needs to be taken into account before making a decision for reconfiguration. On the other hand, moving a backbone node does not incur any loss of data as long as there is enough power to guarantee a minimum BER-defined link performance. 20 In this dissertation, MC and TR mechanisms have been studied and developed as part of a self-organizing network capability that allows optimizing network performance in dynamic scenarios. It is important to note that what makes the topology control problem in DWB- based networks a unique problem is the heterogeneous and dynamic nature of such networks. DWB networks form a wireless backbone infrastructure that interconnects a dynamic set of users with lower communication capabilities. Backbone nodes use different communication technologies to communicate with end users and neighbor backbone nodes, whose dynamic behavior and its effect on network performance need to be taken into account. 2.3 Coverage and connectivity We address the topology control problem for DWB-based networks as a joint coverage-connectivity optimization problem. Not known approaches till date have considered the joint coverage- connectivity optimization problem in dynamic networks. Work has been done for separately optimizing network coverage and backbone connectivity in relatively fixed scenarios. Optimal base station placement for network coverage optimization is typically addressed as a design problem in the context of clustering or facility location problems (FLP), which are known to be NP-Complete [40]. Centralized approximation algorithms have been developed that achieve close-to-optimal solutions in a relatively fixed scenario. But the need for global network information 21 makes them not suitable for coping with the heterogeneous and dynamic nature of next generation wireless networks. Also, backbone connectivity is usually assumed to be guaranteed by a fixed backbone infrastructure, a very limiting assumption in a dynamic scenario. Recent work has addressed the backbone connectivity optimization problem in directional wireless networks [42-50]. In this context, approaches have either considered the topology reconfiguration process in which the location of the backbone nodes is given and the optimization is done over the assignment of links between them; or the relay node placement problem which considers the addition of backbone nodes to provide connectivity between already placed, typically fixed, base stations. In both cases, global network information is required to compute the new topologies. Also, in order to implement them, new point-to-point links need to be set- up, which involve the physical redirection of directional beams with its associated loss of data. New mathematical models and optimization methods that can address the increasing heterogeneity and dynamic behavior of next generation complex network systems are required. Specifically, new methodologies need to provide: ? Accurate link physics models in order to precisely characterize the behavior of the heterogeneous set of communication links in the network ? Distributed low complexity algorithms for dynamically optimizing network performance by providing the network with the required self-organizing capability. ? Joint coverage-connectivity optimization 22 Chapter 3: A Physics-based approach to topology control in dynamic wireless networks 3.1 Introduction Next generation communication networks are becoming increasingly complex systems due to their heterogeneous architecture and dynamic behavior. The need for ubiquitous broadband connectivity is driving communication networks to adopt hierarchical architectures with diverse communication technologies and node capabilities at different layers that provide end-to-end broadband connectivity in a wide range of scenarios. Modeling such complex systems is a very challenging and cumbersome mathematical problem. New network scientific approaches to modeling such dynamic networks are needed, while at the same time retaining physical reality within the modeling parameters. This dissertation provides new analytical tools to understand the nature of communications in complex wireless networks and its effect on network performance, and control strategies to dynamically optimize network performance in uncertain environments. 23 3.2 Network robustness and potential energy We seek methodologies for providing robustness through self-organization in dynamic networks. Very complex systems in a variety of fields can be modeled as networks; that is, a set of nodes that represent the physical entities in the system, and a set of links representing the physical interactions between the system?s entities. In nature, physical systems have developed robust self-organizing capabilities in order to adapt to the changing environment. We present topology control mechanisms for complex dynamic wireless networks that mimic the natural and self-organizing behavior of analogous physical systems whose topologies are adaptive and robust as a result of internal physical interactions among the nodes forming the network. Robustness in physical systems is related to the system?s potential energy. Robust network configurations arise when the system?s potential energy is minimized. We plan to define potential energy functions to characterize the communications cost of heterogeneous network configurations and develop topology control strategies that try to optimize desirable network properties such as coverage, connectivity and power efficiency, by minimizing the system?s potential energy. The potential energy of a physical system is defined as the energy stored within the system due to its position (physical configuration) in space. A communications network is, in essence, electromagnetic energy being propagated among the nodes forming the network. Therefore, we define the potential energy of a communications network as the total energy stored in the communication links forming the network or the energy used for communications for a given target performance. The potential energy of a communications network is thus determined 24 by its physical configuration in space or network topology, as defined by the location of the network nodes and the choice of communication links between them. In dynamic DWB-based networks, changes in the cost of the network topology are due to: 1) Uncontrolled parameters: a. End users mobility b. Atmospheric obscuration c. Node failures. 2) Controlled parameters: a. Location of backbone nodes b. Connections between backbone nodes Uncontrolled parameters such as the mobility of terminal nodes (whose motion is determined by their respective missions, tasks, and applications), the presence of atmospheric obscuration, and node failures, change the energy of the network system. For example, two neighbor nodes moving away from each other will increase the energy of the system as more power needs to be transmitted to maintain link performance, while the opposite will occur when the nodes move closer to each other. In physics, any change in the energy of a system results from the presence of a net force acting on the system. In our model, we characterize uncontrolled parameters changing the energy of the network system as external forces. An external force can increase or decrease the energy of the system. Thus, we can model the network dynamics as external forces changing the energy of the network system. The presence 25 of atmospheric obscuration and the mobility of nodes changing link distances, act as forces perturbing the equilibrium condition of the network system. We say the network is in equilibrium when the total net force acting on the system is zero, and thus the energy is not changing. Physical systems naturally react to minimize their potential energy and thereby increase their robustness. Internal forces are responsible for bringing the network to an equilibrium condition where the total energy is minimized. Our approach models network control strategies as internal forces minimizing the energy of the network system. For example, mobility control schemes should adjust the location of controlled backbone nodes in the direction of the decreasing energy function. We aim to develop algorithms and protocols for mobility control by computing internal forces at each backbone node as negative energy gradients and to show how the network can autonomously achieve energy minimizing configuration driven by local forces exerted on network nodes. The beauty of this physical energy model is that very complex systems can be characterized with continuous and convex energy functions which take into account the heterogeneity of the network system. Moreover, the network dynamics is naturally characterized as external forces perturbing the energy of the system and control strategies as internal forces reacting to external excitations in order to achieve energy minimizing configurations. 26 This dissertation also shows how the use of control strategies that minimize the energy of the network system, ensure desirable network properties such as coverage, connectivity and power efficiency. 3.3 Problem statement In our network architecture, a host s communicates with another host d in the following way: host s transmits its information to the closest backbone node; then the traffic traverses through the backbone network until it reaches the backbone node that is closest to the destination. Finally, the backbone node that is closest to the destination transports the traffic to the host d. As it can be observed, this scheme is based on two properties: first, the end hosts need to be well covered by the backbone nodes, and second, the backbone nodes must have good connectivity among themselves. We formulate the topology control problem in DWB-based networks as an energy minimization problem. We define a potential energy function for the network system as the total communications energy stored in the wireless links forming the network topology, as follows: 443442144 344 21 G M k kk F N i N j ij uubU ??? == = += 1 )h( 1 ji 1 )r,R()R,R( , (3.1) where Ri is the location of backbone node i, rk the location of terminal node k, N the number of backbone nodes, M the number of terminal nodes, h(k) the index of the 27 backbone node covering terminal node k, and bij the integer variables that determine the backbone topology: ?? ? ?= o.w. 0 if 1 T(i,j)b ij , (3.2) where T refers to the backbone topology. The link cost function )R,R( jiu represents the potential energy of link (i,j) and will be precisely defined in the following chapter as the communications energy per unit time needed to send information from node i to node j at the specified BER. Note that the first term in of the cost function, denoted by F, represents the total energy stored in the directional wireless links forming the backbone network, and the second term G represents the total energy stored in the wireless links covering the end users. Thus, F is a measure of cost for the backbone connectivity, i.e. a higher value of F indicates a backbone topology where higher communications energy needs to be provided in order to maintain backbone nodes connected. On the other hand, a higher value of G indicates a higher demand for communications energy in order to maintain end users covered at the specified QoS (BER). Thus, we formulate the joint coverage-connectivity optimization problem as a weighted multi-objective optimization problem of the following form: ?? ? ?= ? ? ?? ? ?+ ??? ? ??? ??= +?= ??? == = o.w. 0 if 1 s.t. )r,R()R,R( )R,...,R,(min 1 )h( 1 ji 1 N1 T(i,j)b uub GFbU ij M k kk N i N j ij ij ? ? . (3.3) 28 Note that in the above formulation the optimization is performed over 1) the assignment of directional wireless links between backbone nodes bij and 2) the location of the N backbone nodes )R,...,R( N1 . These are the controllable parameters from the topology control perspective. TR mechanisms determine the link assignments bij and MC mechanisms determine the locations )R,...,R( N1 . A stated earlier, the term F in the above cost function is a metric of connectivity of the backbone nodes, and minimizing it results in a strong DWB topology. The term G, on the other hand, is a metric of coverage and minimizing it results in high network coverage. The parameter ? ( 0?? ) acts as a balancing factor between the two optimization terms. Minimizing the above cost function J for different values of ? will produce Pareto-optimal solutions. The cost function U represents the potential energy of the communications network, i.e. the communications energy needed to create/maintain/guarantee the communications functionality in the network system. It can also be thought as the communications energy stored in the network system, i.e. the potential energy of an analogous physical system where communications links define forces of interaction between network nodes. Of key importance in the optimization problem stated in Eq. 3.3 is therefore to define the link cost functions uij that will determine the form of the overall cost function U. In the following section, we present link cost models that take into account the energy usage for the different wireless technologies used in DWB networks. 29 Chapter 4: Physical layer characterization 4.1 Introduction and background Modeling the propagation channel has always been one of the most difficult parts of the design of wireless communication systems. Typically, the channel variations are characterized statistically and are grouped into two broad categories: large-scale and small-scale variations. Large-scale propagation models are used to predict the mean signal power for any transmitter-receiver (TX-RX) separation. Small-scale signal models characterize the rapid fluctuations of the received signal strength over very short travel distances [6]. The most common channel model used in wireless communication systems has the following components. ? Path loss: the received signal power averaged over large scale variations has been found to have a distance dependence which is well modeled by 1/dn, where d denotes the TX-RX distance and the exponent n is determined from field measurements for the particular system at hand [6]. ? Large-scale variations: these are modeled by the lognormal shadowing model. In this model, the received signal power averaged over small-scale variations is statistically described by a lognormal distribution with the distance-dependent mean obtained from the path loss calculation [6]. 30 ? Small-scale variations: these are modeled by a Rayleigh distribution. In the Rayleigh model, the received signal is a wide-sense stationary stochastic process whose amplitude at each point in time is a Rayleigh random variable [6]. Small-scale variations are typically due to multipath. That is, the received signal is the superposition of two or more streams of the same data that have traveled through different paths. This effect is especially common in terrestrial wireless communication systems where information is sent isotropically and different rays can reach the same receiver having traveled different paths, due to reflections in buildings or other obstacles. Typically, a wireless communication receiver is designed with diversity reception to combat small scale variations, which means that the receiver can collect streams of the same data that have traveled through independent paths. A widely used diversity technique is the Rake receiver in spread-spectrum communication systems, which collects multipath components at intervals of the chip period [6-8]. A technique called maximum ration combining (MRC) is used to optimally combine these independent streams. In a full Rake receiver, all multipath components are collected and combined optimally. Directional wireless networks, on the other hand, involve line of sight (LOS) point-to-point transmissions and thus there are no multipath effects [1]. Large scale variations are typically due to shadow fading effects caused by the presence of large obstructions in the path between the transmitter and the receiver [6]. In wireless communication systems a tolerable bit-error-rate (BER) is specified for 31 large scale variations. Based on the tolerable BER, a minimum received signal power is required to account for the signal fades and guarantee the specified BER. In directional wireless communications, large scale signal variations are quite important and are mainly due to atmospheric turbulence. This effect is especially strong in FSO links. Optical turbulence is caused almost exclusively by temperature variations in the atmosphere, resulting in the random variations of refractive index. An optical field propagates through the atmospheric turbulence will experience random amplitude and phase fluctuations, which will generate a number of effects: break up of the beam into distinct patches of fluctuating illumination, wander of the centroid of the beam, and increase in the beam width over the expected diffraction limit [13-17]. In terms of communications performance, the intensity fluctuations produced by atmospheric turbulence translate into reduced signal-to-noise ratio (SNR) and increased link bit-error-rate (BER). In direct-detection FSO systems using on-off keyed (OOK) modulation, the BER is found to be: ? ? ?? ? ?= 022 1erfc 2 1 SNRBER , (4.1) where SNR0 is the signal to noise ratio in the absence of atmospheric turbulence, defined as: ( ) R kTBPeB PiSNR S S N S 42 2 2 2 0 +? ?== ? , (4.2) where is is the output signal current from the detector, ?N is the noise variance (zero- mean white Gaussian noise is assumed), Ps is the received signal power, ? is the receiver responsivity, B is the bandwidth, k is the Boltzmann constant, T is the 32 effective noise temperature, and R is the effective resistance of the receiver circuitry [9]. In Eq. 4.1 the threshold level is set at half the average signal level 2STH ii = . In the presence of optical turbulence, the signal current is a random variable NS iii += with mean Si and variance 222 NSi ??? += . The averaged SNR is given by: 2 0 26/5 2 2 0 2 2 233.11 I L I i S SNRkwL SNRiSNR ?? ? + ? ? ? ? ? ? ? ? ??? ? ??? ?+ == , (4.3) where I? is the variance of the intensity fluctuations, L the link length and wL the spot size [15]. Note from Eq. 4.3 that in the presence of atmospheric turbulence the average SNR is always lower than SNR0. The resulting BER is obtained averaging Eq. 4.1 over the intensity fluctuation spectrum. This leads to the expression: ( )?? ?? ? ? ??? ?= 0 22 erfc21 S s s SI diSNRi iipBER , (4.4) where pI(i) is the probability density function (PDF) of the intensity fluctuations. A lognormal distribution is generally used to model pI(i) [15]. Fig. 4.1 shows the calculations of BER for an FSO system as a function of SNR0, for intensity variance ranges from 0.001 to 0.5 [15]. 33 Figure 4.1: BER of an FSO system at different intensity variance values. A lot of work has been done to design techniques for mitigating the effects of optical turbulence. These techniques involve transmitter and/or receiver designs such as aperture averaging and delay diversity techniques [18-20]. In this dissertation, turbulence-induced fading models for both RF and FSO technologies are used for link margin calculations. The minimum received power needed to guarantee a specified link BER is computed based on these models. In the context of topology control, the most important channel factor to consider is the path loss. Given the receiver sensitivity and the link margin for turbulence-induced fading, the transmitted power needed to guarantee that the received power is above the link margin will depend on the path loss. In general, path loss is a function of the link distance and the link directivity. In directional wireless communications, moreover, absorption of the beam by the 34 atmosphere can be important, especially in adverse weather conditions of fog, clouds, rain, snow, or in conditions of battlefield obscuration [21]. The combined effects of direct absorption and scattering of electromagnetic radiation can be described by a single path-dependent attenuation coefficient ( )z? . The power reaching a RX from a TX can easily be calculated for links without significant turbulence effects. The received power PR for a RX with receiver area A, coming from a transmitter at range L and beam divergence angle ? , varies as: 22 2 L AePP L TR pi? ??= , (4.5) where PT is the transmitted power, and ? in this case is assumed constant along the propagation path L. This result assumes a directional beam whose beam width at the receiver is significantly greater than the receiver diameter. Tightly collimated systems have been proposed [23] for which LTR ePP ??= . In this dissertation, atmospheric propagation models for both FSO and RF communication will be presented. These include attenuation models based on scattering of electromagnetic radiation by suspended water particles in the form of fog and clouds, turbulence-induced fading models and directivity-driven free space path loss. These models are used to extend current wireless channel models in order to provide a more comprehensive characterization of the wireless channel in increasingly heterogeneous and dynamic wireless networks. Communication cost in DWB-based networks will be defined based on the developed models. 35 4.2 Communication cost model In DWB-based networks backbone nodes use a hybrid communication mode in order to communicate with both end users and neighbor backbone nodes. Omnidirectional RF transmissions are used to cover end users at tier 1 of the architecture while directional wireless communications are used to aggregate traffic from end users and transport it through the backbone at tier 2 (see Fig. 1.1). Moreover, directional wireless communications use both RF and FSO technologies to send information point-to-point without causing interference. Thus, we need to define a general link cost function for a wireless link (i,j) that takes into account the behavior of the diverse wireless technologies used in next generation wireless networks (omnidirectional RF, directional RF and directional FSO). In this work, we focus on the communications energy used at the wireless links forming the network and define the general link cost function for a given link (i,j) as the transmitted power needed at transmitter i in order to guarantee a specified BER at receiver j: ij j Rij Pu ??= 0 , (4.6) where jRP 0 is the minimum received power at node j in order to guarantee the specified BER and ij? is the path loss or path attenuation for link (i,j). We refer to j RP 0 as the link margin and will be described based on the large scale variations of the wireless channel in section 4.3. The path loss ij? for a link (i,j) with distance L defined as ji RR ?=L , where Ri and Rj are the locations of nodes i and j respectively, is described in terms of two main components: 36 444 3444 21 43421 fs n j eR i Tobs ij ADe ij ? pi ? ? ? jiRR RR4ji ?= ? , (4.7) where obs? refers to the atmospheric obscuration (or attenuation) and fs? to the free space path loss. The atmospheric obscuration component is an exponential function of the link distance L with atmospheric attenuation coefficient ? , and will be described in section 4.4.2. The free space path loss component is a polynomial function of the link distance (typically quadratic in non urban areas) and inversely proportional to de product RT AD . The product RT AD determines the link directivity and will be described in section 4.4.1. Using Eq. 4.7, the general link cost model becomes: ( ){ 44444 344444 21 444 3444 2143421 ? ? pi ? ? fs n j eR i T obs j Rij ADePu ij ?? ? ? ??? ? ?? ? ?? ? ?= ? ji RR marginlink 0 RR 4ji , (4.8) where again uij represents the cost of link (i,j) in terms of the communications energy per unit time needed to assure a specified BER when sending information from node i to node j, as illustrated in Fig. 4.2. 37 Figure 4.2: Wireless link model parameters. The link cost function in Eq. 4.8 will be used to characterize the potential energy of the network system, as stated in Eq. 3.1. Recall that the idea is to abstract the communications network as a physical system where communication links define physical interactions between network nodes, which are determined based on the variation of the potential energy. In the following sections we precisely define the three main components of the link cost function uij: 1) link margin, 2) atmospheric attenuation, and 3) free space path loss. 4.3 Turbulence induced fading Large scale time variations of the received signal intensity in directional wireless communications are mainly due to atmospheric turbulence. A lot of work has been done to characterize atmospheric turbulence [13-17], and several techniques have been developed to mitigate its effects on FSO communication links [18-20]. In Ri DT Rj AR PR0 i j ij? L 38 this dissertation we present models that characterize turbulence-induced fading for both FSO and RF links. These models are used to define the probability density function (PDF) of the intensity fluctuations pI(i) at the receiver. In FSO communications a lognormal distribution is generally used to model pI(i) [15]. One way to measure the strength of atmospheric turbulence is by examining the variance of the log intensity fluctuations (Rytov variance [19]) described as: 6/116/722 23.1 LkC nR =? , (4.9) where 2nC is the atmosphere refractive index structure parameter, ?pi2=k is the wave number, and L is the propagation length [15]. In terms of this parameter, the turbulence is called ?weak? if 3.02 R? , although true strong turbulence may need 252 >R? [15]. Fig. 4.3 compares the variances calculated using Fante?s weak and strong turbulence theories with the Rytov value [19]. It also shows the path of a composite curve that is predicted to be valid over all turbulence strengths. 39 COMPARISON OF CORRELATION PARAMETER WITH RYTOV VALUE Square root of variances, 863 meters range, 632.8 nonometers 0 1 2 3 0 1 2 3 4 5 Sigma(Rytov) Si gm a(W ea k) an d S igm a(S tro ng ) Rytov Weak Theory Strong Theory Composite Weak Rytov Strong Figure 4.3: Weak and Strong Variances compared with the Rytov value [20]. Circles shown represent the path of a composite curve that is predicted to be valid over all turbulence strengths. Note that the ?Weak? curve follows the linear variation predicted by the Rytov variance well up to 3.02 =R? . The ?Strong? curve is not valid for small values of 2R? , but should represent expected variances well for 12 >R? . The circles in Fig. 4.3 represent a path for a ?composite curve? that follows weak? for small 2R? and then merges with strong? for larger 2R? . Such a composite curve demonstrates the increase in intensity variance that occurs as turbulence increases followed by its saturation at high levels of turbulence. 40 Under weak turbulence conditions, where the Rytov approximation holds, the parameter that determines the turbulence strength is the 2nC value (from Eq. 4.9). Fig. 4.4 shows examples of the Rytov variance in the operating range below 1km for various turbulence strengths with 2nC values range from 10-13 to 10-17, and an optical wavelength of 1310nm. Figure 4.4: Rytov variance versus propagating distance (1310nm beam) for different Cn2 values. In the case of RF links, which use electromagnetic waves in the millimeter and microwave region, Clifford and Strohbehn [13] derived a general result for the amplitude and phase fluctuations, which for the most practical propagation paths of interest reduce to the formulas presented earlier for optical wavelengths. Thus the 41 Rytov variance as described in Eq. 4.9 will be used to determine the amplitude of intensity fluctuations for RF links as well. Note that due to the 6/7k dependence, RF links, which use larger wavelengths than optical links, will experience less intensity fluctuations and therefore will be more resistant to turbulence effects. The BER is used as a measure of link performance at the physical layer. A link is considered feasible for communications if its BER is below a given threshold (typically 10-9-10-6). The link BER can be derived from the signal-to-noise ratio (SNR) and the probability density function of the intensity fluctuations pI(i) using Eq. 4.4: ( )?? ?? ? ? ??? ?= 0 22 erfc21 S s s SI diSNRi iipBER . From the above equation, the average signal-to-noise ratio SNR required to guarantee a specified BER can be computed. The required SNR0 can then be found using Eq. 4.3: 2 0 26/5 2 2 0 233.11 I L I SNRkw L SNRSNR ?? + ? ? ? ? ? ? ? ? ??? ? ??? ?+ = Finally, the required average received power PR0 is obtained using Eq. 4.2 as: ?= N R SNRP ? 00 , (4.10) where ? is the receiver responsivity and N? the noise standard deviation. Based on these models, the minimum received power PR0 for every potential link in the network can be determined. 42 4.4 Path loss Directional wireless backbone networks are typically deployed at high altitudes, where line of sight can be exploited. DWB nodes can be deployed on top of buildings or other infrastructures, or can be airborne, for example involving UAVs (Unmanned Aerial Vehicles) at very high altitudes. Thus, the propagation medium where directional wireless links are going to be deployed typically involves the low layers of the atmosphere. Path loss is defined as the attenuation undergone by an electromagnetic wave in transit between a transmitter and a receiver. The path loss ? for a wireless link can be derived as the ratio between the transmitted power and the received power: { 43421 fs n eRTobs L R T L ADeP P ? pi ? ? ? 4== , (4.11) where obs? refers to the path loss due to atmospheric obscuration and fs? to the free- space path loss. In the following sections we will describe in detail these two main path loss components. 4.4.1 Free space path loss The free space path loss measures the attenuation of an electromagnetic signal that would result from a line of sight path through free space, with no atmospheric obscuration effects, and it is defined as: n eRT FS LAD pi? 4= , (4.12) 43 which is a polynomial function of the link distance. The eRT AD pi4 constant is independent of the nodes? locations and will be determined by the directivity of the transmitter antenna DT and the effective receiver area AeR [6]. In this work we are especially interested in studying the effects of different link directionalities on the free space path loss. The directivity DT of a transmitter is defined as the ratio of the maximum power density to the power density of a completely isotropic transmission, as described by: n T T L PD pi ?? 4 ),( max?= (4.13) The directivity measures the confinement of electromagnetic energy in the direction of maximum radiation and can be computed as a function of the solid angle of the electromagnetic beam as: ?= pi4TD . (4.14) The solid angle ? can be computed in spherical coordinates as: )cos1(2 sin 2 0 0 ?pi??? pi ? ?==? ?? dd , (4.15) where ? is the half angle beam divergence [6] as illustrated in Fig. 4.5: 44 Figure 4.5: Directional wireless beam illustration. Note that for a completely isotropic transmission, described by a half angle beam divergence of pi radians, the solid angle is equal to 4pi, giving a directivity of 1. As soon as the electromagnetic energy is concentrated in smaller beams, the directivity increases reducing the free space path loss. When the half angle beam divergence is small enough 1<? . - Reassignment: this operation assigns each end host node k to the backbone node i that minimizes the link cost function uik for all Ni ??1 . For this purpose, we find the following value for each end host node k: Ni ukh kin ?? = 1 ),r,R(minarg)( i (6.20) in which )(khn represents the backbone node that provides coverage to the end host node k at iteration n, and iminarg represents the index i that corresponds to the minimum of )r,R( kiu for all Nj ??1 . Our main conjecture regarding the above iterations is that in each step of each type of the above iterations, the cost function remains constant or decreases. Note that the first operation decreases the cost function because it relocates a backbone node in the direction of the force, which is the opposite direction of the gradient of the cost function (Eq. 6.6). The second operation further reduces the cost because it reassigns a terminal node k from a backbone node i to another backbone node i?only if )r,R()r,R( kiki uu ?? , and such an operation either reduces the cost function or does not change its current value. 93 Also note that if we form the a sequence ,...,...,, )()2()1( nUUU with )(nU representing the values of cost function during the above iterations, then the above sequence is non-increasing and lower bounded (because 0)( >nU ). Therefore, this sequence has to converge to a value as n increases. Thus, the convergence criterion is stated as follows: ?iF ) Update terminal neighbor set t(i) Compute net force iF Relocate to ini1ni FRR ?+=+ End Figure 6.2: Force-driven mobility control algorithm. Note that the reassignment operation is executed by the terminal nodes, which send their decisions to their chosen backbone nodes. The backbone nodes then use this information to update their respective terminal neighbor sets. We use t(i) to refer to the set of terminal nodes assigned to backbone node i. Our last remark is on the value of ? . Recall that this value determines the relative importance of the two terms of the cost function. For example, if the backbone nodes run on batteries, long range power transmissions between neighbor backbone nodes is very power consuming and therefore a large value of ? is desirable. On the other hand, if we have plenty of power for each backbone node, for example through connection to the main power, a smaller value of ? should be used in the optimization problem. Also, the dynamics of the scenario have a strong influence on the choice of the value of ? . That is, when atmospheric obscuration is highly present and rapidly changing, a high value of ? allows for stronger backbone connectivity and robustness against failures which could disconnect the backbone network. On the other hand, in clear sky conditions a smaller value of ? can be used to improve network coverage while maintaining good backbone connectivity. Indeed, 95 in either case the mathematical formulation of the cost function and our optimization scheme is capable of modeling the problem. 6.5 Spring System In this section we present a quadratic optimization method for coverage and connectivity control in DWB-based networks in clear atmospheric conditions. We show that when the effects of atmospheric obscuration can be neglected, the cost function U for the network system is analogous to the potential energy of a spring system where wireless links are replaced by physical springs exerting forces on network nodes. We show that Hooke-type forces [53] can be defined at each backbone node, which drive the network topology to achieve energy minimizing configurations. 6.5.1 Quadratic optimization In clear atmospheric conditions we can neglect the effects of atmospheric obscuration ( 0=ij? ) and assume a path loss exponent of n = 2. Then the link cost uij becomes: 2 0 4 L k ADPu ij j eR i T j Rij 43421 pi= , (6.23) which is a quadratic function of L, the link distance. The link margin PR0 is determined by the receiver sensitivity and the turbulence induced fading as defined in 96 section 4.2.2. Initially, we assume the deployment area of the backbone nodes to share the same turbulence conditions and thus PR0 will not change with the location of the backbone nodes. The eRT AD pi4 constant will also be independent of the backbone nodes? locations and will be determined by the directivity of the transmitter antenna DT and the effective receiver area AeR . Thus, we can reformulate the link cost function as: 2 jiijij RRku ?= , where j eR i T j Rij ADPk pi4 0= , (6.24) which is analogous to the potential energy of a spring with spring constant ijk and displacement ji RR ? [53]. Using this link cost function (Eq. 6.24), we can model wireless links as springs which exert attraction forces between network nodes for energy minimization. The beauty of this model is that given the link margin PR0 and the receiver area eRA , the spring constant is inversely proportional to the transmitter directivity TD . Thus, directional wireless links which have high directivities translate into springs with low spring constants, which allow for higher link distances. On the other hand, omnidirectional wireless links use low directivity antennas associated with high spring constants that require much more energy to elongate. This result is very much in accordance with our network architecture, where directional wireless links are used to connect backbone nodes over large distances, whereas omnidirectional wireless links are used to connect each terminal node to its assigned base station. 97 Using the spring link cost model 6.13, the mobility control problem formulation becomes: ?? ? ?= = ??? ??? ? ??? ??? ? ? ? ?? ? ? ?+ ??? ? ??? ? ??= ??? == = o.w. 0 if 1 and ,4 where rRRR)R,...,R(min 0 1 2 )h()( 1 2 ji 1 N1 T(i,j)b ADPk kkbU ij j eR i T j Rij G M k kkkkh F N i ij N j ij pi ? 444 3444 214444 3444 21 (6.25) The goal of the optimization problem is to find the locations of all the backbone nodes that minimize the above cost function. A very interesting property of the above cost function is that due to its quadratic form it can be solved analytically, and the locations found by solving the optimization problem are always inside the network, given the convexity of the feasible region. Moreover, this cost function is analogous to the potential energy of an equivalent network with edges replaced by springs, with spring constants as defined in Eq. 6.24. Thus, we can model the DWB network as a spring system whose potential energy is analogous to the communication cost of the DWB network. In a spring system, nodes move according to the forces exerted by the springs attached to them until reaching an equilibrium configuration where the net force on each node is equal to zero [53]. The equilibrium configuration is also the configuration that minimizes the potential energy of the spring system. Note that the above cost function is not mutually convex. Thus, to increase the confidence margin of optimality of the solution, a perturbation method is used. The perturbation is applied several times after each time that the algorithm converges. If 98 the force-driven algorithm converges to the same solution after a certain number of times (typically, 2-3 times) the corresponding solution is chosen as a global optimal solution with a high degree of confidence. In the following section, we derive the force-driven mobility control algorithm for the spring system model. 6.5.2 SPRING algorithm As explained in section 6.3, the value of the net force at backbone node i is computed as the gradient of the energy function U with respect to the location the backbone node Ri and can be described as: ?? == =+=+= M k ikk N j ij ihb 1 )(ij 1 c i b ii f)(1fFFF ?? (6.26) where ijf is described using Eq. 6.15 as: ij RR ji RR 0ij RRR2 4f jiji ? ? ?? ? ? ?+?? ? ? ??? ?= ?? ijij ee ADP ijjeRjT j R ?? ?pi (6.27) Note that in the case of the spring system, 0=ij? for all i, j, thus ijf becomes: ijij0ij R2R2 4f ijj eR j T j R kADP =??? ? ??? ?= pi (6.28) with ijk as described in 6.24. Note that the force ijf in 6.28 is a weighted average of the distance vectors between backbone node i and its neighbors. This result is in agreement with the behavior of an analogous spring system, where nodes react based 99 on forces exerted by neighbor nodes and move in the direction of the weighted average position of its neighbors. Note that the force on a given backbone node only depends on the location of its neighbors. Thus, a completely distributed algorithm can be designed where each backbone node reacts locally to the forces exerted by neighbor nodes, providing scalability and robustness. No centralized global information is needed. Each backbone node can make movement decisions by itself informed by purely local information and the overall network achieves global optimal configurations. The SPRING optimization algorithm can be derived from the general methodology described in section 6.3, which is based on two main operations: relocation and reassignment. Recall that the relocation operation uses the value of the force to find the node?s new location, as: i n i 1n i FRR ?+= + . Using Eq. 6.9 for the net force on backbone node i, iF , the relocation operation is described as: ?? ? ?? ? =++= ?? == + M k ikkij N j ij fihfb 1 )( 1 n i 1n i )(1RR ?? . (6.29) For the spring system case, using Eq. 6.28, the above operation becomes: ?? ? ?? ? =++= ?? == + M k ikikkijij N j ij kihkb 1 n )( n 1 n i 1n i R)(1R2RR ?? (6.30) Note that the new location found using 6.30 is one step size in the path between the current location of node i and the weighted average of the location of its neighbors, with weights defined by the spring constants kij. 100 The reassignment operation was also described in section 6.3 as: Niukh kin ??= 1for ),r,R(minarg)( i , where h(k) denotes the index of the backbone node assigned to terminal node k. Using the expression for the link cost in Eq. 6.24, the reassignment operation for the spring algorithm becomes: Ni kkh ikn ?? ?= 1 rRminarg)( 2kii (6.31) The SPRING algorithm thus follows the same form as the general force- driven mobility control algorithm illustrated in Fig. 6.2: For each backbone node i While ( ?>iF ) Update terminal neighbor set t(i) Compute net force iF Relocate to ini1ni FRR ?+=+ End where now the force iF is defined by Eqs. 6.9-6.15. 6.5.3 Simulation results In order to gain more insight on the problem and verify the performance of our optimization algorithm, we present results from simulation studies with different design parameters. 101 In our initial simulations, N terminal nodes are distributed in a 100x100 two dimensional plane. Terminal nodes are organized in clusters. The first terminal node is placed in the plane according to a uniform random distribution. Each other terminal is placed within clusterRange of the previous terminal node with probability p_cluster, and uniformly in the 100x100 plane with probability 1-p_cluster. Next, M backbone nodes are placed at random in the plane and an initial ring topology is built connecting all backbone nodes. Then, the SPRING algorithm is executed to make backbone nodes adjust their position until convergence to the optimal backbone configuration. Before we report quantitative results, we first present several figures to visually illustrate the effectiveness of the mobility control algorithm. Fig. 6.3 shows results for a network with 100 terminal nodes and 10 backbone nodes. The values used for the variables clusterRange and p_cluster are 10 and 0.2 respectively. The backbone nodes are labeled and the links between them are shown in thick dotted lines. Links from each terminal node to its closest backbone node are shown in thinner dotted lines. Fig. 6.3a shows the initial non-optimal network configuration. Fig. 6.3b shows the resulting network configuration after running the mobility control algorithm with a balancing factor 1=? . In this case, the low value of ? allows backbone nodes to move close to the terminal nodes to optimize network coverage at the expense of low backbone connectivity. Figs. 6.3c and 6.3d show the resulting network configurations with 5=? and 10=? respectively. The higher value of ? the more weight is put on the backbone connectivity objective thus making the backbone nodes move closer to 102 each other. Finally, Figs. 6.3e and 6.3f show the resulting network configurations for 20=? and 30=? , where stronger backbone networks are produced at the expense of lower network coverage. In Fig. 6.4 we show a network with 20 backbone nodes. The number of terminals remains 100 and they are randomly placed according to the procedure explained above. As seen in Fig. 6.4, the increased number of backbone nodes allows more flexibility to optimize network coverage with less penalization on backbone connectivity, and vice versa. 103 Figure 6.3: Initial non-optimal configuration (a) and optimal network configurations (b, c, d, e) after running the SPRING mobility control algorithm for different values of ? (10 backbone nodes). 104 Figure 6.4: Initial non-optimal configuration (a) and optimal network configurations (b, c, d, e) after running the SPRING mobility control algorithm for different values of ? (20 backbone nodes). 105 In order to quantitatively show the performance of our mobility control algorithm, we computed the coverage and connectivity cost metrics for the Pareto optimal network configurations obtained. Again, we considered networks with 100 terminal nodes and with 10 and 20 backbone nodes respectively. We used the following set of weights: 0.01, 0.3, 1, 3, 5, 10, 15, 20, 25, and 30, to generate 10 Pareto optimal solutions for the networks under study. Fig. 6.5 shows the Pareto optimal curves obtained. The x axis represents the coverage cost metric G, while the y axis represents de connectivity cost metric F. We used FSO links for the backbone-to- backbone links with 2 mrad half beam divergence and RF links for the terminal-to- backbone links with 4/pi rad half beam divergence. The minimum required received power used was -45 dBm (31.6 nW) for all network nodes. The values of F and G obtained were normalized and scaled for the plot in Fig. 6.5. Since the algorithm is solving a multi-objective optimization problem, optimal solutions, which combine low values of both cost metrics, must lie in the south-west corner of the solution space, as shown in Fig. 6.5. Note that the increased number of resources (base stations or backbone nodes) allows for improved Pareto optimization, as shown by the deeper south-west configuration of the Pareto optimal curve associated with the 20 backbone node network in the solution space. Fig. 6.5 also shows the limit on the network coverage cost metric. As we lower the weight on backbone connectivity, the network coverage cost decreases until reaching a point where no further improvement is possible for the given number of backbone nodes. As expected, when using 20 backbone nodes, network coverage can be further optimized due to the increased number of resources. The backbone connectivity cost 106 metric, on the other hand, can be brought to zero by increasing the balancing factor ? , which would lead to a network configuration where all backbone nodes converge into a single point. As seen in Fig. 6.5, both curves tend to zero as the weight on backbone connectivity is increased. Figure 6.5: Pareto Optimal set of solutions (10 and 20 backbone nodes). In order to show the self-organizing capability of our network system, we developed a simulation environment that outputs video sequences of dynamic network scenarios. The objective is to show that our self-organized network system is able to track the network dynamics. 107 As explained in Chapter 3, uncontrollable parameters such as the mobility of the terminal nodes and the atmospheric conditions constitute the network dynamics, which are modeled as external excitations to the network system. In this section, we assume clear atmospheric conditions and thus the scenario dynamics is based on the mobility of the terminal nodes. We first place N terminal nodes organized in clusters in a two dimensional plane following the procedure introduced earlier in this section. We then use the Reference Point Group Mobility (RPGM) model [54] to move the terminal clusters in the plane and show how the backbone system is able to react to the mobility of the terminal nodes driven by local forces that minimize the energy of the network system. First, in Fig. 6.6, we show a sequence of snapshots of the evolution of the network form an initial non-optimal configuration to the optimal configuration driven by local forces computed using the SPRING algorithm. In 6.6a we show the initial placement of the terminal nodes. In this case, 100 terminal nodes are placed in a 50km x 50km plane. These terminal nodes constitute the demand for broadband connectivity. For that purpose, a ?squat team? of backbone nodes are dropped in the area in order to form a backbone network to interconnect the terminal nodes. Fig. 6.6b shows the initial placement of the backbone nodes. The backbone nodes are deployed at an altitude of 0.5km. Fig. 6.6 shows 2D projections of the 3D scenario. Next, in Fig. 6.6c the backbone nodes form an initial backbone topology. We use ring topologies to assure resilience through bi-connectivity (as explained in Chapter 5). Fig. 6.6d shows the result of the initial reassignment step and the computation of the forces that arise at each backbone node. The green solid lines at each backbone node 108 represent the amplitude and direction of the force. Figures 6.6e through 6.6h show the resulting backbone configurations after several iterations of the force-driven mobility control algorithm. Note how the backbone nodes move in the direction of the net force at their respective locations until the net force is small enough. Recall that the SPRING algorithm converges when Ni1for Fi ??