RELIABLE AND EFFICIENT COMMUNICATIONS IN WIRELESS SENSOR NETWORKS By Mai M. Abdelhakim A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of Electrical Engineering - Doctor of Philosophy 2014 ABSTRACT RELIABLE AND EFFICIENT COMMUNICATIONS IN WIRELESS SENSOR NETWORKS By Mai M. Abdelhakim Wireless sensor network (WSN) is a key technology for a wide range of military and civilian applications. Limited by the energy resources and processing capabilities of the sensor nodes, reliable and efficient communications in wireless sensor networks are challenging, especially when the sensors are deployed in hostile environments. This research aims to improve the reliability and efficiency of time-critical communications in WSNs, under both benign and hostile environments. We start with wireless sensor network with mobile access points (SENMA), where the mobile access points traverse the network to collect information from individual sensors. Due to its routing simplicity and energy efficiency, SENMA has attracted lots of attention from the research community. Here, we study reliable distributed detection in SENMA under Byzantine attacks, where some authenticated sensors are compromised to report fictitious information. The q-out-of-m rule is considered. It is popular in distributed detection and can achieve a good trade-off between the miss detection probability and the false alarm rate. However, a major limitation with this rule is that the optimal scheme parameters can only be obtained through exhaustive search. By exploiting the linear relationship between the scheme parameters and the network size, we propose simple but effective sub-optimal linear approaches. Then, for better flexibility and scalability, we derive a near-optimal closed-form solution based on the central limit theorem. It is proved that the false alarm rate of the q-out-of-m scheme diminishes exponentially as the network size increases, even if the percentage of malicious nodes remains fixed. This implies that large-scale sensor networks are more reliable under malicious attacks. To further improve the performance under timevarying attacks, we propose an effective malicious node detection scheme for adaptive data fusion; the proposed scheme is analyzed using the entropy-based trust model, and has shown to be optimal from the information theory point of view. Next, we observe that: while simplifying the routing process, a major limitation with SENMA is that data transmission is limited by the physical speed of the mobile access points (MAs) and the length of their trajectory, resulting in low throughput and large delay. To solve this problem, we propose a novel mobile access coordinated wireless sensor network (MC-WSN) architecture. The proposed MC-WSN can provide reliable and time-sensitive information exchange through hop number control, which is achieved by active network development and topology design. We discuss the optimal topology design for MC-WSN such that the average number of hops between the source and its nearest sink is minimized, and analyze the performance of MC-WSN in terms of throughput, stability, delay, and energy efficiency by exploiting tools in information theory, queuing theory, and radio energy dissipation model. It is shown that MC-WSN achieves much higher throughput and significantly lower delay and energy consumption than that of SENMA. Finally, motivated by the observation that the number of hops in data transmission has a direct impact on the network performance, we introduce the concept of the N-hop networks. Based on the N-hop concept, we propose a unified framework for wireless networks and discuss general network design criteria. The unified framework reflects the convergence of centralized and ad-hoc networks. It includes all exiting network models as special cases, and makes the analytical characterization of the network performance more tractable. Further study on N-hop networks will be conducted in our future research. Copyright by MAI M. ABDELHAKIM 2014 Dedicated to my dear parents and to my beloved husband. v ACKNOWLEDGMENTS I would like to express my sincere appreciation and gratitude to my advisor, Prof. Tongtong Li, for her guidance and support throughout the years of my PhD studies at Michigan State University. The experience I gained while working with Prof. Li is extremely rewarding. I learned a lot from her broad knowledge and insightful comments. Also, I have always appreciated her thoughtfulness and kindness that have created a family-like atmosphere in her research group. It is certainly an honor to have worked with Prof. Li. I would like to thank Prof. Hassan Khalil, Prof. Selin Aviyente, and Prof. Guoliang Xing for serving on my committee, and for their helpful comments and insightful discussions. Thanks to Prof. Jian Ren for his valuable insights and suggestions on securityrelated issues in research. Thanks to Prof. Hyder Radha for supporting my application at Michigan State University, and for nominating me for the graduate office fellowship in the first year of my PhD program. I am blessed with a wonderful family without whom this work would not have been possible. I would like to express my profound gratitude to my parents for their endless love and encouragement. They have always motivated me to excel, and have strived to help me achieve my goals since I was a child. I could not be more grateful to my husband, Mostafa, for being the loving, caring, and supportive person that he is. Without him, my life would not have been complete or enjoyable, and this dissertation would not have been written. vi TABLE OF CONTENTS LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Overview of Wireless Sensor Networks . . . . . . . . . . . . 1.1.1 Sensor Technology . . . . . . . . . . . . . . . . . . . . . 1.1.2 Sensor Network Structures . . . . . . . . . . . . . . . . 1.2 Performance Measures in Wireless Sensor Networks . . . . 1.3 Reliability and Security . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Possible Attacks . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Existing Techniques for Malicious Attacks Mitigation 1.4 Major Contributions of the Dissertation . . . . . . . . . . . . Chapter 2 Distributed Detection in Mobile Access Wireless Networks Under Byzantine Attacks . . . . . . . . . 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . 2.2.1 Overall System Set-Up . . . . . . . . . . . . . . . 2.2.2 Modeling of Possible Attack Strategies . . . . . . 2.2.3 Problem Formulation . . . . . . . . . . . . . . . . 2.3 Simplified Data Fusion Scheme - The Linear Approach 2.3.1 Observations . . . . . . . . . . . . . . . . . . . . . 2.3.2 The Linear Approach . . . . . . . . . . . . . . . . 2.3.3 Enhanced Linear Approach . . . . . . . . . . . . . 2.4 A Closed-form Solution . . . . . . . . . . . . . . . . . . . 2.5 Analytical Bounds for the Proposed Approaches . . . . 2.6 Malicious Node Detection and Adaptive Fusion . . . . 2.6.1 The Malicious Node Detection Scheme . . . . . 2.6.2 The Adaptive Fusion Algorithm . . . . . . . . . . 2.6.3 Analysis From the Entropy Point of View . . . . 2.7 Simulation Results . . . . . . . . . . . . . . . . . . . . . . 2.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . 1 . 1 . 3 . 5 . 8 . 8 . 10 . 12 Sensor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 16 20 20 22 23 27 27 29 30 32 37 41 42 44 45 49 58 Chapter 3 Mobile Access Coordinated Wireless Sensor Networks – Design and Analysis . . . . . . . . . . . . . . . . . . . . . . . . 59 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 vii 3.2 3.3 3.4 3.5 3.6 3.7 3.1.1 Related Work on Network Performance Analysis – Throughput, Stability, and Delay . . . . . . . . . . . . . . . . . . . 65 The Proposed Mobile Access Coordinated Wireless Sensor Network (MC-WSN) . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.2.1 General Description . . . . . . . . . . . . . . . . . . . . . . 70 3.2.2 Major Features . . . . . . . . . . . . . . . . . . . . . . . . . 72 Network Topology Design . . . . . . . . . . . . . . . . . . . . . . 74 Throughput Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.4.1 Definition of the Throughput . . . . . . . . . . . . . . . . 76 3.4.2 Multihop Single Path Routing Case . . . . . . . . . . . . 78 3.4.3 Multihop Multipath Routing Case . . . . . . . . . . . . . 84 3.4.4 Total Network Throughput . . . . . . . . . . . . . . . . . . 85 System Stability and Delay Analysis . . . . . . . . . . . . . . . . 85 3.5.1 Queue Independence Assumption and Modeling Theorems 86 3.5.1.1 Klienrock Independence Assumption . . . . . . . 86 3.5.1.2 Burke’s Theorem and Little’s Theorem . . . . . 87 3.5.2 Queuing Model Characterization for MC-WSN . . . . . . 88 3.5.2.1 Modeling the Arrival and Service Processes . . . 88 3.5.2.2 Calculation of Arrival and Service Rates . . . . . 89 3.5.3 Stability Analysis . . . . . . . . . . . . . . . . . . . . . . . 93 3.5.4 Delay Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 95 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 Chapter 4 N-Hop Networks – A General Framework for Wireless Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 The Evolution of Wireless Communication Systems . . . . . . . 4.2.1 Cellular Systems . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Ad-hoc Networks . . . . . . . . . . . . . . . . . . . . . . . . 4.2.3 The Merging Ground for Cellular and Ad-hoc – Hybrid Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 General Design Criteria . . . . . . . . . . . . . . . . . . . . . . . 4.4 The Concept of N-hop Networks . . . . . . . . . . . . . . . . . . 4.5 Analytical Evaluation of the Network Performance . . . . . . . 4.5.1 Throughput . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5.2 Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5.3 Energy Efficiency . . . . . . . . . . . . . . . . . . . . . . . 4.6 Security Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . 4.6.1 Delay-assisted Network Failure/Attack Detection . . . . 4.6.2 Access Authentication: Accountability and Privacy Protection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii 105 106 106 107 108 108 110 112 115 115 122 123 124 124 127 128 Chapter 5 Conclusions and Future Work . . . . . . . . . . . . . . . . . . 129 5.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 5.2 Discussions for Future Work . . . . . . . . . . . . . . . . . . . . . 131 APPENDICES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 Appendix A Transmission Probability – Proof of Lemma 3.1 . . . . 134 Appendix B Traffic Load Calculations used in Proposition 3.3 . . . 137 BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 ix LIST OF TABLES Table 2.1: Adaptive fusion with malicious node detection . . . . . . . . . 46 Table 2.2: Equivalence between the entropy based trust model and the proposed malicious node detection . . . . . . . . . . . . . . . . 49 x LIST OF FIGURES Figure 2.1: SENMA under Byzantine attack. . . . . . . . . . . . . . . . . . 20 Figure 2.2: The false alarm rate and miss detection probability when n = 30, k = 10, Pa,f = Pa,m = 1, Pf = 0.1, and Pd = 0.775. . . . . 26 Optimal scheme parameters (mo , qo ) versus the network size at different percentage of malicious nodes (α) and different probability of attack (Pa ), when β = 0.01, Pf = 0.1, Pd = 0.775, Pa,m = Pa,f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Figure 2.4: The enhanced linear approach at α = 25%. . . . . . . . . . . . 31 Figure 2.5: The q obtained using linear approach, enhanced linear approach and closed-form solution. Here, the percentage of malicious sensors α = 25%, Pa,m = 1, Pa,f = 1, Pd = 0.775, and Pf = 0.1. 37 Figure 2.6: The trust metrics (T rustf (i)/T rustm (i)) vs. the Pˆa,f (i)/Pˆa,m (i). 48 Figure 2.7: CDF of Pa for dynamic attack strategy with ∆1 = ∆2 = 0.2, initial Pa1 =0.7, Px = 0.5. . . . . . . . . . . . . . . . . . . . . . 50 The false alarm rate and miss detection probability using the linear approach. . . . . . . . . . . . . . . . . . . . . . . . . . . 52 The false alarm rate and the miss detection probability using the enhanced linear approach, and comparisons with AND rule, OR rule and majority voting rule. In general, AND rule results in very high miss detection probability, although it can achieve low false alarm rate. On the other hand, OR rule results in a very high false alarm rate, although it can achieve low miss detection probability. . . . . . . . . . . . . . . . . . . . . . . . 53 Figure 2.10: The false alarm rate and miss detection probability under static and dynamic attacks with and without the malicious node detection scheme. . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Figure 2.3: Figure 2.8: Figure 2.9: xi Figure 2.11: The malicious node detection false alarm rate ηf vs. the observation threshold Nth for static and dynamic attacks, when n = 30 and α = 25%. The results are the average of N = 103 observations, each is further averaged over 103 iterations. . . . Figure 2.12: The effect of the observation interval (N ) on the detection accuracy ηd and the false alarm rate ηf for static and dynamic attacks using Nth = 100 and n = 30. The results are averaged over 4 × 103 iterations. . . . . . . . . . . . . . . . . . . . . . . 56 57 Figure 3.1: Proposed MC-WSN architecture. . . . . . . . . . . . . . . . . . 71 Figure 3.2: MC-WSN with four powerful RCHs. . . . . . . . . . . . . . . . 76 Figure 3.3: Multihop single path between node i and sink k. . . . . . . . . 79 Figure 3.4: O . . . . . . . . . . . . . . . . . . . . . . . . Model of CH i ∈ gh,k 92 Figure 3.5: Average number of hops from a CH to its nearest sink versus the number of RCHs (K), when dc = 200m and Rc = 30m. . . 98 Figure 3.6: Average per node throughput in packets per slot vs. the cell radius for MC-WSN and SENMA. Here, K = 6, VM A = 30m/s, ¯ ρSN = 0.0283, ρCH = 0.0014, SN R = NP Rc −β = 8dB, o Nintf = 2, Rc = 30m, rc = 15m, and Tslot = 25.6ms. . . . . . 100 Figure 3.7: Upper bound on packet generation rate in each cluster (λ) for MC-WSN when dc = 200m, NCH = 200, and K = 6. . . . . . . 101 Figure 3.8: Average delay of MC-WSN and SENMA vs. received SN R. Here, dc = 200m, NCH = 200, K = 6, and VM A = 30m/s. . . . 102 Figure 3.9: The energy dissipation (J/bit) vs. the number of SNs in the MC-WSN and SENMA networks, when dc = 100m, rc = r = 15m, HS = 10m, β = 2, Etx = Erx = 50 nJ/bit, and � = 10 pJ/bit/m2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Figure 4.1: Merging of centralized and ad-hoc networks. . . . . . . . . . . 110 Figure 4.2: A 3-hop mobile network. . . . . . . . . . . . . . . . . . . . . . 114 xii Figure 4.3: Per-node throughput T (i|Ni , Pi ) vs. the average transmit power per noise power ratio for different number of hops, assuming AWGN channel, path loss exponent is 4, SINR threshold is γ = 5dB, the hops are equidistant, distance between transmitter and receiver is normalized to 1m. The transmit power is exponentially distributed. . . . . . . . . . . . . . . . . . . . . 118 Figure 4.4: Optimal number of hops obtained by rounding (4.4) to the nearest integer. Here, γ = 5dB. . . . . . . . . . . . . . . . . . . . . 119 Figure 4.5: Routing flexibility: Scenario 1: BN i and BN j communicate directly. Scenario 2: BN i and BN l communicate through RS r. Scenario 3: BN i and BN m communicate through RS r and the BSs k and q. . . . . . . . . . . . . . . . . . . . . . . . . . . 120 Figure 4.6: The energy dissipation (J/bit) vs. the number hops in N-hop MC-WSN, and comparison with the single hop SENMA network. Here, we set the cell radius dc = 100m; for the MC-WSN, the per-hop distance for CHs is 30m; for SENMA, the per-hop distance and the MA coverage radius are equal to 10m; the path loss exponent β = 2, n = 2000, Etx = Erx = 50 nJ/bit, and �pa = 10 pJ/bit/m2 . . . . . . . . . . . . . . . . . . . . . . . . . 125 xiii Chapter 1 Introduction In this chapter, first, a brief overview of wireless sensor networks is provided, illustrating the sensor technology and different network structures. Second, vital performance measures in wireless sensor network design are presented. Third, security and reliability aspects are discussed, pointing-out different security threats and possible countermeasures. Finally, the main contributions of this dissertation are highlighted. 1.1 Overview of Wireless Sensor Networks Wireless sensor networks (WSNs) have received significant attention form the research community, due to their potential impact on various applications [1–3]. WSNs were initially motivated by military reconnaissance and surveillance applications. Currently, they have been identified as key enabling technology for various civilian applications as well, such as environmental monitoring, emergency response, smart transportation systems, and target tracking. In the following subsections, the sensor technology is presented, then different network structures that can be adopted in WSNs are discussed. 1.1.1 Sensor Technology In 1980s-1990s, sensor networks were recognized as an essential component in warfare, where sensors were deployed for collaborative detection, reconnaissance, and surveillance purposes [4]. For example, employing a system with multiple radars to collect 1 information about air targets. At that time, sensors’ sizes were large and they had separate units for sensing, processing, and communications. During the last two decades, along with the advancements in microelectromechnical systems (MEMS), a tremendous improvement in sensors technology has been witnessed. Now, smaller and cheaper sensors are widely available. Each sensor has an integrated sensing, data processing, and wireless communications units. The sensors platforms can be generally classified into: specialized sensors, generic sensors, high-bandwidth sensors, and gateway-class sensors platforms [5, 6]. The specialized sensors are tiny low-cost sensors with the most constraint resources. Asset tags are examples of specialized sensors. The generic sensors are more powerful than specialized sensors and can serve as their data collectors. Examples on generic sensors can be found in [6–9]. Specialized and generic sensors run an operating system called TinyOS, which is capable of operating on platforms having limited memory and processing capabilities [5]. Among the generic sensor nodes, MICA platforms are very common. They include the MICA2, MICA2DOT, and MICAz platforms. Both MICA2 and MICAz have the IEEE 802.15.4/Zigbee compliant transceiver. The MICA2 [10] platform can be employed in large-scale sensor networks (networks with more than 1000 sensors), security, and surveillance applications. Its RF transmit power ranges from −20dBm to 5dBm, and its receiver sensitivity is −98dBm. The outdoor transmission range is 500ft under a line of sight (LOS) transmission. It operates in the 868/916MHz band and supports data rate of 38.4Kbps. The MICA2 sensor’s size is 36mm × 48mm × 9mm. The MICA2DOT sensor has a coin-sized form of diameter 25mm; its platform is mostly similar to that of MICA2 [11]. The MICAz platform can be utilized in indoor building monitoring and security applications, as well as large-scale WSNs [12]. Its transmission power ranges from 2 −24dBm to 0dBm, and its receiver sensitivity is −94dBm. The outdoor RF transmission range is 75m to 100m with LOS transmission, while the indoor RF range is 20m to 30m. The MICAz RF technology operates in the 2400MHz to 2483.5MHz band and its data rate is 250Kbps. The MICAz sensor’s size is 58 × 32 × 7mm excluding the battery pack. In both MICA2 and MICAz sensors, the power is supplied through two AA batteries. The high-bandwidth sensing platforms provide higher data rate and have more computational capabilities than generic sensor platforms. For example, the “imote” platform, which is developed by Intel [5], supports data rate of 723.2Kbps [6] and its communication range is 30m [13]. The imote incorporates ARM processor and is based on the Bluetooth technology that uses the frequency-hopping spread spectrum technique. The power in the imote is supplied through three AA batteries with recharging capability [7]. Highly powerful sensor platforms are enabled through gateway-class platforms, such as the Intel Stargate platform [5]. Gateway nodes provide links between the sensor network and the conventional infrastructure support, such as Ethernet and WiFi. Stargate is based on Intel XScale (32-bit) microcontroller and has IEEE 802.11b RF module, which supports data rate of 1 − 11Mbps [6]. Stargate-class sensors run Linux operating system [5]. 1.1.2 Sensor Network Structures In WSNs, generally the sensors report their readings to a central unit or a sink for processing and final decision making. Due to the limited communication range and power resource of sensors, direct (one-hop) transmissions from a source to its intended destination or a sink might not be possible, especially in fixed large-scale networks. Allowing multihop data transmissions through intermediate relays would solve this 3 problem and would achieve effective data delivery. The network structure defines how information is exchanged in the network. Network structures can be generally divided into two categories: (i) distributed or ad-hoc networks, which are virtually structureless (ii) centralized networks with welldefined infrastructure. In ad-hoc networks, there are no prior established routes for data transmission; therefore, the transmission process is random, and theoretically the number of hops can be infinite. In structured network, high-level controllers (such as base stations) are employed to coordinate the network and assist data transfer. In this case, data transfer can go through defined routing paths that are usually established during the network set-up phase. Under normal network conditions, the number of hops along a route from a source to a sink is bounded. There is also a trend to blend ad-hoc and centralized network models together, resulting in various hybrid network models [14, 15]. For example, in [15], the transmission is made in an ad-hoc mode only if the number of hops is below a certain limit; otherwise, the transmission is made through the centralized base stations. Another representative example is the clustered wireless sensor networks, where the sensors are grouped into clusters with each cluster managed by a cluster head in a centralized manner [16]. The cluster heads are then responsible for routing the information. Along with the advancements in remote control technologies, Unmanned Aerial Vehicles (UAVs) have been utilized in wireless sensor networks for data collection. For example, in Sensor Networks with Mobile Access points (SENMA) [17], powerful mobile access points (MAs) traverse the network to establish direct communications with each sensor node. In [18], mobile relays are exploited, where each cluster is served by a mobile relay that collects data from its cluster members at predefined locations, then travel over almost a straight line trajectory to send the data to the sink. In [19], multiple locations for data collection (referred to as rendezvous points) are defined, 4 such that a mobile sink visits the predefined locations and stays at each location for a certain amount of time before it leaves to the next location. In this case, there are three states for the mobile sink, namely, traveling state, waiting state, and data collecting (or harvesting) state. The case when multiple mobile sinks are employed is also investigated in [19]. In many applications, the information transmitted over WSN is critical and timesensitive. For example, detecting a target in a battlefield, detecting a fire in a building, or monitoring radiation level in the air [20]. Hence, the reliability and efficiency of information generation, transmission, and retrieval is crucial in WSN. In Section 1.2, several vital performance measures and aspects in wireless sensor networks design are presented. Then, in Section 1.3, reliability and security issues that threaten the functionality of a network are discussed. 1.2 Performance Measures in Wireless Sensor Networks Vital performance measures in wireless sensor networks are summarized in the following. • Throughput The throughput is an important measure of the network per- formance, as it indicates the amount of information that can be successfully communicated over a network. A throughput of a node is feasible if there exists a communication protocol such that the average transmission rate of a node is equal to its throughput. Throughput affects the buffer dynamics in the nodes [21], and consequently has a direct influence on the stability of the network as well as the delay performance. 5 The adopted network model largely impacts the performance of the system. For example, in random ad-hoc networks with multiple source-destination pairs, it was shown in [22] that the average throughput of a node vanishes as the number of nodes in the network increases. More specifically, when n is the total number of nodes in the network and W is the maximum rate on any link, then the � � W . This indicates that for efficient throughput obtained by each node is O √ n communications, the network should not be completely structureless. The throughput of regularly-structured canonical network is considered in [23], and it was shown that proper routing is needed to improve the throughput performance in multihop transmissions. In [24], throughput of multihop many-toone network with uniformly deployed nodes and time division multiple access (TDMA) protocol is investigated, and the effect of clustering the network on improving the throughput performance is discussed. Cooperative transmissions and coding at intermediate hop levels can improve the network throughput [25–27]. In [25, 26], the achievable rate of relay channels is provided, where the destination receives the transmitted signal from the source as well as from the intermediate relay(s), then performs joint decoding. In sensor networks, due to the limited communication range and power resource of the sensors, it may not be possible to have the destination receive direct signals from the sources. Direct transmissions would also result in an increased interference region, which would reduce the spectral efficiency of the network. Allowing nodes to be mobile could improve the throughput performance compared to fixed networks. In [28], the packet stream at the source node is split over multiple mobile relays that in turn deliver the packets to the destination as they get within its communication range. This approach relies on the diversity 6 and mobility to improve the throughput, at the cost of increased delay and energy consumption. When the sinks or access points are mobile, like in SENMA, the capacity of a node having a direct communication with the sink could be significantly superior to that of ad-hoc sensor networks [17]. However, since the sources wait for an access point’s visit, the throughput is limited by the traversal speed and trajectory length of the access point. In [19], the throughput of a network with mobile sinks is investigated, and the effect of the speed of the sink and its trajectory length on the throughput is highlighted. • Delay The delay is the time consumed until the sensing information is delivered to the destination/sink. It is composed of: transmission delay, processing delay, queuing delay, and data propagation delay along the routing path(s) from the source to its destination. The transmission delay depends on the data rate and the packet size; the processing delay depends on the processing speed in the nodes; the queuing delay depends on the traffic pattern characterizing the buffer dynamics at the nodes; the wireless medium propagation delay depends on the distance between the transmitting and receiving ends as well as the EM wave speed (speed of light). For time-sensitive applications, it is crucial to design a network that achieves the required delay performance. In order to guarantee the delay requirement of data transmission over a network, sufficient network control is essential. Proper architecture, topology design, and transmission protocols are needed to assist in balancing the network traffic load and in guaranteeing time-sensitive information exchange. • Energy Efficiency and Network Lifetime 7 Due to the limited energy supply of sensor nodes, energy efficiency is a fundamental concern in wireless sensor networks. Hence, it is essential to design energy-efficient architectures and protocols to prolong the network lifetime. The transceiver module is the primary source of energy consumption. Therefore, the routing functions highly contribute to the nodes’ power depletion, where each node does not only transmit its packets, but also transmits and receives other nodes’ packets to deliver them to the intended destination. Note that SENMA architecture significantly improves the energy-efficiency compared to random ad-hoc networks, since sensors are relieved from the energy-consuming routing functions [17]. Energy consumption determines the network lifetime. There are several definitions for the network lifetime in the literature. In [29], the lifetime is defined as the time until any sensor in the network depletes its energy, or a fraction of the sensors deplete their energy and become nonoperational. In [30], the lifetime is defined as the time until full coverage of the network is no longer provided. 1.3 Reliability and Security The network should be fast-reacting and self-healing not only to node/link failure conditions that could result from node’s power depletion and rough environmental conditions, but also to malicious attacks. This section presents some threats to sensor network operations, and briefly discusses possible countermeasures. 1.3.1 Possible Attacks Wireless sensor networks are vulnerable to various types of malicious attacks that can severely disrupt the network performance. The malicious attacks in wireless sensor 8 networks can be classified into two categories: 1. Internal attacks, which are launched by authorized nodes that are compromised by an external intruder. An internal attacker can perform arbitrary behavior to harm the network, such as: • Send fictitious sensing reports to the central processing unit or the sink. This is known as Byzantine attack [31]. • Claim different nodes’ identities. This is known as Sybil attack [32]. • Launch routing attacks, which include dropping and/or modifying packets as they are being relayed to the destinations through multihop transmissions. For example, a serious threat to WSN is the known as Sinkhole attack, where the malicious nodes attract traffic by modifying their routing metrics, then perform selective forwarding, drop, or modify packets [33]. • Intentionally collide with benign nodes’ traffic, resulting in retransmissions and power exhaustion of benign nodes. This attack can be regarded as a special type of jamming. 2. External attacks, which are launched by non-authenticated nodes that intentionally intercept and/or disrupt the network operation. External attacks can be further divided into two categories: • Passive attacks, such as eavesdropping, traffic interception and analysis. • Active attacks, such as jamming, where the attackers transmit high power signals to interfere with the network traffic. 9 1.3.2 Existing Techniques for Malicious Attacks Mitigation Internal attacks are more difficult to detect and counteract as compared to external attacks. Cryptographic algorithms, such as authentication and encryption, can counteract most of the external attacks, with exception to jamming [34]. In the following, possible countermeasures that combat some malicious attacks are discussed. For Byzantine attacks: Recall that in Byzantine attacks some authenticated nodes send false sensing reports to the processing unit or the sink. Byzantine attacks cannot be detected through cryptographic approaches. One way to combat these attacks is through distributed detection, where many nodes collaborate to sense the same phenomenon or target and report their measurements to a central processing unit for data fusion. The data fusion rule should be well designed to ensure reliable decisionmaking, even if some of the received information is fictitious. We consider distributed detection in SENMA networks under Byzantine attacks in Chapter 2. For Sybil attacks: A malicious node launching Sybil attack can claim different identities to confuse the processing unit. A node-to-node authentication with locationbased keys is proposed in [35] to combat Sybil attacks. In this location-based authentication approach, the keys used in the authentication process are based on the nodes’ identifications (IDs) as well as their location. Hence, a node launching Sybil attack would be identified. For Sinkhole attacks: In a Sinkhole attack, the malicious nodes attract network traffic by modifying their routing metrics, then drop or modify the information as it is being routed to the sink. Location-based authentication can mitigate Sinkhole attacks only if the routing metric is based on the location, and not on the remaining energy or link reliability [35]. Like Byzantine attacks, generally Sinkhole attacks could not be detected through cryptographic means solely. In [36], Sinkhole attacks are detected through monitoring the CPU usage of the nodes; This scheme requires each node to 10 periodically report its actual CPU usage to a centralized entity, which in turn could identify the malicious nodes. Mitigating Sinkhole attacks through evaluating a trust metric for each node is discussed in [37], where both entropy-based and probabilitybased trust models are presented for trust evaluation. For eavesdropping and traffic analysis: Incorporating information encryption in WSNs is essential to thwart eavesdropping and traffic analysis or render them ineffective. The encryption process is classified into two categories, namely, symmetrickey encryption and asymmetric-key (or public key) encryption. In symmetric-key encryption, the same key is used for encryption at the transmitter and decryption at the receiver. In asymmetric-key encryption, the encryption and decryption processes are preformed using different keys. The operations performed in symmetric-key encryption algorithms are generally less complex than that in asymmetric encryption algorithms. Thus, symmetric-key cryptography is often considered in sensor networks [38]. However, it is noted that symmetric encryption strategies require key distribution and management mechanisms to allow the transmitter and the receiver to securely share the secrete key and periodically update it. A study in [39] demonstrated that symmetric encryption can be easily implemented on MICA2 sensors, and asymmetric encryption could be tractable. For jamming: Jamming mitigation can be realized through frequency hopping and spread spectrum approaches [40]. Due to the limited number of frequencies that a sensor can operate in, jamming mitigation through spread spectrum techniques could be inapplicable in sensor networks [38]. Other approaches for jamming mitigation include traffic surfing [41], where nodes adapt their communication channel based on the interference. Two approaches are considered in [41]: In the first approach, all the sensors in the network change their channels when high interference (jamming) is detected; in the second approach, only nodes in the interference region choose a 11 different communication channel. These approaches may work well under fixed-pattern partial-band jamming, but they still face significant challenges under random jamming. 1.4 Major Contributions of the Dissertation This dissertation aims to improve the reliability and efficiency of time-critical communications in WSNs, under both benign and hostile environments. In Chapter 2, we explore reliable distributed detection in mobile access wireless sensor networks under Byzantine attacks [42]. We consider the q-out-of-m fusion rule, which is popular in distributed detection and can achieve a good trade-off between the miss detection probability and the false alarm rate. However, a major limitation with it is that the optimal scheme parameters can only be obtained through exhaustive search, making it infeasible for large networks. In this chapter, first, by exploiting the linear relationship between the scheme parameters and the network size, we propose simple but effective sub-optimal linear approaches. Second, for better flexibility and scalability, we derive a near-optimal closed-form solution based on the central limit theorem. Third, subjecting to a miss detection constraint, we prove that the false alarm rate of q-out-of-m diminishes exponentially as the network size increases, even if the percentage of malicious nodes remains fixed. Finally, we propose an effective malicious node detection scheme for adaptive data fusion under time-varying attacks; the proposed scheme is analyzed using the entropy-based trust model, and has shown to be optimal from the information theory point of view. Simulation examples are provided to illustrate the performance of proposed approaches under both static and dynamic attacks. In Chapter 3, we propose a novel mobile access coordinated wireless sensor network (MC-WSN) architecture for reliable, efficient, and time-sensitive information exchange. 12 In conventional sensor networks with mobile access points (SENMA), the mobile access (MA) points traverse the network to collect information directly from individual sensors. While simplifying the routing process, a major limitation with SENMA is that a transmission is made only if an MA visits the corresponding source node; thus, data transmission is limited by the physical speed of the MAs and the length of their trajectory, resulting in low throughput and large delay. The proposed MC-WSN effectively resolves this problem through hop number control [43]. More specifically, with active network development and topology design, the number of hops from any sensor to a mobile access can be limited to a pre-specified number. We discuss the optimal topology design for MC-WSN such that the average number of hops between the source and its nearest sink is minimized, and analyze the performance of MC-WSN in terms of throughput, stability, delay, and energy efficiency by exploiting tools in information theory, queuing theory, and radio energy dissipation model. It is shown that under stable system conditions, MC-WSN achieves much higher throughput and significantly lower delay and energy consumption than that of SENMA. In Chapter 4, we provide a unified framework for quantitative characterization of various wireless networks [44]. We first revisit the evolution of centralized, ad-hoc and hybrid networks, and discuss the trade-off between structure-ensured reliability and efficiency, and ad-hoc enabled flexibility. Motivated by the observation that the number of hops for a basic node in the network to reach the base station or the sink has a direct impact on the network throughput, delay, efficiency and their evaluation techniques, we introduce the concept of the N-hop networks. It can serve as a general framework that includes most existing network models as special cases, and can also make the analytical characterization of the network performance more tractable. Moreover, for the network security, it is observed that hierarchical structure enables easier tracking of user accountability and malicious node detection; on the other hand, the multi-layer 13 diversity increases the network reliability under unexpected network failure or malicious attacks, and at the same time provides a flexible platform for privacy protection. In Chapter 5, we summarize the conclusions and present some proposed directions for future research. 14 Chapter 2 Distributed Detection in Mobile Access Wireless Sensor Networks Under Byzantine Attacks This chapter explores reliable data fusion in mobile access wireless sensor networks under Byzantine attacks. We consider the q-out-of-m rule, which is popular in distributed detection and can achieve a good trade-off between the miss detection probability and the false alarm rate. However, a major limitation with this rule is that the optimal scheme parameters can only be obtained through exhaustive search, making it infeasible for large networks. In this chapter, first, by exploiting the linear relationship between the scheme parameters and the network size, we propose simple but effective sub-optimal linear approaches. Second, for better flexibility and scalability, we derive a near-optimal closed-form solution based on the central limit theorem. Third, subjecting to a miss detection constraint, we prove that the false alarm rate of the q-out-of-m c �2014 IEEE. Reprinted, with permission, from M. Abdelhakim, L. Lightfoot, J. Ren, and T. Li, “Distributed Detection in Mobile Access Wireless Sensor Networks under Byzanc tine Attacks,” IEEE Transactions on Parallel and Distributed Systems, 2014 [42], �2011 IEEE. Reprinted, with permission, from M. Abdelhakim, L. Lightfoot, and T. Li, “Reliable Data Fusion in Wireless Sensor Networks under Byzantine Attacks,” IEEE Military Communications Conference, Nov. 2011 [45], and M. Abdelhakim, L. Zhang, J. Ren, and T. Li, “Cooperative Sensing in Cognitive Networks under Malicious Attack”, IEEE International Conference on Acoustics Speech and Signal Processing, May 2011 [46],. 15 rule diminishes exponentially as the network size increases, even if the percentage of malicious nodes remains fixed. Finally, we propose an effective malicious node detection scheme for adaptive data fusion under time-varying attacks; the proposed scheme is analyzed using the entropy-based trust model, and has shown to be optimal from the information theory point of view. Simulation examples are provided to illustrate the performance of proposed approaches under both static and dynamic attacks. 2.1 Introduction Wireless sensor networks have received significant attention from the research community due to their impact on both military and civilian applications [1,2,47,48]. Limited by the processing capability and power supply of the sensor nodes, incorporating security into wireless sensor networks has been a challenging task [38, 49–53]. A serious threat to wireless sensor networks is the Byzantine attack [31,54–59], where the adversary has full control over some of the authenticated nodes and can perform arbitrary behavior to disrupt the system. Distributed detection under malicious attacks has been studied from different perspectives in the literature. In [60], an iterative redundancy approach was proposed to combat the Byzantine failure problems in distributed computation architectures. In this approach, the system chooses a number of nodes to perform the computation in order to reach the required reliability level. If consensus cannot be reached among the selected nodes, then more nodes are recruited for the computation. The algorithm is repeated until the required reliability is achieved. A similar approach use majority voting based on iterative group message exchange can be found in [61]. In [62], credibilitybased fault-tolerance is discussed for the volunteer computing systems, where both majority voting and spot-checking scheme are integrated. In spot-checking, training 16 data is used to detect the malicious machines. The server continues the voting and spot-checking processes until the overall credibility level is reached. While the approaches in [60–62] may work well for ordinary distributed systems, the complexity and delay caused by the iterative processes could be an unaffordable burden for wireless sensor networks (WSNs). In [63], fault-tolerant data acquisition is discussed for clustered sensor networks, in which data fusion is first performed in each cluster to obtain local estimates, and then performed at a higher level to obtain a global estimate from the local estimates provided by each cluster head. Weighted average is utilized for data aggregation, where the weighting factor of each sensor is determined using spatial correlation among neighboring sensors. One possible limitation with this approach is that degraded system performance may occur when a group of neighboring sensors collaborate to send fictitious data. In [64], the median approach is proposed for distributed detection in clustered WSN, under the assumption that the data is always sent through binary symmetric channels, and all nodes have the same, arbitrary-low probability of sending faulty results. The latter assumption could be too ideal, since attackers could send false sensing information with high probabilities. In this work, we consider reliable data fusion in wireless sensor networks with mobile access points (SENMA) [17] under both static and dynamic Byzantine attacks, in which the malicious nodes report false information with a fixed or time-varying probability, respectively. In SENMA, the mobile access point traverses the network and collects the sensing information from the individual sensor nodes. The major advantage of the SENMA architecture is that it ensures a line of sight path to the access point within the power range of the sensor nodes, allowing the information to be conveyed without routing. This feature makes it a resilient, scalable and energy efficient architecture for wireless sensor networks. In many cases, due to bandwidth and energy limitations, the sensors quantize their sensing result into a single bit [65–68]. The MA receives the 17 sensing reports and applies the fusion rule to make the final decision. One popular hard fusion rule used in distributed detection is the q-out-of-m scheme [66, 67, 69], in which the mobile access point randomly polls reports from m sensors, then decides that the target is present only if q or more out of the m polled sensors report ‘1’. It is simple to implement, and can achieve a good trade-off between minimizing the miss detection probability and the false alarm rate. In ideal scenarios, the optimal scheme parameters for the q-out-of-m fusion scheme are obtained through exhaustive search. However, due to its high computational complexity, the optimal q-out-of-m scheme is infeasible as the network size increases and/or the attack behavior changes. To overcome this limitation, effective sub-optimal schemes with low computational complexity are highly desired. The main contributions in this chapter can be summarized as follows: First, we propose a simplified, linear q-out-of-m scheme that can be easily applied to large size networks. The basic idea is to find the optimal scheme parameters at relatively small network sizes through exhaustive search, and then obtain the fusion parameters for large network size by exploiting the approximately linear relationship between the scheme parameters and the network size. It is observed that the proposed linear approach can achieve satisfying accuracy with low false alarm rate. However, there are chances of violating the problem constraint. To enforce the miss detection constraint and improve the data fusion accuracy, we further propose to use the linear approximation as the initial point for the optimal exhaustive search algorithm. With this enhanced linear approach, near-optimal solutions can be obtained with much lower computational complexity compared with that of the pure exhaustive search approach. Second, in an effort to search for an easier and more flexible distributed data fusion solutions that can easily adapt to unpredictable environmental changes and cognitive behavior of malicious nodes, we derive a closed-form solution for the q-out-of-m fusion 18 scheme based on the central limit theorem. It is observed that the closed-form solution is a function of the network size, the percentage of malicious sensors, the malicious nodes’ behavior, and the detection accuracy of the sensor nodes. We show that the closed-form solution delivers comparable results with that of the near-optimal solution obtained from the enhanced linear approach. Third, we perform theoretical analysis for both the linear approach and the closedform solution. We show that under a fixed percentage of malicious nodes, the false alarm rate for both approaches diminishes exponentially as the network size increases. This analysis reveals an interesting and important result: even if the percentage of malicious nodes remains unchanged, larger size networks are much more reliable under malicious attacks. It indicates that the network size plays a critical role in reliable data fusion. Moreover, we also find an upper bound on the percentage of malicious nodes that can be tolerated by the network under the q-out-of-m fusion rule. It turns out that this upper bound is determined by the sensors’ detection probability and the attack strategies of the malicious nodes. Finally, we propose a simple and effective malicious node detection approach, where the malicious sensors are identified by comparing the decisions of the individual sensors with that of the fusion center. It is observed that dynamic attacks generally take longer time and more complex procedures to be detected as compared to static attacks. It is also found that the proposed malicious detection procedure can identify malicious sensors accurately if sufficient observation time is allowed. The proposed approach is analyzed using an entropy-based trust model. We show that under the same system settings, the proposed malicious node detection approach is optimal from the information theory point of view. We further propose to adapt the fusion parameters based on the detected malicious sensors and their estimated probability of attack. It is shown that the proposed adaptive fusion scheme can improve the system performance 19 significantly under both static and dynamic attack strategies. 2.2 2.2.1 Problem Formulation Overall System Set-Up We consider a centralized sensor network architecture, known as SENMA [70], where we assume that the network is composed of n power-limited sensor nodes and a powerful mobile access point. The architecture is illustrated in Figure 2.1. We assume that the nodes are randomly and uniformly distributed over the network, and the mobile access point traverses the network on a predefined trajectory to communicate with all the sensing nodes. The sensor network performs distributed detection. Each sensor node detects the presence of the target object by applying an application-dependent detection algorithm, such as energy detection [71], and sends its one-bit hard decision report to the mobile access point (‘1’ means that the target is present), which makes the final decision accordingly. This hard decision model is adopted here for two reason: (1) To reduce the transmission and processing burden of the sensor network; (2) To enable more tractable analysis on the effect of the network size on the reliability of the distributed detection under Byzantine attacks. Benign Sensor node Mobile access point Malicious sensor node Figure 2.1: SENMA under Byzantine attack. 20 If the network covers a large area, we divide the area into smaller sections, and apply the fusion rule over nodes that are within the same section. This setting ensures that, statistically, nodes within the same section have the same chance of detecting the target. We assume that the network contains k malicious sensors. The percentage of malicious sensors, k/n, is denoted by α, which is assumed to be known or can be estimated at the mobile access point (MA). When no prior knowledge of α exists, the MA would start with a majority vote1 and obtain an estimate for α by comparing the individual sensing reports with the final decision. We assume that each benign sensor node has a false alarm probability2 Pf and a miss detection probability3 Pm , while the malicious sensors have their own false alarm probability P˜f and miss detection probability P˜m . These probabilities are determined by the environmental conditions and the sensors’ capabilities to detect the target. The MA uses the binary reports of the sensor nodes to make the final decision on whether the target is present or absent. This distributed detection problem can be modeled using the conventional binary hypothesis test, where the hypothesis H0 represents the absence of the target, and the hypothesis H1 represents the presence of the target. Here, we will first discuss different attack strategies that can be adopted by the malicious sensors, then present the problem formulation based on the q-out-of-m scheme. 1 In majority vote if more than half of the sensors reported ‘1’, then the final decision is ‘1’. 2 The false alarm rate is the conditional probability that the target is said to be present, when it is not. 3 The miss detection probability is the conditional probability that the target is said to be absent, when it is present. 21 2.2.2 Modeling of Possible Attack Strategies There are different attack strategies that could be adopted by the malicious sensors. Let Po be the probability that each malicious node intentionally reports the opposite information to its actual sensing decision. It is assumed that all malicious nodes have the same probability of attack in a particular sensing period. We classify the possible attack strategies into two categories: 1. Static Attack: In this strategy, the malicious nodes send opposite data with an arbitrary probability Po that is fixed, with 0 < Po ≤ 1. 2. Dynamic Attack: In this strategy, the malicious nodes change Po after each attacking block, which is composed of one or more sensing periods. More specifically, Poi = Poi−1 + ∆1 x − ∆2 (1 − x), (2.1) where Poi is the value of Po in the nth attacking block, x is a Bernoulli random variable that is equal to ‘1’ with probability Px , ∆1 and ∆2 are the increment and decrement step size, respectively. Taking the malicious nodes’ own false alarm and miss detection probabilities into consideration, it turns out that the malicious sensors may have different probabilities of attack when the target is present and when the target is absent. We refer to them as the miss detection attack probability (Pa,m ) and false alarm attack probability (Pa,f ). More specifically, the overall miss detection attack probability is given by: Pa,m = P¯o (1 − P˜m ) + (1 − P¯o )P˜m , where P¯o = Po for static attacks, and equals to the average Poi over all attacking blocks for dynamic attacks. The false alarm attack probability is given by: Pa,f = P¯o (1 − P˜f ) + (1 − P¯o )P˜f . We define Pa as the overall attack probability of malicious sensors. If the state of nature is equal to ‘1’ with probability p, 22 then Pa = pPa,m + (1 − p)Pa,f . In the special case when the sensor nodes can perfectly detect the state of nature, i.e., P˜f = 0 and P˜m = 0, then Pa = Pa,m = Pa,f = P¯o . 2.2.3 Problem Formulation For reliable data fusion in SENMA under Byzantine attacks, we propose to use the qout-of-m fusion rule, in which the MA randomly polls m out of n reports, then decides that the target is present (H1 ) only if q or more out of the m polled sensors report ‘1’. The main reason is that other hard fusion rules, such as OR4 , AND5 , or the majority voting rule, might not achieve the compromise between minimizing the false alarm rate and the miss detection probability [66], especially under malicious attacks. Moreover, the q-out-of-m scheme parameters can be adapted based on the attacking behavior and percentage of malicious sensors. This inherit flexibility makes the q-out-of-m scheme superior to other hard fusion rules. We aim to obtain m and q to minimize the overall false alarm rate Qf , while keeping the overall miss detection rate Qm below a certain predefined value β. That is, our objective is to find the optimal m and q that can minimize Qf , subject to the constraint Qm ≤ β. The problem can be formulated as follows: min Qf (m, q)m (2.2) m,q s.t. Qm (m, q) ≤ β, 1 ≤ q ≤ m ≤ n, q, m ∈ N. It should be pointed out that there is always a trade-off between minimizing the false alarm rate and the miss detection probability, therefore the parameter q should not be too small nor too large. Large q can improve the false alarm rate, but would increase 4 OR rule: if at least one sensor reports ‘1’, then the decision is ‘1’; otherwise, the decision is ‘0’. 5 AND rule: if all sensors report ‘1’, then the decision is ‘1’; otherwise, the decision is ‘0’. 23 the miss detection probability. Small q can achieve a higher detection probability, but would increase the false alarm rate. d,m−d Define Pk,n−k as the probability of polling m − d out of n − k benign sensors and (k)( n−k ) d,m−d d out of k malicious sensors. That is, Pk,n−k = d m−d . According to our system n) (m model, the overall false alarm rate, Qf , can be expressed as: k � Qf = d � � � d d,m−d Pk,n−k c=0 d=max(0, m+k−n) × m−d � j=max(0,q−c) � c c (1 − P )(d−c) Pa,f a,f � m−d j Pf (1 − Pf )(m−d−j) . j (2.3) If the m polled sensors contain d out of the k malicious nodes, then the false alarm occurs when c or more out of d malicious sensors attack and q − c or more benign sensors send false alarms, where 0 ≤ c ≤ d. It is noted that the minimum number of malicious reports being polled is d = max(0, m + k − n). That is, when the number of sensors polled, m, is greater than the number of benign sensors (n − k), then there are at least m − (n − k) malicious reports received by the MA. The overall probability of detection Qd can be expressed as: Qd = k � d,m−d Pk,n−k c=0 d=max(0, m+k−n) × m−d � j=max(0,q−c) d � � � d � c (d−c) (1 − Pa,m )c Pa,m � m−d j Pd (1 − Pd )(m−d−j) , j (2.4) where Pd = 1 − Pm is the detection probability of the benign nodes, when the target is present. The overall miss detection probability Qm is then obtained by Qm = 1 − Qd . 24 Intuitively, if q is greater than the number of benign sensors, i.e., q > n − k, and the malicious nodes have high miss detection attack probability (Pa,m → 1), then the overall miss detection probability will be very high (Qm → 1). Thus, q should not be too large. On the other hand, if q is less than the number of malicious sensors, i.e., q < d, and the malicious nodes have high false alarm attack probability (Pa,f → 1), then Qf → 1. Thus, q should not be too small. The trade-off between minimizing the false alarm rate and the miss detection probability is further illustrated in Figures 2.2(a) and 2.2(b), where Qf and Qm are obtained for different values of m and q. It is shown that lower q improve the miss detection probability, but degrade the false alarm rate; and, higher q degrades the miss detection probability, but improves the false alarm rate. Note that OR rule corresponds to the case when m = n and q = 1. It is clear from Figure 2.2(a) that OR rule results in a very high false alarm rate under Byzantine attack. It is noted that finding the optimal m and q from (2.2) is a nonlinear integer optimization problem that is hard to be solved theoretically. The optimal approach is to perform exhaustive search over all possible m and q values, and then choose the (mo , qo ) pair that results in the lowest false alarm rate while satisfying the miss detection constraint. The computational complexity of the optimal exhaustive search is O(n2 ) [72], which would be infeasible for real-time data fusion in large networks. Therefore, we aim at finding simpler but accurate methods to obtain the scheme parameters that solve (2.2). 25 n=30,k=10 0 10 −2 10 −4 Qf 10 −6 10 −8 10 q=1 q=5 q=10 q=15 q=20 −10 10 −12 10 0 5 10 15 m 20 25 30 25 30 (a) The false alarm rate. n=30,k=10 0 10 −2 10 −4 10 −6 Qm 10 −8 10 −10 10 q=1 q=5 q=10 q=15 q=20 −12 10 −14 10 0 5 10 15 m 20 (b) The miss detection probability. Figure 2.2: The false alarm rate and miss detection probability when n = 30, k = 10, Pa,f = Pa,m = 1, Pf = 0.1, and Pd = 0.775. 26 2.3 Simplified Data Fusion Scheme - The Linear Approach In this section, we will first highlight some observations based on the optimal q-outof-m scheme, and then present the simplified algorithms that can be easily applied to large-scale networks. 2.3.1 Observations To develop effective sub-optimal schemes with low computational complexity, it is important to know how the parameters m and q change with the system variables, such as α and n. In this section, we consider the case where the malicious sensors attack with probability Pa . We calculate the optimal parameters at different Pa values, under different network sizes and different percentages of malicious sensors. The following observations are made [45]: Observation 1: The optimal m is almost independent of the percentage of malicious nodes, and has a linear relationship with n. In fact, it is always equal to or very close to n, as shown in Figures 2.3(a) and 2.3(c), which implies that the reports of almost all the sensors should be considered in the optimal q-out-of-m fusion scheme6 . This observation enables us to reduce the problem to finding the best q when m = n, which lowers the computational complexity from O(n2 ) to O(n). Observation 2: The optimal value of q follows an approximately linear function of n with different slopes depending on the percentage of the malicious nodes and the probability of attack, as shown in Figures 2.3(b) and 2.3(d). Motivated by these observations, we develop simplified approaches to obtain the 6 However, this is no longer the case when malicious node detection scheme is employed, as the reports of the malicious sensors would be discarded. Malicious detection will be considered in section 2.6. 27 50 25 α=20% α=25% α=30% α=20% 45 α=25% α=30% 20 40 35 15 qo mo 30 25 10 20 15 5 10 5 10 15 20 25 30 n 35 40 45 0 10 50 15 20 25 30 n 35 40 45 50 (a) Optimal m vs. n at different α, when Pa = (b) Optimal q vs. n at different α, when Pa = 1. 1. 50 35 Pa=0.7 30 Pa=0.2 40 25 35 20 qo mo 45 Pa=0.7 Pa=0.4 30 15 25 10 20 20 25 30 35 n 40 45 50 5 20 Pa=0.4 Pa=0.2 25 30 35 n 40 45 50 (c) Optimal m vs. n at different Pa , when α = (d) Optimal q vs. n at different Pa , when α = 25%. 25%. Figure 2.3: Optimal scheme parameters (mo , qo ) versus the network size at different percentage of malicious nodes (α) and different probability of attack (Pa ), when β = 0.01, Pf = 0.1, Pd = 0.775, Pa,m = Pa,f . 28 q-out-of-m fusion parameters with low complexity that can be easily applied to large network sizes. 2.3.2 The Linear Approach In this section, we propose a simplified q-out-of-m scheme by exploiting the linear relationship between the scheme parameters and the network size. The main idea is that we can get the optimal scheme parameters at relatively small network sizes, and use them as reference points. These optimal (m, q) pairs for the different network sizes, Pa values, and α ratios, can be obtained and stored in a look-up table, then used to get the suboptimal scheme parameters for large network sizes. We propose to set m = n and use the following linear function of n to obtain q [45]: qˆn,α = �qn0 ,α + So (α)(n − n0 )�, (2.5) where So (α) is the slope of the optimal qo versus n curve at a particular attack probability given that the percentage of the malicious nodes is α, qˆn,α is the suboptimal q value at a network size n, and qno ,α is the optimal q value at a relatively small network size n0 and it serves as a reference point. Both qˆn,α and qno ,α are at α percent of malicious sensors. �x� is the smallest integer larger than or equal to x. Note that the optimal q depends on the false alarm and miss detection probabilities of the sensor nodes, hence a periodical update of the reference points and related slopes would be required in time-varying environments. While the linear approach can deliver very good performance, there are chances of violating the problem constraint. Therefore, we propose to enhance the linear approach to guarantee that the best choice of q obtained satisfies the miss detection probability constraint. 29 2.3.3 Enhanced Linear Approach To ensure that the scheme parameter obtained using the linear approximation, qˆn,α , results in the lowest false alarm rate and satisfies the miss detection constraint in (2.2), the linear approach is enhanced using an iterative method to find qˆn,α 7 . The algorithm works as follows: 1. Set m = n and use the linear approximation in (2.5) as an initial value for qˆn,α . 2. Calculate the miss detection probability using (2.4). 3. Increase qˆn,α to qˆn,α + 1 if Qm is below the predefined β. Then, go to step 2. 4. Decrease qˆn,α to qˆn,α − 1 if Qm is above the predefined β. Then, go to step 2. 5. Terminate the iterations when the largest qˆn,α that meets the miss detection constraint is obtained. Note that higher values of q lower the false alarm rate. The approach above obtains the largest q that satisfies the miss detection constraint, hence provides a near-optimal solution. The sub-optimal q values (ˆ qn,α ), obtained using the linear and the enhanced linear approaches, are shown in Figure 2.4(a). It is shown that the linear relationship between q and n is also valid for the enhanced linear approach. In Figure 2.4(b), the number of iterations required in the enhanced linear approach is plotted versus the network size. It is shown that the enhanced approach converges after few iterations, and thus it is computationally less intensive than the optimal exhaustive search. 7 Reprinted from M. Abdelhakim, L. Lightfoot, J. Ren, and T. Li, “Reliable Cooperative Sensing in Cognitive Networks”, Wireless Algorithms, Systems, and Applications, WASA’12, Springer Berlin Heidelberg, vol. 7405, pp. 206 - 217 [73], with kind permission from Springer Science and Business Media. 30 300 Linear approach Enhanced linear approach 250 q 200 150 100 50 0 50 100 150 200 250 300 350 400 450 500 400 450 500 n (a) q vs. network size. Number of iterations 15 10 5 0 50 100 150 200 250 300 350 n (b) Iterations of the enhanced linear approach. Figure 2.4: The enhanced linear approach at α = 25%. 31 While the linear approach works quite well, the absence of a well-defined closedform solution makes it difficult to adapt q based on the environmental conditions and the malicious behavior. To find q for different network settings, the slopes and the reference points should always be updated using exhaustive search. This could be tedious when the environment is fast-varying. To solve this problem, in the following section, we derive a closed-form expression for q. 2.4 A Closed-form Solution In this section, we derive a closed-form solution of q for the q-out-of-m fusion rule under both static and dynamic attacks. We exploit the observations of the optimal exhaustive search by setting m = n, as illustrated in the previous section. Recall that the malicious sensors have miss detection and false alarm attack probabilities, Pa,m and Pa,f , respectively. For notation simplicity, we assume that these two probabilities are equal, that is, Pa,m = Pa,f = Pa . It is worth mentioning that the analysis can be easily extended to the case when Pa,m �= Pa,f . We assume that all sensing reports are independent. It is noted that the distribution of each sensing report is determined by the environment and the behavior of the corresponding sensor node. Let the sensing report of node i be ui �{0, 1}, where i = {1, ..., n}. If node i is benign, then ui is a Bernoulli random variable characterized by detection probability Pd if the target is present, or the false alarm rate Pf if the target is absent; if node i is malicious, then ui is a Bernoulli random variable characterized by the parameter 1 − Pa if the target is present, or Pa if the target is absent. � The aggregated result at the MA is given by, U = ni=1 ui The random variable U represents the number of 1’s that the access point received. To apply the q-out-of-m fusion rule, U is compared to q. If U ≥ q, the final decision is that the target is present 32 (i.e., decide H1 ); otherwise, the final decision is that the target is absent (i.e., decide H0 ). Our closed-form solution is based on the central limit theorem, where the aggregated result at the access point is approximated as a Gaussian random variable. In fact, we have the following result: Proposition 2.1 Suppose a network of size n containing both benign sensors and malicious sensors, where the percentage of malicious sensors is α. The benign sensors have a detection probability Pd , and the malicious sensors attack with a probability Pa . Assuming the q-out-of-m fusion rule is applied subject to a predefined miss detection constraint β, then the lowest false alarm rate can be achieved when q = �an + √ bnQ−1 (1−β)�. Here, a = (1 − α) Pd +α(1−Pa ), b = (1 − α) Pd (1−Pd )+α(1−Pa )Pa , and Q−1 (.) is the inverse Q function8 . Proof: Note that U is the summation of independent random variables. If the number of sensors n is large, then U can be approximated as a Gaussian random variable. When the target is present (H1 ), U ∼ N (Mu,p , Vu,p ), where Mu,p and Vu,p can be found by summing up the means/variances of the (n − k) benign nodes and the k malicious nodes, respectively. More specifically, Mu,p = (n − k)Pd + k(1 − Pa ) = [(1 − α) Pd + α(1 − Pa )] n, (2.6) Vu,p = (n − k)Pd (1 − Pd ) + k(1 − Pa )Pa = [(1 − α) Pd (1 − Pd ) + α(1 − Pa )Pa ] n. (2.7) Define a = (1 − α) Pd + α(1 − Pa ) and b = (1 − α) Pd (1 − Pd ) + α(1 − Pa )Pa , we get 8 The Q function is defined as: Q(x) = √1 2π �∞ 33 x e− x2 2 dx. Mu,p = an and Vu,p = bn. When the target is absent (H0 ), U ∼ N (Mu,a , Vu,a ), where Mu,a = (n − k)Pf + kPa = [(1 − α)Pf + αPa ]n, (2.8) Vu,a = (n − k)Pf (1 − Pf ) + kPa (1 − Pa ) = [(1 − α)Pf (1 − Pf ) + αPa (1 − Pa )]n. (2.9) Similarly, define c = (1 − α)Pf + αPa and d = (1 − α)Pf (1 − Pf ) + αPa (1 − Pa ), we get Mu,a = cn and Vu,a = dn. ˜ f , and is The overall false alarm rate using the Gaussian model is denoted by Q defined as the conditional probability that U is greater than or equal to q given that the target is absent. That is: ˜ f = P (U ≥ q|H0 ), Q (X−Mu,a )2 � n − 1 2Vu,a � = e dX 2πVu,a q � � � � q − Mu,a n − Mu,a � � = Q −Q . Vu,a Vu,a Assuming very large network size n, then Q ˜f ≈ Q Q � � n−Mu,a √ Vu,a q − Mu,a � Vu,a � � . (2.10) → 0, and it follows that: (2.11) ˜ m is defined as the conditional Similarly, the overall miss detection probability Q ˜ m can be probability that U is less than q given that the target is present. Hence, Q 34 expressed as: ˜ m = P (U < q|H1 ) Q = 1 − P (U ≥ q|H1 ) � � q − Mu,p � ≈ 1−Q . Vu,p (2.12) There is an obvious trade-off between the false alarm rate and the miss detection probability. It can be noted from equations (2.11) and (2.12) that, increasing q will result in an improved false alarm rate, but degrades the the miss detection probability. Therefore, the miss detection constraint sets an upper bound to the value of q. If the miss detection constraint is Qm ≤ β, then q should be bounded by9 : q ≤ Mu,p + � Vu,p Q−1 (1 − β), (2.13) In order to minimize the false alarm rate, the largest q value is selected. That is: � � Mu,p + Vu,p Q−1 (1 − β) √ = �an + bnQ−1 (1 − β)�, q = � (2.14) where �x� is the largest integer less than or equal to x. This approach ensures that the q defined in (2.14) minimizes the false alarm rate while satisfying the miss detection � constraint. In the following, we consider the percentage of malicious nodes that can be tolerated by the network using the q-out-of-m fusion rule. More specifically, we have the following result: For reliable data fusion using the q-out-of-m rule, the percentage of malicious 9 Note that in order to have Q(x) ≥ y, then x ≤ Q−1 (y). 35 P d , where P is the probability of detection of the sensors nodes has to satisfy α < P +P d d a and Pa is the attack probability of the malicious nodes. In fact, as discussed in Section 2.2, in order to achieve low false alarm rate, we should have q > k. Following Proposition 2.1, this implies that: k < Mu,p + � Vu,p Q−1 (1 − β) (2.15) Note that the second term on the left hand side of (2.15) is negative, since β is a small number. We have: k < Mu,p < [(1 − α) Pd + α(1 − Pa )] n. (2.16) Dividing both sides by n, and note that α = nk , we get: α< Pd . Pd + Pa (2.17) The values of q obtained by the linear, the enhanced linear, and the closed-form solution, are shown in Figure 2.5. It is observed that the enhanced linear and the derived closed-form solution obtain almost the same value for q, which shows that the closed-form solution obtained using the Gaussian model is accurate and achieves near-optimal solution. The significance of the closed-form solution is that it facilitates instantaneous adaptation of the fusion parameters to the changes in the environmental conditions and the attack strategies. Adaptive fusion will be further discussed in Section 2.6. 36 α=25% 300 Closed−form solution Linear Approach Enhanced Linear Approach 250 q 200 150 100 50 0 0 50 100 150 200 250 n 300 350 400 450 500 Figure 2.5: The q obtained using linear approach, enhanced linear approach and closedform solution. Here, the percentage of malicious sensors α = 25%, Pa,m = 1, Pa,f = 1, Pd = 0.775, and Pf = 0.1. 2.5 Analytical Bounds for the Proposed Approaches In this section, we derive the analytical bound for the q-out-of-m scheme based on the closed-form solution and the linear approach, and show that the accuracy of the q-out-of-m scheme increases exponentially as the network size increases, even if the percentage of malicious sensors remains the same. We consider the linear approach first, for which we have: Proposition 2.2 Using the linear q-out-of-m approach, for a fixed percentage of malicious sensors, the overall false alarm rate diminishes exponentially as the network 37 q−k size n goes to infinity. More specifically, when n is very large and Pf < n−k , then Qf ≤ exp {−(An + B)}, where A and B are constants, and A > 0. Proof: In the worst case when Pa,f = 1, the false alarm probability Qf can be expressed as: Qf = n−k � i=q−k � � n−k Pfi (1 − Pf )n−k−i . i (2.18) It is clear that Qf is the summation over a binomial probability density function with parameters Pf and n − k, where the random variable is the number of benign nodes having false alarm. Recall that the Chernoff bound states that if X is a binomial random variable with mean µ, then: P r {X ≥ (1 + δ)µ} < � expδ (1 + δ)(1+δ) �µ for δ > 0. (2.19) Let the random variable X be the number of benign nodes sending false alarm, then µ = (n − k)Pf . Therefore, Qf = P r{X ≥ q − k}. By setting (1 + δ)µ = q − k, we get q−k q−k δ = (n−k)P − 1. When Pf < n−k , we have δ > 0. It then follows from (2.19) that: f � � q − k −(q−k) Qf < exp{q − k − µ}. µ (2.20) By applying the logarithm function followed by the exponential function, we get: � � � � q−k Qf < exp −(q − k) ln +q−k−µ . µ (2.21) When the linear approach is employed, we have q = qˆn,α , where qˆn,α = qno ,α + (n − no )So (α). Here, we assume that the percentage of the malicious nodes, α, is fixed. � � The term ln q−k can be written as: µ 38 � q−k ln µ We have: � � � qno ,α + (n − no )So (α) − αn = ln n(1 − α)Pf � � qno ,α − no So (α) So (α) − α = ln + . n(1 − α)Pf (1 − α)Pf � � � q−k So (α) − α lim ln = ln = Zo , n→∞ µ (1 − α)Pf � (2.22) (2.23) where Zo is a constant. Following (2.21)-(2.23), when n → ∞, Qf can be bounded as follows: Qf < exp {−(q − k)Zo + q − k − µ} � � � < exp −(Zo − 1) qno ,α + (n − no )So (α) − αn � −n(1 − α)Pf < exp {−(An + B)} , (2.24) � � where A = (Zo − 1) [So (α) − α] + (1 − α)Pf and B = (Zo − 1) qno ,α − no So (α) . Note that A > 0. In fact, note that ln(x) > 1 − x1 for x > 1 [74], following (2.23), we have � � (1−α)Pf (1−α)Pf Zo − 1 > − S (α)−α . Then, A > − S (α)−α [So (α) − α] + (1 − α)Pf = 0. o o This proves that, as n goes to infinity, Qf decreases exponentially with the network size, even if the percentage of malicious nodes is fixed. � For the closed-form solution, we have: Proposition 2.3 For a fixed percentage of malicious nodes and under the same attack strategy, the overall false alarm rate using the closed-form q-out-of-m approach diminishes exponentially as the network size n goes to infinity. More Specifically, for large n 39 and Pf < q−k n−k , Proof: ˜ f ≤ exp Q � (a−c) − 12 d 2 � n , where a, c and d are constants. From equation (2.11), the false alarm rate can be bounded using the Chernoff bound [75] as follows:  ˜ f ≤ 1 exp − 1 Q 2 2 � q − Mu,a � Vu,a �2  , q − Mu,a � > 0. Vu,a (2.25) q−M a The condition √ u,a > 0 is equivalent to q > Mu,a , and consequently Pf < q−kP n−k . In Vu,a q−k the worst case when Pa = 1, this condition becomes Pf < n−k . Following Proposition √ 2.1, set q = �an + bnQ−1 (1 − β)�, we get:  � √ bnQ−1 (1 − β) − cn �2  ˜ f ≤ 1 exp − 1 an +  √ Q 2 2 dn  � �2  √ −1 √ 1 1 (a − c) n + bQ (1 − β)  √ ≤ exp − . 2 2 d (2.26) �√ � √ � � If the network size is very large, i.e., n → ∞, then |(a − c) n| >> � bQ−1 (1 − β)� and we obtain: � 2 � 1 1 (a − c) ˜f ≤ Q exp − n . 2 2 d (2.27) If α is fixed and the attack strategy is the same, then a and c are constants and the false alarm rate decreases exponentially as the network size increases. This proves the � proposition. Discussions: (i) Our analytical results provided in this section highlight the impact of the q-out-of-m fusion scheme on large-scale networks that are more reliable under malicious attacks. They indicate that when the q-out-of-m rule is used for data fusion, 40 then the false alarm rate diminishes exponentially as the network size increases even if the percentage of malicious sensors remains the same. This implies that for a fixed α, we can improve the network performance significantly by increasing the network size. (ii) Explanation on the condition in Propositions 2.2 and 2.3: The conq−k dition “Pf < n−k ” is equivalent to “q − k > Pf (n − k)”. The physical meaning of this condition can be explained in two ways: First, in order to have arbitrarily low overall false alarm probability by the q-out-of-m fusion rule, the individual false alarm rates of the benign nodes should be less than a certain limit. This limit is equal to the ratio between the least number of benign nodes in the set of q nodes relied on in the q-out-of-m scheme (q − k), to the total number of benign nodes (n − k). Second, since each benign node has a none zero false alarm rate Pf , to reduce the overall false alarm rate, sufficient number of benign nodes need to be taken into account so the the “averaged” result will lead to a low overall false alarm rate. Mathematically, this q−k condition can also be understood as: if Pf > n−k (i.e., δ < 0), then the overall false alarm rate would be very high and cannot decrease beyond a certain level. In fact, we can write P r {X ≥ (1 + δ)µ} = P r {(1 − |δ|)µ ≤ X < µ} + P r {X ≥ µ}. The term P r {X ≥ µ} is generally high. If we approximate X as a normal distribution, then P r {X ≥ µ} = 12 . Therefore, if δ < 0, the overall false alarm Qf ≥ 12 . 2.6 Malicious Node Detection and Adaptive Fusion In this section, we propose to enhance the system performance through malicious node detection, where the hostile behavior is identified and the malicious sensors are discarded from the final decision making. Furthermore, we propose an adaptive fusion procedure, where the fusion parameters are tuned based on the attack behavior and the percentage of the malicious sensors. 41 2.6.1 The Malicious Node Detection Scheme Let Imal be the set of the malicious nodes, and ONs denotes the reports of all nodes till the sensing period Ns . When the attack strategy is known, and the percentage of malicious nodes is fixed, a traditional approach to find the malicious set, Imal , is to maximize the a posterior probability of Imal given the observations ONs [76]. That is, the detected malicious set Iˆmal = arg maxI P (Imal |ONs ), where P (Imal |ONs ) is the mal conditional probability that the malicious set is Imal given all the reports ONs . However, this detection approach is difficult to be implemented since it requires searching over all possible sets of Imal . In this section, we propose a simple malicious node detection scheme, where the sensors’ decision reports are used to identify the malicious nodes and estimate their attack behavior. Let Pa,f (i) and Pa,m (i) denote the probabilities that the ith node attacks when the target is absent and present, respectively. Let Pˆa,f (i) and Pˆa,m (i) be their estimated versions. We estimate Pa,f (i) and Pa,m (i) by using two counters for each node at the mobile access point. More specifically, for node i, • Ti,o : represents the number of times node i sends ‘0’ when the final decision is ‘1’. • Ti,1 : represents the number of times node i sends ‘1’ when the final decision is ‘0’. These counters are updated after each sensing period by comparing the final decision (obtained using the q-out-of-m rule) with the individual sensing reports. Assuming the observation interval is N sensing periods, and the number of observations where the access point decides that the target is present and absent are N1 and T T N0 , respectively. Then, if the node is benign, Ni,o and Ni,1 would be indications for the 1 0 ith node’s miss detection probability and false alarm rate, respectively. On the other 42 T T hand, if node i is malicious, Ni,o and Ni,1 will be estimates for Pa,m (i) and Pa,f (i), 1 0 respectively. T i,o More specifically, N = Qf (1 − Pf )(1 − p) + (1 − Qm )Pm p, where p = P rob{H1 } is the probability that the target is present. When both Qf and Qm are very low, Ti,o T N N then p = N1 and N � Pm N1 , which implies that Ni,o � Pm . We can write, 1 Ti,o N < Pm +δm,0 , where δm,0 mainly depends on the false alarm rate of the access point 1 T i,1 and the individual sensor. Similarly, N = Qm (1−Pm )p+(1−Qf )Pf (1−p) � Pf NNo . T That is, Ni,1 < Pf + δf,0 , where δf,0 mainly depends on the miss detection probability 0 at the access point as well as the individual sensor. We define the thresholds λp,f and λp,m as: λp,f = Pf + δf,0 , λp,m = Pm + δm,0 , (2.28) where Pf and Pm are the benign nodes’ false alarm and miss detection probabilities, δf,0 and δm,0 represent the tolerance in the estimated false alarm rate and miss detection probability of the nodes. Since, the fusion rule at the access point keeps the miss detection constraint, i.e. Qm has low value, δ0,f is a considerable small value. The miss detection constraint could be met at the expense of high false alarm rate, especially at small network sizes. Thus, we choose δf,0 < δm,0 . The parameters δf,0 , δm,0 should also account for the tolerance in the benign nodes’ miss detection and false alarm rates that would result from the changes in the environmental conditions and/or the sensors’ capabilities. We assume that the MA can estimate Pf and Pm . The malicious node detection procedure has two levels: T T If Ni,o ≥ λp,m or Ni,1 ≥ λp,f , the 1 0 node’s report is discarded from the current decision process, but its counters will • Level 1: Discard the suspicious reports continue to be updated in the next sensing periods. 43 T T • Level 2: Discard the unreliable nodes If Ni,o ≥ Pm + δ1 or Ni,1 ≥ Pf + δ2 , where 1 0 δ1 and δ2 are relatively large, then the corresponding node will be discarded from the sensing process. The nodes’ counters would be calculated to estimate the attack probability, but they will not be involved in the final decision making process. It should be noted that N needs to be greater than or equal to a certain threshold Nth before taking the decision to discard any node. Nth should be chosen to ensure the accuracy of the time averages, Pˆa,f (i) and Pˆa,m (i). When Pa,f (i) and Pa,m (i) are in the orders of 10−1 , it is safe to choose Nth ≥ 100. As will be illustrated in Section 2.7, the detection of the malicious nodes launching dynamic attacks is generally more difficult and takes longer time than the detection of the malicious nodes performing static attacks. 2.6.2 The Adaptive Fusion Algorithm Adaptive fusion can be achieved by updating the value of the q-out-of-m fusion parameters based on the average probability of attack. Recall that Iˆmal is the set of detected � � �ˆ � malicious nodes, then �Imal � is the total number of sensors detected to be malicious. The estimated average attack probability is given by: � � �ˆ � �Imal � � 1 � Pˆa = �� Pˆa (Iˆmal (i)) � ˆ �Imal � i=1 (2.29) T +T Iˆ (i),o Iˆmal (i),1 where Iˆmal (i) is the ith detected malicious sensor and Pˆa (Iˆmal (i)) = mal . N Then, q is tuned using equation (2.14) with the new problem settings, where n − � � � � �ˆ � �ˆ � �Imal � ⇒ n, k − �Imal � ⇒ k, α = k/n and Pa = Pˆa . 44 To deal with the malicious nodes who disguise themselves as benign nodes for a long periods between attacks, we can reset the counters periodically, and take the history of the nodes into account through initial conditions. More specifically, we define Nth,2 as the observation interval after which the counters are reset to the initial conditions. Nt,0 and Nt,1 are the total sensing periods performed in the network when the final decision is ’0’ and ’1’, respectively. The history of each node i is always reflected in o ) and the percentage of its miss detection the percentage of its false alarm reports (If,i o ). The adaptive fusion algorithm based on the malicious node detection reports (Im,i is further illustrated in Table 2.1. As will be shown in the simulation section, adaptive fusion with malicious node detection can improve the system performance significantly. We define ηd and ηf as the detection accuracy and false alarm rate of the malicious node detection scheme, respectively. That is, ηd � NM M , k ηf � NBM , n−k (2.30) where NM M is the number of malicious nodes detected to be malicious, NBM is the number of benign nodes mistakenly regarded as malicious, k is the total number of � � �ˆ � malicious sensors and (n − k) is the number of benign sensors. Note that �Imal � = NM M + NBM . It will be shown in Section 2.7 that with sufficient observation time, the proposed detection scheme can achieve high ηd and low ηf under static and dynamic attacks. 2.6.3 Analysis From the Entropy Point of View In the proposed malicious node detection approach, each node’s behavior is determined based on the uncertainty in the accuracy of its sensing report. Since uncertainty is generally measured by entropy, in this section, we analyze the proposed approach 45 Table 2.1: Adaptive fusion with malicious node detection o , I o ) to zeros Initialize all counters (N , N1 , N0 , Nt,1 , Nt,0 , Nr,1 , Nr,0 , Ti,o , Ti,1 , Im,i f,i After each sensing period, do: Set N to N + 1 for i from 1 to n if decision of node i is not equal to the final q-out-of-m decision check if node i reports ‘0’ and the final decision is ‘1’ Set Ti,o to Ti,o + 1, Nt,1 to Nt,1 + 1, and N1 to N1 + 1 otherwise check if node i report ‘1’ and the final decision is ‘0’ Set Ti,1 to Ti,1 + 1, Nt,0 to Nt,0 + 1, and N0 to N0 + 1 end if end for If the observation intervals N is greater than or equal Nth , then check for each node i: { T Ti,1 o ≥ P +δ o if Ni,o + Im,i m 0,m or N + If,i ≥ Pf + δ0,f 1 0 discard the reports of node i from the current decision process end if T o ≥ P + δ or Ti,1 + I o ≥ P + δ if Ni,o + If,i m 1 2 f f,i N0 1 discard the reports of node i from the sensing process end if T +T o + Io Estimate the attack probability of each node: Pˆa (i) = i,oN i,1 + If,i m,i Estimate the average probability of attack using (2.29) Update q based on the new settings using (2.14) } If N > Nth,2 , do the following for all nodes in the sensing process { Update the history: Set o Im,i to o N Ti,o +Im,i r,1 Nt,1 Set Nr,1 = Nt,1 Set Nr,0 = Nt,0 Reset the counters Ti,o , Ti,1 Reset N , N1 , N0 to zero } 46 and o If,i to o N Ti,1 +If,i r,0 Nt,0 using the entropy-based trust model [37]. First, for each node i ∈ {1, 2, ..., n}, we define two trust metrics T rustf (i) and T rustm (i) to represent the uncertainty in the node’s accuracy when the target is absent and present, respectively. T rustf (i) �    1 − H(Pˆa,f (i)),         H(Pˆ (i)) − 1, a,f if Pˆa,f (i) < 0.5; (2.31) if Pˆa,f (i) ≥ 0.5. where H(Pˆa,f (i)) is the entropy which represents the uncertainty that node i intentionally reports a false ‘1’ when the actual state of nature is ‘0’. That is, � H Pˆa,f (i) � � � ˆ ˆ = −Pa,f (i) log2 Pa,f (i) � � � � − 1 − Pˆa,f (i) log2 1 − Pˆa,f (i) . (2.32) T rustm (i) is defined in a similar way by replacing Pˆa,f (i) in equation (2.31) with Pˆa,m (i). The entropy trust metrics are in the range [−1, 1], where negative values mean that the attack probability of the corresponding node is greater than 0.5. The trust metrics are equal to ‘1’ when the corresponding node is benign with a perfect detection accuracy. Figure 2.6 plots the trust metrics (T rustf (i)/T rustm (i)) versus the Pˆa,f (i)/Pˆa,m (i). Note that Pf and Pm are generally small quantities, and we can assume Pf +δ0,f < 1/2 and Pm + δ0,m < 1/2. Define λe,f and λe,m as: λe,f � 1 − H(Pf + δ0,f ), λe,m � 1 − H(Pm + δ0,m ). 47 (2.33) Level 1 Level 2 1 0.8 T r ust f (i ), T r ust m (i ) 0.6 λe,f , λe,m λp,f , λp,m 0.4 Level 1 0.2 Level 2 0 −0.2 Discard reports Trustf ≤ λe,f ⇔ Pa,f ≥ λp,f Trustm ≤ λe,m⇔ Pa,m ≥ λp,m −0.4 −0.6 Discard sensors Trustf ≤ 0⇔ Pa,f ≥ 0.5 Trustm ≤ 0 ⇔ Pa,m ≥ 0.5 −0.8 −1 0 0.1 0.2 0.3 0.4 0.5 0.6 Pˆa ,f(i ), Pˆa, m(i ) 0.7 0.8 0.9 1 Figure 2.6: The trust metrics (T rustf (i)/T rustm (i)) vs. the Pˆa,f (i)/Pˆa,m (i). Compare (2.33) and (2.28), we can see that the proposed malicious node detection approach can be mapped to the entropy-based trust model. The equivalence is further illustrated in Table 2.2. Our discussions above show that under the same settings for δ0,f , δ0,m , δ1 and δ2 , the proposed malicious node detection scheme is equivalent to the detection approach based on the entropy-based trust model. This implies that the proposed malicious node detection scheme is optimal from the information theory point of view. 48 Table 2.2: Equivalence between the entropy based trust model and the proposed malicious node detection Cases Entropy-based trust model vs. the proposed malicious node detection approach 1. Discard suspicious reports T rustf (i) ≤ λe,f ⇔ Pˆa,f (i) ≥ λp,f T rustm (i) ≤ λe,m ⇔ Pˆa,m (i) ≥ λp,m 2. Discard unreliable nodes T rustf (i) ≤ 0 ⇔ Pˆa,f (i) ≥ 0.5 T rustm (i) ≤ 0 ⇔ Pˆa,m (i) ≥ 0.5 2.7 Simulation Results In this section, we illustrate the performance of the proposed approaches through simulation examples. In the simulations, we assume that the miss detection limit is β = 0.01, the hypothesis H1 happens with probability p = 0.5. The false alarm rate and the miss detection probability of each benign sensor are assumed to be Pf = 0.1 and Pd = 0.775. These false alarm and miss detection values are obtained assuming that the sensors employ energy detection, when the SNR level is 5 dB and the timebandwidth product is 5 [77]. For the static attack strategy, we set Po = 1. For the dynamic attack strategy, we set ∆1 = ∆2 = 0.2, Po1 = 0.7, Px = 0.5, and the number of sensing periods per attacking block is T = 10. The cumulative distribution function (CDF) of Pa is shown in Figure 2.7. It can be seen that Pa is spread over wide range of values. 49 1 0.9 0.8 CDF 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0.1 0.2 0.3 0.4 0.5 Pa 0.6 0.7 0.8 0.9 1 Figure 2.7: CDF of Pa for dynamic attack strategy with ∆1 = ∆2 = 0.2, initial Pa1 =0.7, Px = 0.5. Example 2.1 - Linear approaches and comparison with existing methods In this example, the performance of the linear and the enhanced linear approaches are evaluated, and we also compare them with existing AND rule, OR rule, and majority voting fusion approaches. We assume that the malicious nodes can detect the target perfectly and always report false information (i.e. Pa,m = 1, Pa,f = 1). At different values of α, So (α) is calculated from Figure 2.3. The reference points are at no = 35. The false alarm rate and the corresponding miss detection probability of the linear approach for different values of n and α are shown in Figures 2.8(a) and 2.8(b), respectively. It is clear that in most cases, the miss detection constraint is met. Slight increase in the miss detection over β happens at α = 15% and 25%. One solution to 50 this problem is to use the enhanced linear approach discussed in Section 2.3.3. Figures 2.9(a) and 2.9(b) show the false alarm rate and the miss detection probability, respectively, at different percentages of malicious nodes, when the iterative enhanced linear approach is used to find the fusion parameter. Comparing Figure 2.9(b) with Figure 2.8(b), it can be seen that the miss detection constraint is enforced when the enhanced procedure is applied. It can also be shown from both Figures 2.8(a) and 2.9(a) that the false alarm rate improves as the network size increases even under the same percentage of malicious nodes. In comparison with existing approaches, it is shown in Figure 2.9(b) that the majority voting rule cannot guarantee the miss detection requirement. Moreover, AND rule results in a very high miss detection probability, although it can achieve low false alarm rate. On the other hand, OR rule results in a very high false alarm rate, although it can achieve low miss detection probability. Hence, they are not reliable under malicious attacks. Example 2.2 - The closed-form solution without malicious node detection In this example, we assume that α = 25%, and the malicious nodes have P˜f = Pf and P˜m = 1 − Pd . The access point assumes that the attack probability is ‘1’, and obtain q accordingly. We assume that the percentage of malicious sensors is known or can be estimated at the access point. It is shown in Figure 2.10(a) that when the malicious detection approach is not employed, the performance is worst under the static attack strategy with Po = 1. It is observed that the false alarm rate is lower for the considered dynamic attacks as compared to the static attack. This is because that when the probability of attack is time varying, it could be very low in some sensing periods. It can be observed from Figure 2.10(a) that at a fixed percentage of malicious nodes, the false alarm rate decreases rapidly as the network size increases. This echoes our 51 0 10 −2 10 −4 10 −6 False alarm rate Qf 10 −8 10 −10 10 −12 10 n=60 n=70 n=80 n=90 n=100 −14 10 −16 10 −18 10 −20 10 15 20 25 30 α (%) (a) The false alarm rate. −1 10 n=60 n=70 n=80 n=90 n=100 Miss detection probability Qm Miss detection threshold −2 10 −3 10 −4 10 15 20 25 30 α (%) (b) The miss detection probability. Figure 2.8: The false alarm rate and miss detection probability using the linear approach. 52 0 10 −5 False alarm rate Qf 10 −10 10 n=60, enhanced linear n=70, enhanced linear n=80, enhanced linear n=90, enhanced linear n=100, enhanced linear n=60, majority voting n=60, OR rule −15 10 −20 10 15 20 25 30 α (%) (a) The false alarm rate. 0 Miss detection probability Qm 10 −1 10 Miss detection threshold −2 10 n=60, enhanced linear n=70, enhanced linear n=80, enhanced linear n=90, enhanced linear n=100, enhanced linear n=60, majority voting n=60, AND rule −3 10 −4 10 15 20 25 30 α (%) (b) The miss detection probability. Figure 2.9: The false alarm rate and the miss detection probability using the enhanced linear approach, and comparisons with AND rule, OR rule and majority voting rule. In general, AND rule results in very high miss detection probability, although it can achieve low false alarm rate. On the other hand, OR rule results in a very high false alarm rate, although it can achieve low miss detection probability. 53 analytical results presented in Section 2.5. The miss detection probability versus the network size is plotted in Figure 2.10(b). It is clear that the miss detection constraint is met, and there is a good margin for improvement that can be achieved using the adaptive fusion scheme. This margin is mainly due to the choice of q, where the access point assumed that the attack probability is ‘1’. Example 2.3 - Adaptive fusion: closed-form solution with malicious node detection In this example, we use the same settings as in Example 2.2. Malicious node detection is applied and the value of q is adapted based on the detected malicious behavior. Here, we use δ0,f = 0.07, δ0,m = 0.2, δ1 = 0.4, and δ2 = 0.3. Figure 2.10(a) shows the overall false alarm rate averaged over 104 observation periods when Nth = 100. We assume that Nth,2 is larger than the considered observation interval; hence, the counters will not be reset. The results are further averaged over 102 iterations to get more accurate results. It can be seen that significant performance improvement is achieved for both static and dynamic attacks when the adaptive fusion with malicious node detection is employed. Figure 2.10(b) shows that the miss detection constraint is satisfied for all cases. The non-smoothness of the curves is mainly due to tuning the integer-valued scheme parameters to satisfy the miss detection constraint. It should be emphasized that the thresholds δ0,f , δ0,m have a direct impact of the performance of the malicious node detection scheme and they could be further optimized to improve the performance. In the simulations, we added the condition that when Pˆa,f (i) > λp,f or Pˆa,m (i) > λp,m ∀i, the access point will discard node i only if Pˆa,f (i) > 0.5 or Pˆa,m (i) > 0.5 In Figure 2.11, we show the effect of the observation threshold Nth on the false alarm rate of the malicious node detection scheme (ηf ) for both static and dynamic attacks when the adaptive fusion is employed. Here, we set n = 30. The results are 54 0 10 Dynamic attack, without detection Static attack, without detection Dynamic attack, with detection Static attack, with detection −1 False alarm rate 10 −2 10 −3 10 −4 10 20 25 30 35 40 45 n 50 55 60 65 70 (a) The false alarm rate. −1 10 Dynamic attack, without detection Static attack, without detection Static attack, with detection Dynamic attack, with detection Miss detection threshold −2 Miss detection probability 10 −3 10 −4 10 20 25 30 35 40 45 n 50 55 60 65 70 (b) The miss detection probability. Figure 2.10: The false alarm rate and miss detection probability under static and dynamic attacks with and without the malicious node detection scheme. 55 Static attack Dynamic attack 0.016 False alarm rate ηf 0.014 0.012 0.01 0.008 0.006 60 65 70 75 80 Nth 85 90 95 100 Figure 2.11: The malicious node detection false alarm rate ηf vs. the observation threshold Nth for static and dynamic attacks, when n = 30 and α = 25%. The results are the average of N = 103 observations, each is further averaged over 103 iterations. the average of 103 observations each is further averaged over 103 iterations. Larger Nth would generally result in a lower ηf , since collecting more observations will result in more accurate statistics. In Figure 2.12(a), we show the effect of the observation interval N on the detection accuracy of the malicious node detection scheme (ηd ). It is clear that malicious nodes launching dynamic attack require longer observation interval to be detected than nodes adopting static attack. In general, it is clear from Figure 2.12(a) that the proposed malicious node detection scheme is efficient and provides very high detection accuracy. In Figure 2.12(b), the false alarm rate of the malicious node detection scheme is plotted versus the observation interval. As expected, it is shown that ηF decreases as more 56 0 Detection accuracy ηd 10 −0.01 10 −0.02 10 Dynamic attack Static attack −0.03 10 100 150 200 250 300 350 400 450 Observation interval (N) 500 550 600 (a) The detection accuracy −1 10 Dynamic attack Static Attack False alarm rate ηf −2 10 −3 10 −4 10 100 150 200 250 300 350 400 450 Observation interval (N) 500 550 600 (b) The false alarm rate. Figure 2.12: The effect of the observation interval (N ) on the detection accuracy ηd and the false alarm rate ηf for static and dynamic attacks using Nth = 100 and n = 30. The results are averaged over 4 × 103 iterations. 57 observations are available at the access point. 2.8 Summary In this chapter, we considered the q-out-of-m fusion rule for SENMA networks under Byzantine attacks. Both static and dynamic attack strategies were discussed. We proposed simplified q-out-of-m fusion schemes by exploiting the linear relationship between the scheme parameters and the network size. We also derived a near-optimal closed-form solution for the fusion threshold based on the central limit theorem. An important observation is that, even if the percentage of malicious sensors remains fixed, the false alarm rate diminishes exponentially with the network size. This implies that for a fixed percentage of malicious nodes, we can improve the network performance significantly by increasing the density of the nodes. Furthermore, we obtained an upper bound on the percentage of malicious nodes that can be tolerated using the qout-of-m rule. It is found that the upper bound is determined by the sensors’ detection probability and the attack strategies of the malicious nodes. Finally, we proposed an effective malicious node detection scheme for adaptive data fusion under time-varying attacks. The detection procedure is analyzed using the entropy-based trust model, and has shown to be optimal from the information theory point of view. It was observed that nodes launching dynamic attacks take longer time and more complex procedures to be detected as compared to those conducting static attacks. The adaptive fusion procedure has shown to provide significant improvement in the system performance under both static and dynamic attacks. Further research can be conducted on adaptive detection under Byzantine attacks with soft decision reports. 58 Chapter 3 Mobile Access Coordinated Wireless Sensor Networks – Design and Analysis In this chapter, we propose a novel mobile access coordinated wireless sensor network (MC-WSN) architecture for reliable, efficient, and time-sensitive information exchange. In conventional sensor networks with mobile access points (SENMA), the mobile access (MA) points traverse the network to collect information directly from individual sensors. While simplifying the routing process, a major limitation with SENMA is that a transmission is made only if an MA visits the corresponding source node; thus, data transmission is limited by the physical speed of the MAs and the length of their trajectory, resulting in low throughput and large delay. The proposed MC-WSN effectively resolves this problem through hop number control. More specifically, with active network development and topology design, the number of hops from any sensor to a mobile access can be limited to a pre-specified number. In this chapter, c �2013 IEEE. Reprinted, with permission, from M. Abdelhakim, J. Ren, and T. Li, “Mobile Access Coordinated Wireless Sensor Networks – Topology Design and Throughput Analysis,” IEEE Global Communications Conference, 2013 [43], and M. Abdelhakim, L. Lightfoot, J. Ren, and T. Li, “Architecture Design of Mobile Access Coordinated Wireless Sensor Networks,” IEEE International Conference on Communications, Jun. 2013 [78]. 59 we discuss the optimal topology design for MC-WSN such that the average number of hops between the source and its nearest sink is minimized, and analyze the performance of MC-WSN in terms of throughput, stability, delay, and energy efficiency by exploiting tools in information theory, queuing theory, and radio energy dissipation model. It is shown that under stable system conditions, MC-WSN achieves much higher throughput and significantly lower delay and energy consumption than that of SENMA. The effectiveness of the proposed approaches are demonstrated through simulation results. 3.1 Introduction Wireless sensor networks (WSNs) have been identified as a key enabling technology for various military and civilian applications, such as reconnaissance, surveillance, environmental monitoring, emergency response, smart transportation, and target tracking. Along with recent advances in remote control technologies, Unmanned Aerial Vehicles (UAVs) have been utilized in wireless sensor networks for data collection [17, 19], as well as for sensor management and network coordination. Network deployment through UAV has also been explored in literature [79, 80]. For efficient and reliable communication over large-scale networks, sensor network with mobile access points (SENMA) was proposed in [17]. In SENMA, the mobile access points (MAs) traverse the network to collect the sensing information directly from the sensor nodes. SENMA has been considered for military applications, where small low-altitude unmanned aerial vehicles (UAVs) serve as the mobile access points that collect sensing information for surveillance, reconnaissance and collaborative spectrum sensing [81]. When the energy consumption at the MAs is not of a concern, SENMA improves the energy efficiency of the individual sensor nodes over ad-hoc networks by relieving sensors from complex and energy-consuming routing functions. 60 While simplifying the routing process, a major limitation with SENMA is that a transmission is made only if an MA visits the corresponding source node; thus, data transmission is largely limited by the physical speed of the MAs and the length of their trajectory, resulting in low throughput and large delay. This makes SENMA undesirable for time-sensitive applications. As an effort to solve this problem, in this work, we propose a mobile access coordinated wireless sensor networks (MC-WSN) for time-sensitive, reliable, and energyefficient information exchange. In MC-WSN, the whole network is divided into cells, each is covered by one MA, and served with powerful center cluster head (CCH) located at the middle of the cell, and multiple ring cluster heads (RCHs) uniformly distributed along a ring in the cell. The MAs coordinate the network through deploying, replacing and recharging the nodes. They are also responsible for enhancing the network security, by detecting compromised nodes then replacing them. Data transmission from sensor nodes to the MA goes through simple routing with cluster heads (CHs), CCH or RCHs serving as relay nodes. As in SENMA, the senors are not involved in the routing process. A major feature of MC-WSN is that: Through active network deployment and topology design, the number of hops from any sensor to the MA can be limited to a pre-specified number. As will be shown, the hop number control, in turn, results in better system performance in throughput, delay, energy efficiency, and security management. For performance evaluation of the proposed architecture, we first discuss optimal topology design for MC-WSN such that the average number of hops between the source and its nearest sink is minimized, then analyze the performance of MC-WSN in terms of throughput, stability, delay, and energy efficiency. As an important measure of network performance, throughput is generally defined as the amount of information that can be successfully transmitted over a network, 61 and is largely determined by the network model and transmission protocols. Existing work on throughput analysis is versatile [22–24, 82–85], including one-hop centralized cases [82, 83] and ad-hoc cases [22, 84, 85]. There are also research on systems with mobile nodes [28, 86] and systems with mobile access points, like SENMA [17]. In SENMA, as there is a direct link between each sensor and the mobile sink, the system throughput is significantly superior to that of ad-hoc sensor networks [17]. In [22], the throughput of random ad-hoc networks is studied. It was shown that the throughput obtained by each node vanishes as the number of nodes in the network increases. More specifically, for an ad-hoc network containing n nodes, the throughput � � W obtainable by each node is O √ bit-meters/sec, where W is the maximum capacn ity of each link in the network. Note that the size or density of an ad-hoc network or a wireless sensor network plays a critical role in network performance. This result indicates that for reliable and efficient communications, the network cannot be completely structureless, but should have a well-defined structure while maintaining sufficient flexibility. This thought has actually been reflected in the merging of centralized and ad-hoc networks, leading to ad-hoc networks with structures, known as hybrid networks [44, 87]. As will be shown in Section 3.2, the proposed MC-WSN is also an example of hybrid network: it has a hierarchical structure supported by the CCH, RCHs, and CHs; at the same time, it also allows partially ad-hoc routing for network flexibility and diversity. In this chapter, we analyze the throughput of MC-WSN under both single path and multiplath routing. We evaluate the average per node throughput and compare it with that of SENMA. It is observed that the throughput of MC-WSN is independent of the physical speed of the MA, and hence is orders of magnitude higher than that of the conventional SENMA. Throughput is closely related to network stability and delay performance. For a 62 system to be stable, the arrival rate at each node cannot be larger than the service rate, which is bounded by the corresponding throughput. At the same time, to ensure bounded delay in the transmission, the system has to be stable. The major challenge for stability and delay analysis in wireless networks lies in the dependency among different queues along the routing path. For example, we have dependency between the inter-arrival times (which measures the time difference between two successive arrivals) and service times at each of the intermediate queues, and dependency between service times at different queues. Due to these dependencies, network analysis becomes highly complicated and intractable. Fortunately, it was observed that when the network is densely connected with moderate to heavy traffic loads, the dependencies between the inter-arrival times and service times can be eliminated by merging or multiplexing multiple packet streams at each link. This is known as the Klienrock independence assumption, and has shown to be a valid model for network analysis [88]. In this work, based on the Klienrock independence assumption and queuing modeling/analyzing theorems (mainly Burke’s theorem and Little’s Theorem), we establish the queuing model for the CHs in MC-WSN, analyze the stability and delay of the network, while highlighting their relationship with the throughput. The major contributions in this chapter can be summarized as follows: • We propose a reliable and efficient mobile access coordinated WSN (MC-WSN) architecture for time-sensitive information exchange. The MAs coordinate the network through node deployment, replacement, recharging, malicious node detection, and data collection. The energy efficiency for individual sensors is maximized as they are not involved in the routing process, and do not need to receive beacon signals from the MA. Through active network deployment, the number of hops from any sensor to its corresponding MA can be limited to a pre-specified 63 number. The hop number control ensures efficient system performance, and also makes the quantitative characterization of MC-WSN (in terms of throughput, stability, delay, and energy efficiency) more tractable. • We present an optimal topology design for MC-WSN such that the average number of hops between a sensor and its nearest sink is minimized. • We calculate the throughput of MC-WSN considering both single path and multiplath routing between each source and its corresponding sink. More specifically: (i) we analyze the throughput from an information theoretic perspective, and show that as the packet length gets large, the throughput approximately equals to the average normalized information that passes through the channel between a source and its sink; (ii) we illustrate the effect of the number of hops on the throughput, and show that the throughput diminishes exponentially as the number of hops increases; (iii) we show that the throughput of MC-WSN is independent of the physical speed of the MA and the length of its trajectory, and is orders or magnitude higher than that of SENMA. • We establish the queuing model for the cluster heads based on the Klienrock independence assumption and Burke’s theorem. We prove that the traffic at each CH can be modeled as an independent M/M/1 queue, by showing that: (i) the service process of each queue can be modeled as a Poisson process and is independent from node to node; (ii) the arrival process at each queue can be modeled as a Poisson process. We calculate the arrival rate and service rate of individual CHs, and derive the necessary conditions for the stability of MCWSN. It is shown that the system stability largely relies on the arrival rate and the throughput, which maps to conditions on scheduling, number of channels, signal to noise ratio (SNR), as well as the bound on the number of CHs that can 64 be served by each sink (either CCH or RCH). • We conduct delay analysis for MC-WSN and calculate the average delay for a packet to reach its nearest sink in both single path case and multipath case. It is shown that the hop number control and the network uniformity achieved by MC-WSN can largely simplify the delay analysis. • We calculate the energy dissipated in the individual sensor nodes, and show that MC-WSN achieves higher energy efficiency over SENMA. Our analysis are demonstrated through numerical results. It is shown that under stable system conditions, MC-WSN achieves much higher throughput and considerably lower delay and energy consumption over SENMA. Overall, the hierarchical and heterogeneous structure makes MC-WSN a highly resilient, reliable, and scalable architecture. Moreover, the methods used here for network design and analysis provide insight for more general network modeling and evaluation. 3.1.1 Related Work on Network Performance Analysis – Throughput, Stability, and Delay Throughput performance The network model has a direct impact on the at- tained performance. For ad-hoc networks with multiple source-destination pairs, it was shown in [22] that the throughput of each node diminishes as the number of nodes in the network increases. The throughput analysis of one-hop many-to-one scenario was considered in [82,83], where multiple nodes directly communicate with a sink under a random multiple access protocol. More specifically, in [82], the throughput, capacity, and stability regions of random multiple access were analyzed under multipacket reception channel model (which allows simultaneous successful receptions of packets). It 65 was shown that as the packet size gets large, the asymptotic capacity region becomes equal to the throughput region. In [83], the asymptotic stable throughput (i.e., the limiting stable throughput as the number of users goes to infinity) of opportunistic slotted Aloha system was obtained. The results were applied to CDMA-based networks, where an optimal transmission protocol was analyzed in the case of a large spreading gain. Defining the channel utilization as the normalized throughput, i.e., the throughput divided by the maximum throughput, it was shown that slotted Aloha � � log(Nt ) can achieve 1 − O channel utilization, where Nt is the maximum number of N t simultaneous transmissions that would satisfy the signal to interference and noise ratio (SINR) requirement. Throughput of multihop many-to-one single-path regularly-structured canonical network, where there is no merging of different paths/chains connected to the sink, was considered in [23]. It was shown that with the random IEEE 802.11 MAC protocol, the throughput generally does not reach the maximum link capacity. However, proper routing can significantly improve the throughput performance. The throughput of multihop many-to-one network with uniformly deployed nodes and time division multiple access (TDMA) protocol was studied in [24]; it was shown that a throughput of W n can be achieved in a single-hop many-to-one scenario, however it is generally not achievable in multihop scenarios. The effect of clustering on improving the throughput was also investigated in [24], along with discussions on the trade-offs between throughput and energy efficiency. Allowing nodes to be mobile could improve the network throughput performance compared to fixed ad-hoc networks. In [28], the effect of the mobility of the nodes on the throughput performance was discussed, considering that the mobile nodes transmit only when they are close to the destination. The main idea in [28] is that for a random source-destination pair, the source splits the packet stream to as many mobile relays 66 as possible, then a relay delivers the data when it gets close to the destination. Data transmission is made over at most two hops, and the successful reception is determined based on having the SINR value greater than a certain threshold. This approach mainly relies on the diversity as well as the nodes’ mobility to improve the throughput. Under this setting, it was shown that the achieved throughput is independent of the number of nodes in the network, and hence is significantly superior to that of fixed adhoc networks. Possible limitations of this approach are the large energy consumption and complexity in dynamic scheduling associated with the mobility, the high cost of diversity, the large delay that would depend on the velocity of the nodes [85], and series security issues. In sensor networks with mobile access points, SENMA, a sensor can only transmit when an access point is within the sensor’s communication range [17]. Hence, the throughput is limited by the access point’s traversal speed and its trajectory length. In [19], mobile sinks are employed for data collection; each mobile sinks visits limited number of pre-defined collection points in the network. Each sensors routes its information close to the nearest collection point through multihop routing, then data is delivered to the sink that visits the corresponding location. The throughput of this network model was investigated in [19], and the effect of the speed of the sinks and their trajectory length on the throughput was discussed. Stability and delay performance Stability ensures that the quantity of interest, such as the queue length or delay, is kept within a bounded region or has a limiting distribution [89]. In other words, to ensure a bounded delay performance, the system should be stable. The stability analysis of systems employing Aloha MAC protocol or its variant can be found in [89–92]. Stability region was obtained by means of stochastic dominance [90, 91, 93], where an auxiliary dominant system is modeled in which the 67 lengths of the queues are larger than, or equal to, that of the original system. Hence, the stability of the dominant system presents sufficient conditions on the stability of the original system. For stable system operation, the arrival rate to each queue in the system should be lower than its service rate [89, 90, 93]. Note that the maximum service rate at a node is equal to the probability of successful transmission, i.e., the throughput. Delay analysis for wireless networks has been considered in previous work from different perspectives and considering different communication models. In [94], the delay-limited capacity was investigated for a single-hop single transmitter-receiver pair. That is, the analysis was mainly focused on the coding delay, and did not consider the queuing and the multiple access delays. Similar work can be found in [95]. In [91], stability and delay were characterized for simple two-user single-hop network using Aloha multiple access with multipacket reception capability, and the transmission probability that minimizes the delay was obtained. Analyzing stability and delay in large-scale multihop networks is challenging, due to the complex interactions and dependencies between the nodes/queues along the routing path(s) between a source to its destination. These challenges were highlighted in [88]. There are several existing approaches attempting to analyze the network performance taking into account dependencies between different queues [96–99]. However, most of the work in this area mainly focus on small-scale networks and/or consider special assumptions, such as deterministic service process. An attempt to find lower bound on the delay for multihop transmissions with multiple source-destination pairs and assuming fixed and equal link capacities can be found in [100]. The approach relies on obtaining a reduced system model, in which each group of adjacent nodes representing a bottleneck (only few nodes can transmit at the same time) are modeled by a single queue. Then, a lower bound on the delay is 68 obtained based on the reduced system. Tractable analysis for densely connected networks became possible with the introduction of the Klienrock independence assumption, which allows us to model each node in the network separately when there is sufficient merging/multiplexing of data streams at each link [88, 101]. Motivated by the Klienrock independence assumption, an endto-end delay distribution was analyzed in [102] when traffic aggregation is performed at the relay nodes. In [103], the delay of multihop ad-hoc networks was analyzed using the diffusion approximation, where each node is characterized as a separate queue with general distributions for the arrival and service processes (G/G/1 queue). In [104], the end-to-end delay distribution in multihop WSNs was obtained by modeling each hop along a route as a Geo/PH/1/M queue, in which the inter-arrival times are geometrically distributed and the service times are phase-type (PH) distributed. Note that the geometric distribution is the discrete analogue of the exponential distribution. Through empirical results, it was verified that the arrival process can be accurately represented by a Poisson distribution, which has exponentially distributed inter-arrival times. The delay performance in networks utilizing mobile nodes, such as in [17, 19, 28], will generally depend on the velocity of the corresponding nodes [85]. Hence, these network models would be inefficient for time-sensitive applications. In this chapter, after describing the proposed MC-WSN architecture and topology design, we present the network analysis. As will be shown, the MC-WSN performance is independent of the physical speed of the MA. 69 3.2 The Proposed Mobile Access Coordinated Wireless Sensor Network (MC-WSN) In this section, we describe the proposed MC-WSN architecture and highlight its major features. 3.2.1 General Description We assume the network is divided into cells of radius dc . Each cell contains a single powerful mobile access point (MA) and n uniformly deployed sensor nodes (SNs) that are arranged into NCH clusters. Each cluster is managed by a cluster head (CH), to which all the cluster members report their data. CHs then route the data to the MA [43, 78]. A powerful center cluster head (CCH) is employed in the middle of each cell, and K powerful ring cluster heads (RCH) are placed on a ring of radius Rt . The CCH and RCHs can establish direct communication with the MA or with other RCHs that are closer to the MA. All nodes within a distance Ro from the CCH route their data to the MA through the CCH. All other nodes route their data to the MA through the nearest RCH. If a sensor is within the MA’s coverage range, then direct communications can take place when permitted or needed. After receiving the data of the sensors, the MA delivers it to a Base Station (BS). The overall network architecture is illustrated in Figure 3.1. As will be illustrated in Section 3.3, the number of hops from any sensor to the MA can be limited to a pre-specified number through the deployment of CCH and RCHs. In the proposed MC-WSN architecture, the MA coordinates the sensors and resolves the node deployment issue as well as the energy consumption problem of wireless sensor networks. More specifically, the MAs are responsible for: (i) deploying nodes, (ii) replacing and recharging nodes, (iii) detecting malicious sensors, then removing and 70 RCH CCH RCH RCH RCH CCH RCH RCH RCH CCH RCH RCH Cluster head Mobile access Point Sensor node Base Station Center cluster head (CCH)/Ring cluster head (RCH) Figure 3.1: Proposed MC-WSN architecture. replacing them, (iv) collecting the information from sensors and delivering it to a BS. When an MA needs to be recharged or reloaded, it sends a request to the MA base. The base will send a new MA to the cell, and the substituted MA will be called back to the base for maintenance services. The MAs can move on the ground, and can also fly at low altitude. Each MA traverses its cell mainly for replacing or recharging low-energy sensor nodes and cluster heads, as well as removing the malicious nodes. The recharging can be performed in a wireless manner [105]. The MA moves physically for data collection only in the case when the routing paths do not work. Data collection from the sensors can be event based or periodic. Data transmissions 71 from SNs to CHs, between CHs, and from CCH/RCHs to the MA are made over different channels to avoid interference between different communication links. Let the communication range of each sensor node and CH be rc and Rc , respectively. CHs have larger storage capacity and longer communication range than SNs, i.e., Rc > rc . We assume shortest path routing between the CHs and the CCH/RCHs. Note that the sensors are not involved in the inter-cluster routing to minimize their energy consumption. Due to the MA-assisted active network deployment, we can assume that the nodes are uniformly distributed in the network. It is therefore reasonable to place the powerful RCHs at evenly spaced locations on the ring Rt . To maximize the throughput and minimize the delay of data transmission from the sensors to the MA, the number of hops needed in routing should be minimized. In Section 3.3, we discuss network topology design and obtain the optimal Rt and Ro that minimize the number of hops. 3.2.2 Major Features The main advantages of MC-WSN lie in: (i) multi-functionality of the mobile access; (ii) hop number control through topology design; and (iii) hierarchical and heterogeneous node deployment. More specifically, MC-WSN has the following features: • Controlled network development and prolonged network lifetime The proposed MC-WSN allows the MAs to manage the deployment of SNs and CHs. That is, the MA can add more nodes, relocate or replace exiting nodes. In addition, it can recharge or replace low-energy nodes. When a node has low remaining energy, it sends a control message to the MA notifying it with its energy level. The MA can then check and make the decision to replace the node or recharge it. Being coordinated by the MA, the MC-WSN architecture resolves the network deployment issue and can actively prolong the network lifetime. 72 • Time-sensitive data transmission In conventional SENMA, a transmission is made only if an MA visits the corresponding source node; thus, data transmission is limited by the physical speed of the MAs and the length of their trajectory, resulting in low throughput and large delay. In MC-WSN, the delay is effectively managed through hop number control, and is independent of the physical speed of the MA. • Enhanced network security First, the MAs can detect malicious SNs and CHs and replace them [45]. When the MA receives data from a node, it first authenticates the source and checks its identity. If the source passes the authentication procedure, the MA monitors the reports of each individual node and compares it with the final decision obtained through data fusion. Based on the observations over multiple sensing periods, the malicious nodes can be detected and removed [42]. Second, with hop number control, the delay from a sensor to the MA is limited within a pre-specified time duration under regular network conditions. If the actual delay is significantly larger, then an unexpected network event or network failure is detected. Third, it is difficult to get the MA itself compromised or destroyed, since it is much more powerful than other network nodes, and it moves randomly in the network where its location can be kept private [106]. • Efficient energy consumption The SNs have the most limited resources in wireless sensor networks. In the proposed MC-WSN, SNs only communicate with their nearest CHs, and are not involved in any inter-cluster routing. Also, unlike SENMA, SNs in MC-WSN do not need to receive the periodic beacon signal from the MA, and hence the energy efficiency is further improved. Note that the beacon signals in SENMA are used to notify SNs of the presence of the MA and 73 to indicate which sensor to transmit. • Enhanced network resilience, reliability and scalability: MC-WSN is a self-healing architecture, where the CCH and RCHs represent different options for data transmission to the MA. The diversity in multipath routing increases the resilience of the network. In the worst case when the routing paths do not work, the MA can traverse its cell for data collection. Overall, the hierarchical and heterogeneous structure makes the MC-WSN a highly resilient, reliable, and scalable architecture. 3.3 Network Topology Design In this section, we investigate network topology design of MC-WSN, and calculate the optimal radius Ro and the ring radius Rt that minimize the average number of hops from any CH to the MA. Note that under shortest path routing, the number of hops is proportional to the distance between the source and the sink. To minimize the number of hops, we design the topology such that the average distance between a cluster head and its nearest sink is minimized. In the proposed MC-WSN architecture, the average squared distance between any source and the corresponding sink (CCH/RCH) can be expressed as: d¯2 = 2K �� π/K θ=0 � π/K � R t θ=0 x=0 x=R0 � π/K � dc θ=0 � Ro x=Rt � � x2 fX (x)fθ (θ)dxdθ+ x2 − 2xRt cos(θ) + Rt2 � � fX (x)fθ (θ)dxdθ+ � x2 − 2xRt cos(θ) + Rt2 fX (x)fθ (θ)dxdθ , (3.1) where x is the distance from any CH to the center of the cell, and θ is the angle from 74 the CCH, as illustrated in Figure 3.2. Here, fX (x) is the PDF of x. Assuming that the CHs are uniformly distributed in a circle of radius dc , then fX (x) can be approximated 1 , ∀θ ∈ [0, 2π]. by fX (x) = 2x2 , and the PDF of θ is modeled as fθ (θ) = 2π d c Recall that K is the number of RCHs. Assume K > 1, and set ∂ d¯2 = 0, ∂Ro ∂ d¯2 = 0. ∂Rt πR We get the optimal Ro = 2K sin(t π ) , and Rt = K √ (3.2) 3−1 π π K sin( K )dc π )d . = 0.233K sin( K c It follows that Ro = 0.366dc . In summary, we have the following result. Proposition 3.1 Assuming a circular cell of radius dc , to minimize the number of hops in the MC-WSN architecture with one CCH and K RCHs, where K > 1, data transmission should be arranged as follows: (1) The CHs within a distance Ro = 0.366 dc from the center of the cell deliver their data to the MA through the CCH. (2) The CHs at a distance x from CCH, where Ro ≤ x < dc , deliver their data to the MA π )d . through the nearest RCH on the ring of radius Rt = 0.233K sin( K c With the optimal topology, the average squared distance from a CH to its nearest π )]2 . Assuming shortest path routing is available, sink is d¯2 = 0.5d2c − 0.047d2c K 2 [sin( K ¯ the average number of hops can be expressed as Nhop = Rd , where Rc is the comc munication range of the cluster heads. Note that as K increases, d¯ and consequently Nhop decrease. As can be seen, the maximum number of hops can be limited to a pre-specified number through the deployment of RCHs. 3.4 Throughput Analysis In this section, we analyze the throughput of the multihop MC-WSN architecture. After introducing the definition of the throughput in the single hop case, we analyze 75 = ! /K RCH /K d x Rtsin CCH RCH 2 (x -2xRtcos RCH 2 1/2 +Rt ) =0 Rt Ro Rt RCH Figure 3.2: MC-WSN with four powerful RCHs. the multihop throughput under both single path and multipath routing. 3.4.1 Definition of the Throughput We start with the single hop case. Assuming node i is transmitting to sink k, where k ∈ {0, 1, ..., K}. The throughput of node i to sink k, Ti,k , is defined as the average number of packets per slot that are initiated by node i and successfully delivered to k (ν) as the set of nodes that have their packets the intended receiver k [92]. Define RS successfully delivered to sink k in slot ν, where S is the set of nodes scheduled to transmit. Then, Ti,k can be expressed as:   T � 1 k (ν)] Ti,k = E  lim I[i ∈ RS T →∞ T = ν=1 T 1 � k (ν)}, P r{i ∈ RS T T →∞ lim ν=1 76 (3.3) where I(.) is the indication function. Let tki be a binary flag indicating that node i transmits data to sink k: tki = 1 means that sensor i is scheduled to transmit its data to the sink k, otherwise tki = 0. Similarly, let rik be a binary flag indicating that the data of node i is successfully received at the intended destination k (CCH or RCH). Note that the transmission from the powerful CCH/RCH to the MA can be made at high-power and high-rate. Also, with the active network deployment performed by the MA, the data from each sensor to its CH can be transmitted over a single hop using a collision-free MAC protocol. Thus, we focus on data transmission from the CH of the originating node to its corresponding CCH/RCH. Assume that the packet reception from slot to slot is an i.i.d process, then it follows that: Ti,k = P r{rik = 1|tki = 1}P r{tki = 1}. (3.4) In the following, we analyze Ti,k from the information theory perspective, by discussing the relationship between Ti,k and the mutual information between the packet transmitted from CH i and the packet received at sink k. For each slot, define Xik as the transmitted packet from CH i to sink k, where ˜ k be the non-zero packets of X k = 0 means that node i is not transmitting. Let X i i ˜ k [82]. Assuming that sink k receives packets from multiple nodes Xik , then Xik = tki X i in a collision-free manner. Define Yk as the received vector at sink k, where the ith element in Yk is the received packet from CH i. Let rk be the vector whose ith element is rik . It has been shown in [82] that the mutual information between Xik and Yk can be written as a function of the throughput of CH i to sink k (Ti,k ) as follows: ˜ k )Ti,k , I(Xik , Yk ) = I(tki , rk ) + H(X i (3.5) where I(x, y) is the mutual information between x and y, and H(x) is the entropy 77 ˜ k ), which is measured in number of packets per slot. of x. Let Ikp = I(Xik , Yk )/H(X i In general, Ti,k ≤ Ikp . Note that tki is binary, i.e., H(tki ) ≤ 1, which implies that ˜ k ) → ∞, I(tk , rk ) ≤ H(tk ) ≤ 1. As a result, if the packet length gets large, i.e., H(X i i i then we have Ti,k � Ikp . From the information theory perceptive, this shows that: Ti,k is the average normalized information (measured in packets per slot) passed through the channel between CH i and sink k. 3.4.2 Multihop Single Path Routing Case In this subsection, we analyze the throughput of a node in the case when there is a pre-defined, multihop single path from each CH to its corresponding sink. Consider that CH i requires Nik hops to reach sink k. Nik is based on the network architecture, topology, and routing scheme. Let the ideal or shortest path from CH i to sink k be i k → i k → ...i1 → i0 , where i k is the source CH i and i0 is the Ni Ni −1 Ni k sink k. This is illustrated in Figure 3.3. Let ti,h be a binary flag at hop h, indicating that CH ih is scheduled to relay a packet of CH i to CH ih−1 along the route to sink k. k be a binary flag indicating that the data of CH i is successfully received Also, let ri,h at CH ih−1 along the same route to sink k. It follows that, at each particular time slot, we have: k = 1} = P r{r k = 1|tk = 1}P r{tk = 1}. P r{ri,h i,h i,h i,h (3.6) Consider that a packet of CH i is received at sink k in slot ν. This implies that there exists a scheduling slot vector ν = [ν − ∆ν k , ..., ν − ∆ν1 , ν], such that all Ni −1 nodes along the routing path from i to the sink successfully transmit the packet of node i. More specifically, node ih is scheduled to transmit in slot ν − ∆νh−1 , where 78 iNk i ik Ni -1 ik Ni -2 i0 Sink k i Figure 3.3: Multihop single path between node i and sink k. ∆νx > ∆νy , ∀x > y and ∆ν0 = 0. Along slot vector ν, define the transmission flag of CH i as tki (ν), such that tki (ν) = [1, .., 1] when CH i transmits a packet to sink k and the transmission at the last hop (at CH i1 ) occurs in slot ν. Note that if the relay at the last hop along the transmission path from i to the sink transmits the packet of node i, then it implies that all intermediate hops were scheduled to transmit in prior slots. That is, we have P r{tki (ν) = 1} = P r{tki,1 (ν) = 1, ..., tk k (ν − ∆ν k ) = 1}. N −1 i,N i (3.7) i Omit the slot index, (3.7) can be simplified as: P r{tki = 1} = P r{tki,1 = 1, ..., tk k = i,N i 1}. For the throughput calculation here, we do not consider retransmissions of packets. Assuming that there exists a schedule such that the source CH and all its intermediate relays are assigned time slots to transmit/forward the source’s data, and assuming that the transmissions in all slots are i.i.d, then we can drop the slot index from the throughput expression. In the case when the amplify-and-forward protocol is adopted k ’s are independent at different hops, it in the relaying process, which implies that ri,h 79 follows from (3.4) and (3.6) that: Nk Ti,k = P r{tki,1 = 1, ..., tk k = 1} i,N i Nk = P r{tki = 1} i � i � k = 1|tk = 1}, P r{ri,h i,h h=1 k = 1|tk = 1}. P r{ri,h i,h (3.8) h=1 Note that if decode-and-forward is employed at the intermediate CHs instead of the amplify-and-forward, then the errors in one hop can be corrected at another hop experiencing better channel conditions. This is at the expense of increased complexity and delay at all hops. It is noted from equation (3.8) that the throughput depends on the employed PHY, MAC, routing protocols as well as the network environment. tki is related to the MAC protocol, while rik is related to the PHY protocol. The routing protocol determines the path and the number of hops from a source to its destination. Denote Nintf as the minimum separation between links for bandwidth reuse. That is, when a transmission is made by a CH, other nodes within a distance of Nintf Rc from the transmitting CH should remain silent or use another orthogonal channel. Let nk be the number of nodes connected to sink k. Then we have the following result. Lemma 3.1 When TDMA is used, each node connected to sink k can transmit with a probability P (tki = 1) ≥ N 1 n . If hybrid TDMA/FDMA is used, and NF req is the intf k number of frequencies available for simultaneous CHs transmissions within the same N interference region, then P (tki = 1) ≥ N F reqn . intf k Proof: The proof is provided in Appendix A. � We now evaluate the probability of successful reception, which can be viewed as 80 a condition on the signal to interference and noise ratio SINR. Let Pi be the power of node i that is exponentially distributed with mean P¯i . That is, P r{Pi = x} = � � P¯ −1 exp −P¯ −1 x . Assume P¯i = P¯ ∀i. Suppose a transmission is made from li to lj , where li and lj are the locations of the transmitting and receiving nodes, respectively, and Li,j = |li −lj | is the distance between them. The SINR in the transmission from i to j, SIN Ri,j , can be expressed as SIN Ri,j = −β Li,j Pi � −β , No + Lx,j Px i x∈X x�=i where No is the noise power, X i is the set of all radios transmitting on the same channel and in the same time slot as node i, and β ≥ 2 is the path loss exponent (β = 2 in free space environment). In structured networks, the assignment of channels and time slots can be managed to minimize the interference. In this case, the interference term becomes negligible, and we get SIN Ri,j = −β Li,j Pi No . Hence, we use SIN R and SN R interchangeably. We can write k = 1|tk = 1} = P r{SIN R P r{ri,h ih ,ih−1 > γ}, i,h (3.9) where γ is the SINR threshold for successful transmission. Note that if the transmitter power is fixed and is affected by a Rayleigh fading channel, the received power will be exponentially distributed [107]. In other words, this model is equivalent to having a fixed-power transmitted signal passing through a Rayleigh fading channel. In both cases, the received SINR will be exponentially distributed [108]. Define λi,h = � �β γNo Lih ,ih−1 as the minimum transmit power of node ih to guarantee the SINR 81 threshold at hop h − 1. We have, P r{SIN Rih ,ih−1 > γ} = P r{Pih > λi,h } � � � ∞ 1 1 = ¯ exp − P¯ s ds s=λi,h P � �β � No � = exp −γ ¯ Lih ,ih−1 . P (3.10) � �−β P¯ Li ,i h h−1 Note that the average SNR at hop h can be expressed as: SN Rh = . If No � � Lih ,ih−1 = L ∀h, then SN Rh = SN R and P r{SIN Rih ,ih−1 > γ} = exp − SNγ R ∀h. From (3.8) - (3.10), we get Nk � �β � No � Ti,k = = 1} exp −γ ¯ Lih ,ih−1 P h=1   k N  i �  N �  �β  o k = P r{ti = 1} exp −γ ¯ Lih ,ih−1 .   P   P r{tki i � (3.11) h=1 Theorem 3.1 In a multihop MC-WSN network, assuming exponentially distributed transmit powers, the throughput of CH i along a predefined single routing path to sink k is: Ti,k = P r{tki = 1} exp      Nik −κ �� h=1 Lih ,ih−1   �β    , (3.12) where Nik is the number of hops in CH i’s transmission, P r{tki = 1} is the probability that CH i and all its intermediate relaying nodes are scheduled to transmit the data of CH i to sink k, β is the path loss exponent of the channel, Lx,y is the distance between nodes x and y, and κ = γ NP¯o . Remark 3.1 It can be seen from Theorem 3.1 that if the hops are equidistant, the 82 throughput will decrease as the number of hops increases. More specifically, when Lih−1 ,ih = L, ∀h ∈ {1, 2, .., Nik }, we get Ti,k ∝ exp{−Nik }. It follows that: lim Ti,k = 0. (3.13) Nik →∞ This result justifies our motivation of limiting the number of hops from each sensor to the MA to a pre-specified number through the topology design and deployment of CCH and RCHs. With hop number control, we can have better control and management over the system throughput, delay, security, and energy efficiency. Remark 3.2 It is worth mentioning that if the distance between the source and the sink is fixed, then larger number of hops would correspond to lower per-hop distance, and consequently resulting in an improved performance at low SN R values. However, this would request higher node density, and hence an increase in the number of nodes in each cell. In this chapter, under the assumption that the number of nodes in each cell is fixed, we will mainly consider the case of fixed per-hop distance. Now we obtain the overall average per node throughput. Define PA as the probk ability that a cluster head lies in the coverage area of sink k. That is, its nearest sink N is sink k. Following Lemma 3.1, we set P (tki = 1) = N F reqn , which is a conservative intf k measure for the per node transmission probability. Recall that NCH is the total number of CHs, then the number of CHs that transmit to sink k is nk = PA NCH . Hence, k the overall average per node transmission probability in the cell, P¯t , can be expressed as: K � NF req NF req = PA k Nintf nk k Nintf PA NCH k k=0 k=0 NF req = (K + 1) , Nintf NCH P¯t = K � PA 83 (3.14) where Nintf is the bandwidth reuse measure, and NF req is the number of frequencies available for simultaneous cluster head transmissions. For equidistant hops with length Rc , the overall average per node throughput is expressed as � � β T¯ = P¯t exp −κNhop Rc , (3.15) where Nhop is the average number of hops from a CH to its corresponding sink in each cell, and is obtained in Section 3.3. 3.4.3 Multihop Multipath Routing Case In the previous subsection, we considered the case when there is a single pre-defined path between a CH and a sink. Note that, in general, the transmission can go through different paths due to the existence of network diversity. In this section, we formulate the throughput for the multipath case. We have the following result: Theorem 3.2 Let N be the maximum number of hops from a CH to its sink along any routing path. Consider that for each hop number l ∈ {1, 2, ..., N }, there are Pi,l possible l-hop paths from CH i to sink k. Let T (i|Nik = l, Pik = p) be the throughput that can be achieved along one of the l-hop paths from source i to sink k assuming the path Pik = p, then the throughput of node i can be calculated as: P Ti,k = i,l N � � l=1 p=1 T (i|Nik = l, Pik = p) Pr{Pik = p|Nik = l} Pr{Nik = l}. (3.16) Here, l-hop path means a path that consists of l hops. It is noted that T (i|Nik = l, Pik = p) can be obtained from Theorem 3.1 by substituting Nik = l, which is the number of hops along the particular path Pik = p. The term Pr{Pik = p|Nik = l} depends on the routing protocol. It should be emphasized that when multiple routes 84 are enabled, the utilized scheduling protocol, and hence P (tki = 1), could be different than that in the single routing path case. 3.4.4 Total Network Throughput The network throughput, Υ, is defined as the average number of packets received successfully from all clusters per unit time. Let N k be the set of CHs that transmit to sink k. Following Theorems 3.1 and 3.2, the total throughput of the proposed MC-WSN architecture with K RCHs and a CCH can be obtained as: Υ = K � � Ti,k k=0 i∈N k = Pi,l K � � N � � k=0 i∈N k l=1 p=1 = Pi,l K � � N � � k=0 i∈N k l=1 p=1 T (i|Nik = l, Pik = p) Pr{Pik = p|Nik = l} Pr{Nik = l} pki (p) exp    −κ × Pr{Nik = l}, l � � h=1 Lk k i ,i (p) h h−1 where nk is the number of nodes connected to sink k, L k k i ,i  �β   Pr{Pik = p|Nik = l} (3.17) (p) is the length between h h−1 CHs ikh and ikh−1 along path p, and pki (p) is the transmission probability of CH i along path p to sink k. 3.5 System Stability and Delay Analysis In this section, we analyze the stability and delay of MC-WSN by exploiting tools in queuing theory. After introducing the independence assumption and modeling theorems, we establish the queuing model of the CHs, and then perform the stability and 85 delay analysis. 3.5.1 Queue Independence Assumption and Modeling Theorems The difficulty in the system stability and delay analysis in communication networks is mainly attributed to the dependency between different queues along the routing path of a packet. Let the arrival time of packet j at a queue be Tj . Then the inter-arrival time between packets j and j + 1 is Aj = Tj+1 − Tj . The service time at a node is generally defined as the duration between the time the packet is at the head of the node’s queue until it is successfully transmitted. In other words, the service time equals to the packet length divided by the service rate. 3.5.1.1 Klienrock Independence Assumption In networks of tandem queues, there is generally a correlation between the inter-arrival times and the packet lengths/service times at the intermediate queues [88]. For example, if the packets retain their lengths when they are forwarded at different hops, considering that the link rates are fixed, then we have: (i) dependency between the inter-arrival times and service times at each of the intermediate queues; (ii) dependency between service times at different queues. Due to these dependencies, network analysis becomes highly complicated and intractable. However, it was observed that when the network is densely connected with moderate to heavy traffic loads, these dependency can be removed [101]. In other words, the dependencies between the inter-arrival times and service times can largely be eliminated by merging multiple packet streams on each link [88]. This is known as the Klienrock independence assumption. More specifically, in a densely connected network 86 with moderate to heavy traffic loads, if we have Poisson arrival processes at the entry points of the network, and exponentially distributed service times at each link, then the multiplexing of the independent Poisson packet streams at every node has the effect similar to restoring the independence between the inter-arrival times and service times [88]. The underlying argument is that: if packets received by a node from different sources are ordered in the queue by the order they arrive in a first-come first-served manner, the resulted queues through the packet multiplexing/merging process become independent. The idea here is similar to the interleaving process in communication systems, which randomizes consecutive symbols and validates the independence assumption among all the symbols. The independence assumption was verified through experiments in [88] using different network topologies (star, diamond, and k-connect networks) under uniform and non-uniform traffic. It was shown that the independence assumption provides a valid model for network analysis. It should be noted that, having an exponentially distributed packet lengths and deterministic service process is equivalent to having fixed packet lengths and Poisson service process. Both cases will result in an exponentially distributed service time. The independence assumption allows us to treat each node in the network independently as an M/M/1 queue [88], and hence enables tractable network analysis. 3.5.1.2 Burke’s Theorem and Little’s Theorem Next, we introduce two important queue modeling and analyzing theorems that will be used in our analysis in the following subsections. The first one is the Burke’s theorem [101], which describes the relationship between the arrival flow and the service flow. 87 Burke’s theorem: Consider an M/M/1, M/M/m, or M/M/∞ system with Poisson arrival process of rate λx , then the departure process is Poisson with rate λx . The second one is the well-known Little’s theorem [101], which formulates the average delay per packet as a function of the average arrival rate and the number of packets in the system. Little’s Theorem: Let the steady state average number of packets in a system be Nx and the average packet arrival rate be λx , then the average delay per packet in the x system Dx = N λx . In the next subsection, we characterize the queuing model of cluster heads in MCWSN. 3.5.2 Queuing Model Characterization for MC-WSN 3.5.2.1 Modeling the Arrival and Service Processes In this subsection, we provide the queuing model for each individual CHs in MC-WSN, and show that the Klienrock independence assumption provides an accurate model for stability and delay analysis of the MC-WSN network. More specifically, we have the following result: Theorem 3.3 (i) The service process of each queue can be modeled as a Poisson process and is independent from node to node. (ii) The arrival process at each queue can be modeled as a Poisson process. Proof: (i) Service Process: Due to the exponentially distributed SN R, different links in the MC-WSN multihop transmissions have different service times that are independent from link to link. Recall that the probability of successful transmission (i.e., the throughput) between node i and j is Ti,j . Then, the number of packets successfully transmitted from i to j in c slots can be modeled as a Binomial random 88 variable with parameters c and Ti,j [109]. According to the law of small numbers, when large time interval is considered, i.e., c → ∞, the Binomial distribution with parameters c and Ti,j converges to a Poisson distribution with parameter S = cTi,j [110]. (ii) Arrival process: All the CHs can be divided into two groups: (a) CHs that only transmit packets generated from their own clusters. (b) CHs that serve as relays for other CHs, and hence transmit their generated traffic and also the relay traffic. Without loss of generality, consider two CHs i and j, where CH i receives data from its cluster members (sensors) only, while CH j receives data from its cluster members as well as from CH i. Note that in general the aggregation of several independent and identically distributed traffic can be accurately approximated as a Poisson process [101] (p. 165). Hence, the arrival process of packets from sensors to their corresponding CHs can be modeled as a Poisson process. That is, CH i has a Poisson arrival process. Next, we will show that CH j has an overall Poisson arrival process as well. Since the service process from each CH is Poisson, therefore CH i is an M/M/1 queue. It follows from the Burke’s theorem that the departures process of CH i is Poisson distributed. The Poisson departures from CH i arrive at CH j and are merged with data from sensors in cluster j, which is also Poisson. Since the summation of independent �n Poisson process of rates {λ1 , ..., λn } is a Poisson process of rate λt = i λi [101], then the overall arrival process at CH j has a Poisson distribution. This proof can be directly extended to CHs that serve as a relay for more than one CH. � Based on the discussions above, each CH in the network can be modeled as an independent M/M/1 queue. Our stability and delay analysis are based on this model. 3.5.2.2 Calculation of Arrival and Service Rates Here, we calculate the arrival and service rates of CHs by considering different traffic loads at the CHs in the network. To do this, we first group the CHs based on their 89 locations and the number of hops to their corresponding sink (either the CCH or an RCH). • For the CCH: Due to the uniformity of the MC-WSN structure achieved by the MA, it is reasonable to assume that all CHs at the same hop level from the CCH carry approximately the same amount of traffic. Hence, for delay analysis, we do not distinguish between nodes within the same hop level from the CCH. • For the RCHs: The traffic around the RCH could be different due to the unequal areas. More specifically, within a particular RCH coverage area (illustrated in Figure 3.2), the outer region, where x > Rt , and the inner region, where Ro < x ≤ Rt , have different traffic loads. This is because the area of the outer region is larger than that of the inner region, which corresponds to larger number of hops and more CHs in the outer region. Therefore, when analyzing the performance of the CHs around the RCH, we identify the nodes by their hop level as well as their region from the RCH (inner or outer region). Nodes within the same hop level of a particular region from a RCH are not distinguished. From the discussions above, without loss of generality, we define the following: O is the group of nodes in the hth hop level from sink k and in the outer region. • gh,k I is the group of nodes in the hth hop level from sink k and in the Similarly, gh,k inner region. The superscript O and I are omitted when referring to the CCH. I O I • λO i,h,k and λi,h,k are the total arrival rates at CH i ∈ gh,k and i ∈ gh,k , respec- tively. I O I • sO i,h,k and si,h,k are the service rates at CH i ∈ gh,k and i ∈ gh,k , respectively. Take a CH at the hth hop from the outer region of sink k as an example. Based on the independence assumption, it can be modeled as an M/M/1 queue with total arrival 90 O rate λO i,h,k and service rate si,h,k . The total arrival rate at a CH is the sum of the arrivals of packets from its own cluster members and the arrivals of packets forwarded from other cluster heads to be delivered to the nearest sink. We refer to the former as the “generated arrival rate”, ˜ g,i , while the latter is referred to as “forwarded arrivals rates”, denoted denoted by λ ˜ O or λ ˜ I , depending on where the CH resides. Following our discussions in by λ f,i,k f,i,k the previous subsection, we assume that the traffic generated from each cluster in the network follows a Poisson process with equal rates, and is independent of the hop level ˜ g,i = λ ∀i. In the following, we consider the or the location in the network. That is, λ analysis of CHs in the outer regions of the sinks (RCHs). The analysis of CHs in the inner regions as well as those within the coverage area of the CCH can be performed in a similar manner. O based on the Burke’s theorem. We characterize the forwarded traffic to CH i ∈ gh,k O O Let Nf,h,k be the number of cluster heads that forward their data through CH i ∈ gh,k on their route to sink k, as illustrated in Figure 3.4. It follows that the forwarded O is: traffic to CH i ∈ gh,k ˜ O = N O λ, λ f,i,k f,h,k (3.18) Hence, the total arrival rate to CH i is: ˜O λO i,h,k = λg,i + λf,i,k � � O = 1 + Nf,h,k λ, O , h ∈ {1, ..., N }, i ∈ gh,k (3.19) where N is the largest number of hops from a CH to its sink along any routing path. In the following, we model the service rate of the CHs. Let Tslot be the slot duration T in seconds, then the average service rate in packets per second from node i to j is T i,j . slot It follows from Theorem 3.1 that the throughput of a direct one-hop transmission from 91 O g h+1,k g O h,k g,i CH i O Nf,h,k CH CH Sink k CH O O si,h,k i,h,k O . Figure 3.4: Model of CH i ∈ gh,k a CH at the hth hop to a CH at the (h − 1)th hop is: sO i,h,k = 1 k,O Tslot k,O P r{ti ,j = 1}P r{SIN Ri ,i > γ}, h h−1 h h−1 (3.20) k,O O is scheduled to transmit a where P r{ti ,j = 1} is the probability that CH i ∈ gh,k h h−1 k,O O packet to CH j ∈ gh−1,k , and P r{SIN Ri ,j > γ} is the probability of successful h h−1 reception of a packet at hop level h − 1. Following Theorem 3.1, under exponentially distributed SN R, we have: sO i,h,k where SN Rh = = 1 k,O P r{ti ,j h h−1 Tslot −β P¯ Li h−1 ,jh . No � = 1} exp − γ SN Rh � , For equidistant hops, we have SN Rh = SN R, ∀h. 92 (3.21) 3.5.3 Stability Analysis Assuming that the arrival and departure processes are stationary, then for a system to be stable, the service rate must be larger than the arrival rate at each queue [83, 89, O and ∀h, k we must have: 90, 93, 111]. That is, for i ∈ gh,k � � O O O sO > λ ⇒ s > 1 + N i,h,k i,h,k i,h,k f,h,k λ. (3.22) The stability condition would impose a requirement on how often a node is scheduled to transmit. Intuitively, nodes closer to the sink should be scheduled more often than other nodes, due to the larger amount of traffic they relay to the sink. Alternatively, for a particular scheduling, the stability will impose an upper bound on the rate at which traffic is generated λ. Following (3.21) - (3.22), we have the following result O . Similar results can be obtained for nodes in other regions. for any CH i ∈ gh,k Proposition 3.2 (Node stability analysis) For the node buffer to be stable, a CH i ∈ O should be scheduled to transmit to the nearest CH j ∈ g O gh,k h−1,k with a probability � � O Tslot 1 + Nf,h,k λ k,O � � P r{ti ,j = 1} > , h h−1 exp − SNγ R ∀i, k. (3.23) Corollary 3.1 For a particular scheduling protocol, to ensure node stability for any O , the arrival rate of the self-generating traffic of each cluster must satisfy: CH i ∈ gh,k λ < argk,h min k,O P r{ti ,j h h−1 � � exp − SNγ R � �, = 1} O Tslot 1 + Nf,h,k ∀i. (3.24) Remark 3.3 As can be seen, the system stability is guaranteed as long as the transmission probability is above a certain threshold. This condition, in turn, can be fulfilled by providing sufficient channels and/or utilizing signal processing techniques for simul93 taneous transmissions. Note that the stability condition can also be mapped to a lower bound on the transmission power at each CH. However, this is not recommended due to two reasons: (i) The transmission power is generally limited. (ii) Increasing the power would result in increased interference, which could reduce the frequency reuse efficiency. Recall that the probability at which a CH is scheduled to transmits its own traffic N to sink k is lower bounded by P {tki = 1} ≥ N F reqn ∀k, i, where nk is the total intf k number of clusters served by sink k. In other words, there is a scheduled time of length N n intf k equal to or less than N slots, where each CH can send one of its own generated F req packets to sink k. At each hop, a single CH transmits its own traffic as well as the � � O relayed traffic from other CHs. That is, it transmits in a total of 1 + Nf,h,k slots in a single scheduling period. Thus, we have: k,O P r{ti ,j = 1} ≥ h h−1 � � O 1 + Nf,h,k NF req Nintf nk , O . i ∈ gh,k (3.25) When the lower bound on the transmission probability in (3.25) is higher than that in (3.23), then the stability is guaranteed through proper scheduling. We have the following result: Corollary 3.2 In the worst case when the scheduling protocol satisfies (3.25) with equality, then a necessary condition to ensure stability is: � � O 1 + Nf,h,k NF req Nintf nk � � O Tslot 1 + Nf,h,k λ � � > . exp − SNγ R (3.26) It follows that for system stability, the number of clusters within the service area of 94 sink k must be bounded as follows: � � NF req exp − SNγ R nk < , Nintf λTslot ∀k. (3.27) Remark 3.4 Based on NF req , the arrival rate λ, and the average link throughput, the number of RCHs K can be chosen such that (3.27) is satisfied. 3.5.4 Delay Analysis Based on the Klienrock independence assumption, the traffic at each CH can be modeled as an M/M/1 queue whose rates are obtained as illustrated in the previous subsections. O as: We define the utilization factor of CH i ∈ gh,k ρO i,h,k λO i,h,k = O , si,h,k (3.28) O O where λO i,h,k and si,h,k are the arrival rate and the service rate of CH i ∈ gh,k . Hence, the expected number of packets in the queue at CH i is [101]: O Ni,h,k = ρO i,h,k λO i,h,k 1 − ρO i,h,k = O . si,h,k − λO i,h,k (3.29) O is obtained The average delay per packet (in seconds) along the queue at CH i ∈ gh,k using Little’s theorem [101] as: O Di,h,k = O Ni,h,k λO i,h,k 1 = O . si,h,k − λO i,h,k (3.30) The delay in a transmission from a CH to a sink is the sum of the delays encountered ¯ ∈ g O ) be the average at all intermediate hops along the route to the sink. Let D(i h,k 95 O , thus we have delay per packet of node i ∈ gh,k ¯ ∈ gO ) = D(i h,k h � O . Dx,j,k (3.31) j=1 O x∈gj,k Delay analysis for CHs in other regions can be performed similarly. Let NO h,k be the number of nodes at the hth hop from RCH k in the outer region, and NIh,k are those in the inner region. Also, let Nh,0 be the number of nodes at the hth I hop level from the CCH (k = 0). Define, NO k and Nk as the maximum number of hops to RCH k from the outer and inner regions, respectively, while N0 is the maximum number of hops to the CCH from a CH in the region x < Ro . Assuming that all CHs have data to transmit, we get the overall average delay in the cell by summing the delay encountered by a transmission from each CH to the nearest sink, then dividing by the number of CHs in the cell. In summary, we have the following proposition. Proposition 3.3 (Single path case) The average delay of a packet in the network to reach its corresponding stationary sink (CCH/RCH) along a predefined single routing path can be expressed as: ¯ = D 1 NCH   O  Nk NIk �  � O ¯ O )+ ¯ ∈ g I ) Nh,k D(i ∈ gh,k NIh,k D(i K  h,k  h=1 + N0 � h=1  h=1 ¯ ∈ gh,k ) . Nh,0 D(i (3.32) Note that due to the symmetry of the architecture, we get the delay of traffic around a single RCH, multiply by K, then add it to the delay of packets in the CCH region; the result is then divided by the number of CHs in the network to obtain the overall average 96 O , NI O I delay per packet. The calculations of Nf,h,k f,h,k , Nh,k , and Nh,k are provided in Appendix B. Under routing diversity, the result for the single path case can be extended to the multipath case as follows: Proposition 3.4 (Multipath case) Let N be the maximum number of hops from a CH to its sink along any routing path. Consider that for each hop number l ∈ {1, 2, ..., N }, ¯ i,k (N k = l, P k = p) be there are Pi,l possible l-hop paths from CH i to sink k. Let D i i the average delay along one of the l-hop paths from source i to sink k assuming the path Pik = p, then the overall average delay of node i’s packet can be calculated as: P ¯ i,k = D i,l N � � l=1 p=1 ¯ i,k (N k = l, P k = p) Pr{P k = p|N k = l} Pr{N k = l}. (3.33) D i i i i i Let N k be the set of CHs that transmit to sink k, then the overall average per packet delay in the network can be expressed as: ¯= D 3.6 1 NCH K � � ¯ i,k . D (3.34) k=0 i∈N k Simulation Results In this section, we demonstrate the performance of MC-WSN through simulation examples. First, we show the effect of the number of RCHs on the average number of hops in data transmission. Then, we illustrate the per node throughput and the delay performance of the MC-WSN, and compare them to that of SENMA. In the simulations, we use the following parameters: the communication range of the cluster heads is Rc = 30m and that of sensors is rc = 15m, the optimal values for Ro and Rt are set according to Proposition 3.1, the path loss exponent is β = 2, the 97 SINR threshold γ = 5dB, and the bandwidth reuse measure Nintf = 2. Assuming the packet size is 16 bytes and the data rate is 5kbps, then the packet duration will be 25.6ms. The slot duration equals to the packet duration, i.e., we set Tslot = 25.6ms. Note that the same slot duration will be needed if the packet size is 128 bytes, and the data rate 40kbps. 4.5 Average number of hops 4 MC−WSN Single sink, centralized network 3.5 3 2.5 2 1.5 2 3 4 5 6 7 Number of RCHs (K) 8 9 10 Figure 3.5: Average number of hops from a CH to its nearest sink versus the number of RCHs (K), when dc = 200m and Rc = 30m. Example 3.1 - Hop number control Figure 3.5 shows the average number of hops versus the number of RCHs (K) in a stable system. As expected, when K increases, the average number of hops decreases. It is noted that in the case when only the CCH is employed, which corresponds to the traditional centralized networks, 98 2d . Under the same settings used in Figure 3.5, it is the average number of hops is 3R c clear that data transmission in MC-WSN can be performed effectively through smaller number of hops as compared to the traditional centralized network model with a single sink. Example 3.2 - Throughput comparison In this example, we evaluate the overall average per node throughput of MC-WSN and compare it to that of SENMA for different network cell sizes, dc . Define the density of the sensor nodes (SNs) and the cluster heads (CHs) as ρSN = n πd2c and ρCH = NCH , πd2c respectively. Here, we set ρSN = 0.0283, ρCH = 0.0014, and assume SN R = 8dB. In SENMA, the transmission T slot probability of any sensor can be evaluated as: P (tSEN M A = 1) = L M A +nT VM A , slot where VM A is the speed of the MA, LM A is the length of the MA trajectory, and Tslot is the slot duration assigned to each node for transmission. We set VM A = 30m/s, which is relatively high. The length of the MA trajectory in SENMA can be expressed dc �−1 �� 2r dc as: LM A = 2π l=0c (dc − (2l + 1)rc ) + 2rc (� 2r � − 1) [112]. The MA flies at c an altitude HS . Therefore, the per node throughput in SENMA is P (tSEN M A = � � β 1) exp −γHS NP¯o . In Figure 3.6, the overall average per node throughput of MC-WSN with K = 6 and SENMA architecture are plotted versus the network cell radius. For MC-WSN, we consider the cases when NF req = 1 and 4. It is shown that the throughput of MC-WSN is superior to that of SENMA. This is because the transmission of the nodes in the SENMA architecture depends on the speed of the MA and its trajectory length. It can be seen from Figure 3.6 that as the number of orthogonal frequencies increases, the throughput of MC-WSN can be further improved. 99 K=6, SNR=8dB, γ=5dB 0 10 MC−WSN, NFreq=1 MC−WSN, NFreq=4 SENMA −1 Per node throughput (packets/slot) 10 −2 10 −3 10 −4 10 −5 10 100 120 140 160 180 200 220 Cell radius (meters) 240 260 280 300 Figure 3.6: Average per node throughput in packets per slot vs. the cell radius for MC-WSN and SENMA. Here, K = 6, VM A = 30m/s, ρSN = 0.0283, ρCH = 0.0014, ¯ SN R = NP Rc −β = 8dB, Nintf = 2, Rc = 30m, rc = 15m, and Tslot = 25.6ms. o Example 3.3 - Delay comparison In this example, we compare the average delay per packet of MC-WSN and SENMA. We set the cell radius to dc = 200m, the number of cluster heads NCH = 200, the number of RCHs K = 6, and the number of frequencies available for simultaneous transmissions NF req = 1, 4. First, the upper bound on the rate λ the guarantees stability is shown in Figure 3.7. Here, we assume (3.25) holds with equality. As can be seen, higher data generation rates can be supported with higher SNR values. Also, as NF req increases, even higher rates can be tolerated at the same SNR level. Next, we obtain the average delay per packet. Denote the upper bound on λ as 100 0.4 NFreq=1 Upper bound on λ (packets/sec) 0.35 NFreq=4 0.3 0.25 0.2 0.15 0.1 0.05 0 2 4 6 8 10 12 SNR (dB) 14 16 18 20 Figure 3.7: Upper bound on packet generation rate in each cluster (λ) for MC-WSN when dc = 200m, NCH = 200, and K = 6. λU B , and set λ = 0.9λU B . The transmission probability is obtained from (3.25). For MC-WSN, we mainly consider the delay in the transmissions from the source cluster head until its corresponding sink (CCH/RCH). The delay from a sensor to its CH and from the CCH/RCH to the MA are negligible when compared to the queuing and transmission delays of the intermediate multihop transmissions. For SENMA, the delay in packet transmission is mainly dominated by the waiting time until the MA visits the source sensor; a node can be anywhere along the trajectory, hence the average L delay for a node to transmit to the MA is DS = 2VM A . In the delay calculations for MA SENMA, we ignore the transmission time of signals from the sensors to the MA, and the transmission time of the MA beacon signal that notifies the sensors to transmit, 101 as well as the waiting time of the MA at each location for data collection. The delay versus the SNR is shown in Figure 3.8. It is clear that MC-WSN provides orders of magnitude lower delay than that of SENMA, and even lower delays are possible when larger number of orthogonal frequencies, NF req , is available. 80 Average delay per packet (sec) 70 MC−WSN, NFreq=4 60 MC−WSN, NFreq=1 SENMA, considering the MA traversal only 50 40 30 20 10 0 2 4 6 8 10 12 SNR (dB) 14 16 18 20 Figure 3.8: Average delay of MC-WSN and SENMA vs. received SN R. Here, dc = 200m, NCH = 200, K = 6, and VM A = 30m/s. Example 3.4 - Energy efficiency We focus on the energy dissipated in the in- dividual sensor nodes (SNs), since they have the most limited resources. We use the circuitry radio energy dissipation model to evaluate the energy efficiency [113]. Assume that the radius of the cluster be rc , and let Etx and Erx be the energy dissipated in the transmitter and receiver electronics of the SNs, respectively. Then, in MC-WSN, 102 the maximum energy dissipated in a sensor to transmit a bit to its corresponding CH β is ESN,M = Etx + �pa rc (J/bit), where �pa is the energy consumed by the power amplifier, β is the path loss exponent. −6 6 x 10 MC−WSN SENMA 5 Energy (J/bit) 4 3 2 1 0 0 0.5 1 1.5 2 2.5 Number of sensors 3 3.5 × 103 4.5 4 Figure 3.9: The energy dissipation (J/bit) vs. the number of SNs in the MC-WSN and SENMA networks, when dc = 100m, rc = r = 15m, HS = 10m, β = 2, Etx = Erx = 50 nJ/bit, and � = 10 pJ/bit/m2 . In SENMA, each SN must first receive a beacon signal from the MA in order to report its data. Assume the access point traverses the network at a height HS broadcasting beacon signals at random locations. The coverage area of the access point is modeled as a circle of radius r. Therefore, the energy dissipated by a sensor β to report a single bit to the MA is ESN,S = Etx + �pa HS + Erx πr2 An [17], where AT T is the area of the cell. Figure 3.9 shows ESN,M and ESN,S as the number of sensor 103 nodes in the network increases. In this example, we set dc = 100m, rc = r = 15m, HS = 10m, β = 2, Etx = Erx = 50 nJ/bit, and � = 10 pJ/bit/m2 . It can be seen from the figure that MC-WSN is significantly more energy-efficient than SENMA, and the energy efficiency gains increases as the density of the sensors increases. It should be noted that energy dissipation in CHs and MAs are ignored here. However, if their energy dissipation is taken into account, the MC-WSN would still be more efficient than SENMA architecture. This is because, in SENMA the MAs are assumed to traverse the network continuously leading to a very high energy consumption. 3.7 Summary In this chapter, a mobile access coordinated wireless sensor networks (MC-WSN) architecture was proposed for reliable, efficient, and time-sensitive information exchange. MC-WSN exploits the MAs to coordinate the network through deploying, replacing, and recharging nodes, as well as detecting malicious nodes and replacing them. The hierarchical and heterogeneous structure makes the MC-WSN a highly resilient, reliable, and scalable architecture. We provided the optimal topology design for MC-WSN such that the average number of hops from any sensor to the MA is minimized. We analyzed the performance of MC-WSN in terms of throughput, stability, delay, and energy efficiency. It was shown that with active network deployment and hop number control, MC-WSN achieves much higher throughput and considerably lower delay and energy consumption over the conventional SENMA. Moreover, our analysis also indicated that with hop number control, network analysis does become more tractable. 104 Chapter 4 N-Hop Networks – A General Framework for Wireless Systems This chapter aims to provide a unified framework for quantitative characterization of various wireless networks. We first revisit the evolution of centralized, ad-hoc and hybrid networks, and discuss the trade-off between structure-ensured reliability and efficiency, and ad-hoc enabled flexibility. Motivated by the observation that the number of hops for a basic node in the network to reach the base station or the sink has a direct impact on the network capacity, delay, efficiency and their evaluation techniques, we introduce the concept of the N-hop networks. It can serve as a general framework that includes most existing network models as special cases, and can also make the analytical characterization of the network performance more tractable. Moreover, for the network security, it is observed that hierarchical structure enables easier tracking of user accountability and malicious node detection; on the other hand, the multi-layer diversity increases the network reliability under unexpected network failure or malicious attacks, and at the same time provides a flexible platform for privacy protection. Finally, we discuss some possible topics for further research. c �IEEE. Reprinted, with permission, from T. Li, M. Abdelhakim, and J. Ren, “N-hop Networks – A General Framework For Wireless Systems,” IEEE Wireless Communications, accepted [44]. 105 4.1 Preface Communications rely on networks. Today’s wireless networks are generally divided into two categories: centralized networks with well-defined infrastructure, and distributed or ad-hoc networks which are virtually structureless. There is also a trend to blend these two structures together, resulting in various hybrid networks [14, 15]. In this chapter, we try to summarize the general design criteria of wireless networks, and come up with a unified framework that can include most of the existing systems as special cases, and makes quantitative characterization of wireless networks more tractable. To do this, we first examine some representative systems in the literature. 4.2 The Evolution of Wireless Communication Systems The development of mobile telephony traces back to the late 1910s, when a group of German engineers started the experiments on telephony via radio links, and tested on the military trains between Berlin-Zossen in 1918 [114]. The first handheld radio transceivers, also called walkie-talkies, were the backpacked Motorola SCR-300 [115], developed in 1940; later refined and widely used during the World War II (1939). Right after the war, engineers in Bell Labs invented a system to allow mobile users to place and receive telephone calls from automobiles, leading to the inauguration of mobile services in 1946 in St. Louis, Missouri. After that, a wide range of incompatible mobile services, supported by analog techniques, were provided in urban areas, each offering very limited coverage through a base station that has only a few channels. 106 4.2.1 Cellular Systems The concept of cellular technology, which exploited low-power transmitters and allowed wide range frequency reuse, was introduced and developed by Bell Labs engineers from the late 1940s to early 1970s [116]. While the first hexagonal cell concept was proposed in 1947 [117], the full development and implementation of the cellular technology, including both frequency reuse and call handover, took more than two decades. The cellular technology made the mobile services affordable to ordinary people, and led to the revolutional widespread of wireless communications. The first generation (1G) cellular systems (1970s), represented by AMPS (Advanced Mobile Phone System) in the US (later on evolved to IS-41) and ETACS (European Total Access Communication System) in Europe, relied on analog technologies and mainly provided voice services. Started in late 1980s and deployed in 1990s, the second generation (2G) cellular systems (United States Digital Cellular (USDC) IS-136, CDMA IS-95, and GSM) all used digital coding and modulation techniques. The 2G systems increased the network capacity by about three times. As they were designed before the wide spread of the internet, they mainly supported voice-centric services and limited data-services, like short messages and Fax. Began in late 1990s, the 3G systems (UMTS WCDMA, CDMA 2000, and TDSCDMA) supported high-speed multimedia services and seamless global roaming. Wireless access became available throughout the earth, with the proud claim of “anywhere, anytime, anything”. The communication quality was further enhanced by the OFDM technique, leading to the high speed, high quality 4G systems, represented by WiMAX (Worldwide Interoperability for Microwave Access) [118] and LTE (Long Term Evolution) [119]. Today, with the coexistence of 3G and 4G, we can have real-time multimedia communications through world-wide networks. 107 4.2.2 Ad-hoc Networks The walkie-talkies, which are still widely used today in military, public safety, businesses, outdoor recreation and the like, actually form a complete mesh network, where any two users, within the device power range, can communicate directly in a structureless manner. Going beyond this one-hop communication mode and allowing multihop routing process, the self-configuring infrastructureless wireless ad-hoc network has attracted lots of attention from the research community. The research on ad-hoc networks was mainly driven by the growth of laptops and 802.11/Wi-Fi wireless networking, and the advent of all kinds of wireless sensors, leading to the areas of MANET (Mobile Ad-hoc Network) [120] and WSN (Wireless Sensor Network) [121], respectively. MANET has been widely deployed as local area networks in businesses, universities, airports and places alike, for convenient wireless internet access and internet-assisted communications. At the same time, wireless sensor networks have seen wide use in both military and civilian applications, such as health monitoring [122], intelligent transportation systems [3], target detection and tracking especially in unattended and possibly hostile areas. 4.2.3 The Merging Ground for Cellular and Ad-hoc – Hybrid Networks While the structureless ad-hoc networks provide excellent flexibility with reliable performance for small scale networks, scalability proved to be a serious challenge for large-scale ad-hoc networks due to the uncertainty, complexity, as well as the delay and energy concerns in the routing process. The problems become even worse when the devices are mobile. 108 This observation leads to ad-hoc networks with local structures, known as hybrid networks. One representative example is the clustered wireless sensor networks, where the sensors are grouped into clusters, with each cluster managed by a cluster head in a centralized manner [16]. The routing responsibility is fulfilled only by the cluster heads, and not ordinary sensor nodes. Similar ideas are developed for the mobile adhoc network (MANET) [120], include multi-hop cellular network (MCN), integrated cellular and ad-hoc relaying systems (iCAR) [87], self organizing product radio networks (SOPRANO) [123], etc. At the same time, hybrid networks also raised from the cellular networks. This is mainly motivated by the following two observations: (i) For todays centralized network, the mobile will generally lose network connection once the BS is not functioning, since each mobile is typically connected to only one BS. (ii) Even if two mobiles are spatially close, they cannot establish direct communication, but have to communicate through the BS, leading to unnecessary resource waste. That is, traditional centralized network does not have sufficient diversity and endpoint communication flexibility. As a result, recent wireless MAN and LAN standards, such as WiMAX 802.16 [118] and WiFi 802.11s [124], have incorporated the mesh capability to the wireless network nodes, which allows each node to forward the traffic of other nodes in the network in a planned yet an ad-hoc manner. Other representative examples include Ad-hoc GSM (A-GSM) [125], cellular networks with device-to-device (D2D) communications [126–129], and iCAR [87], where the main idea is to improve transmission flexibility, viability, capacity, and traffic balance by allowing device-to-device and/or device-to-relay station communications. From our discussions above, it can be seen that hybrid networks serve as a merging ground for centralized and ad-hoc networks, as shown in Figure 4.1, and stimulate the research on different kinds of heterogeneous networks (Hetnets). On the mobile 109 side [126, 130, 131], one visible trend is the real-time video communications that drives for the trade of memory for capacity. The Femtocells in LTE-advanced [130], for example, can be used to store popular videos so that they do not need to be requested through the BS. On the sensor side, an interesting move is sensor networks with robotlike mobile access points [17, 78]. Hybrid networks Higher flexibility and efficiency Higher reliability and efficiency Ad-hoc networks Centralized networks Figure 4.1: Merging of centralized and ad-hoc networks. 4.3 General Design Criteria The evolution of the centralized and ad-hoc networks to hybrid networks reveals that: for wireless communications, we would need both network centric management as well as ad-hoc flexibility. Based on this observation, we can summarize the general network design criteria as follows: The network needs to have a well-organized infrastructure to ensure the reliability (including both transmission accuracy and security), capacity, energy efficiency as well as time efficiency. At the same time, the network should provide sufficient flexibility by allowing authorized ad-hoc communications among the nodes or devices. More specifically, 110 • The infrastructure needs to be hierarchical for efficient management. The density of the devices gets higher as their level gets lower. • The infrastructure needs to provide sufficient diversity at each level to combat hostile attacks or unexpected system failures. More specifically, devices or basic nodes (BNs) at each level can communicate with two or more upper level devices. • The infrastructure needs to provide sufficient flexibility. – Once authenticated, neighboring devices (either relay stations or basic nodes) at the same level can communicate directly with each other within their transmission range without going through higher layer nodes. – When permitted, each device can communicate directly with higher layer nodes within its communication range to minimize the number of hops needed to reach a base station (BS) or sink. – Under special cases when a BN cannot access the network directly, as long as an agreement is reached between two BNs (both BN should be authenticated if possible), one BN can serve as the relay for another BN. From a biomimetic perspective, these criteria can be largely verified in the design of the human body. Consider the circulatory system, in which the extracellular fluid is transported through parts of the body in two stages [132]. The first stage is the movement of the blood in the blood vessels; the second stage is the movement of fluid between the blood capillaries and the intercellular space between the tissue cells. The latter stage is also called micro-circulation, it is for the transport of nutrition to the tissues and removal of cell excreta. The first stage is centralized and well structured with good diversity. Even if some vessels are not functioning well (e.g. blocked), as long as they are within a certain threshold, the human body will continue to function. 111 In the second stage, the micro-circulation, the exchange of water, nutrients and other substance between the plasma in blood and interstitial fluid in the tissue is mainly done through diffusion, which results from thermal motion of the water molecule and dissolved substances in the fluid. To make it short, it is random! As can be seen, the circulatory system in human body is an excellent combination of a well-structured “backbone” network and numerous small random networks at the endpoints. It ensures transmission efficiency, diversity and endpoint service flexibility, and thus provides a very good example for network design. 4.4 The Concept of N-hop Networks With the general design criteria in mind, we now try to come up with a unified framework for wireless networks that could cover most of the existing systems as special cases, and makes quantitative network characterizations (such as throughput, delay, and efficiency) more tractable. We first look at some examples. In strictly centralized networks, which is widely adopted in cellular communication systems, the mobile reaches the base station (BS) in one hop. In the one layer relay-assisted networks, the basic node either reaches the BS directly in one hop, or reaches the base station through the relay in two hops [133]. In the pure ad-hoc networks or sensor networks, there is generally no specific limit on the number of hops for a basic node to reach a sink. For any wireless network, let the minimum number of hops for a basic node (i.e., the terminal, such as a mobile or a sensor) i to reach the base station (BS) or the sink be Ni . Define N = max{N1 , N2 , ...Nn }, where n is the number of basic nodes. N is an important characterization of how closely the basic nodes are connected to the BS or the sink, and it has a direct impact on network capacity, reliability, delay, 112 efficiency, as well as their evaluation techniques. Here we introduce the concept of N -hop networks: a wireless network is said to be an N -hop network if every basic node (BN) can reach the BS or the sink within N hops under normal network conditions. By normal conditions, we mean that there are no hostile attacks, or severe, unexpected system failures. Based on this definition, if N = 1, we obtain the strictly centralized network. For some sensor networks with mobile access points, we also have N = 1, see the SENMA in [17] for example. In SENMA, with well designed mobile access trajectory, there is no routing and all the sensors can reach the mobile access in one hop. If N = 2, we get the relay-assisted network; if N = ∞, it reduces to the pure ad-hoc network. Actually, almost all the existing systems fall into this unified framework. As will be seen later, with this framework, analytical evaluation of the throughput, delay, and efficiency becomes more tractable. Denote the total number of hops for a node i to reach its destination, node j, as c , where N c is the number of Ni,j . For an N -hop network, we have 1 ≤ Ni,j ≤ 2N +Ni,j i,j hops required for the intercell communications between the two base stations connected to nodes i and j, respectively. For the complete (local) mesh network where any two nodes can communicate directly, we always have Ni,j = 1 for any source-destination pair (i,j). Due to possible link failure conditions and/or malicious attacks, the number of hops for a node to reach the sink could be more than N . For this reason, we extend the definition of N-hop networks to α-level N-hop networks, which is characterized by: P r{BN can reach the sink within N-hops} = α. The level α can be used as an indicator of how smooth the network is operating. Next, we provide two examples to further illustrate the N − hop network: one on mobile network, and one on sensor network. 113 BS1 BS2 RS L1 BN1 RS L2 RS L2 RS L1 RS L2 RS L2 BN4 RS L2 BN3 RS L1 BN2 RS L2 RS L2 BS3 BS4 RS L1 RS L1 Level 1 RS RS L2 Level 2 RS BN Figure 4.2: A 3-hop mobile network. Example 4.1 - A 3-hop mobile network In this network, multiple base stations (BSs) and two levels of relay stations (RSs) (level 1 and level 2) are employed to serve the basic nodes (BNs) - the mobiles, as illustrated in Figure 4.2. Level 1 RSs have larger coverage area and storage capacity than level 2 RSs, but level 2 RSs have much higher distribution density in the network. Devices or nodes at each level can communicate with two or more upper level devices. Within their transmission range, neighboring devices (either RSs or BNs) at the same level can communicate directly with each other without going through higher layer nodes. At the same time, each device can communicate directly with the highest level higher layer nodes within its 114 communication range to minimize the number of hops needed to reach a BS. This is a 3-hop network. The tolerance of the network to system failures or hostile attacks is determined by its inherent diversity. Example 4.2 - Mobile Access Coordinated - Wireless Sensor Network (MCWSN) In the proposed MC-WSN architecture described in Chapter 3, data trans- mission from sensor nodes to the mobile access point (MA) goes through simple routing with the center cluster head (CCH) or the ring cluster heads (RCHs). MC-WSN is an example of hybrid network: it has a hierarchical structure supported by the CCH, RCHs, and CHs; at the same time, it also allows partially ad-hoc routing for network flexibility and diversity. Through active network deployment and topology design, the number of hops from any sensor to the MA can be limited to a pre-specified number N [43]. The MC-WSN architecture is illustrated in Figure 3.1. The examples above illustrate that the N-hop network does provide a general framework for the characterization of centralized, ad-hoc, as well as hybrid networks. 4.5 Analytical Evaluation of the Network Performance In this section, we provide a quantitative characterization of wireless networks under the N-hop framework, in terms of throughput, delay, and energy efficiency. 4.5.1 Throughput Consider an N-hop network that contains n basic nodes. For each individual BN i, the throughput, Ti , is defined as the average number of packets per slot that are 115 initiated by node i and successfully delivered to the intended receiver [91]. For an N-hop network, when the receiver is the BS or the sink, the number of hops from BN i to the BS satisfies 1 ≤ Ni ≤ N . Note that the transmission can always go through different paths due to the existence of network diversity. We assume that for each hop number l ∈ {1, 2, ..., N }, there are Pi,l possible l-hop paths from BN i to the BS. Let T (i|Ni = l, Pi = p) be the throughput that can be achieved along one of the l-hop paths Pi = p, then the throughput of node i can be calculated as: P Ti = i,l N � � l=1 p=1 T (i|Ni = l, Pi = p) Pr{Pi = p|Ni = l} × Pr{Ni = l}. The overall network throughput can be obtained as (4.1) �n i=1 Ti . It should be noted that the throughput of node i along Pi = p, T (i|Ni = l, Pi = p), mainly depends on the probability of successful transmission at each hop, which is generally characterized by the probability that the signal to noise and interference ratio (SIN R) is above a certain threshold γ [134]. More specifically, referring to Theorems 3.1 and 3.2 in Chapter 3 and setting K = 1, the throughput from node i to the sink given a certain routing path can be expressed as:    l � � � β No T (i|Ni = l, Pi = p) = P r{ti = 1} exp −γ ¯ Lih ,ih−1 ,   P (4.2) h=1 where P r{ti = 1} is the probability that node i transmits a packet to the sink, Lih ,ih−1 is the distance between the transmitting and receiving nodes at the hth hop along the routing path from source i to the sink, P¯ is the average transmission power, and No is the noise power. Assume a relatively flat noise power along the transmission path, when the trans116 mission power of the nodes is low, the throughput improves as the number of hops increases. This is due to the reduced path loss at each hop as compared to longer distance transmission. On the other hand, when the transmission power is large, the throughput improves as the number of hops decreases, because of reduced propagation errors. This is illustrated in Figures 4.3, where the per-node throughput versus the transmit signal to noise power ratio is shown. In Figures 4.3(a) and 4.3(b), the bandwidth reuse measure along the path (Nintf ) equals to Ni and 3, respectively, and P r{ti = 1} = min{N 1 ,N } . intf i From the discussions above, we can see that under a particular power constraint, there exists an optimal number of hops for throughput maximization. Consider a single source-destination pair. Let Nintf = Ni , i.e., there is no bandwidth reuse along the path from the source to the destination, then P r{ti = 1} = N1 . Assume equidistant i Lt hops of length N , where Lt is the distance between the source and the intended i destination. The optimal number of hops, Nopt , that maximizes the throughput is obtained by setting � ∂T (i|Ni ,Pi ) ∂Ni = 0. It follows from (4.2) that � � � �β � 1 (β − 1)γ N Lt o β − + (Ni )−1−β ¯ Lt exp −γ ¯ Ni = 0. 2 Ni P /No P (Ni ) Therefore, we get: � � 1 (β − 1)γ β β−1 Nopt = L . P¯ /No t (4.3) (4.4) Nopt versus the transmit signal to noise power radio (P¯ /No ) is shown in Figure 4.4. This result indicates that the optimal hop number versus the transmission power provides a critical reference for network structure design. Next, we will discuss the impact of the network structure and routing flexibility on the throughput performance. 117 1 0.9 Throughput (packets/slot) 0.8 1 hop 2 hops 3 hops 4 hops 5 hops 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 −15 −10 −5 0 5 10 Transmit signal power to noise power ratio (dB) 15 (a) Bandwidth reuse measure Nintf = Ni . 1 0.9 Throughput (packets/slot) 0.8 1 hop 2 hops 3 hops 4 hops 5 hops 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 −15 −10 −5 0 5 10 Transmit signal power to noise power ratio (dB) 15 (b) Bandwidth reuse measure Nintf = 3. Figure 4.3: Per-node throughput T (i|Ni , Pi ) vs. the average transmit power per noise power ratio for different number of hops, assuming AWGN channel, path loss exponent is 4, SINR threshold is γ = 5dB, the hops are equidistant, distance between transmitter and receiver is normalized to 1m. The transmit power is exponentially distributed. 118 7 6 Optimal number of hops 5 4 3 2 1 0 −15 −10 −5 0 5 10 Transmit signal power to noise power ratio (dB) 15 Figure 4.4: Optimal number of hops obtained by rounding (4.4) to the nearest integer. Here, γ = 5dB. Example 4.3 Structured versus structureless network models In an N-hop structured network, under normal network conditions we always have Ni ≤ N . On the other hand, for structureless networks, due to the absence of the infrastructure support, generally it is hard to put a limit on the maximum number of hops needed in the data delivery process. Assume that the per-hop distance is fixed, it follows from (4.2) and also from Remark 3.1 in Chapter 3, that limNi →∞ Ti = 0. It can hence be seen that comparing with structureless network, the N-hop network secures the throughput for each node by limiting the number of hops in the data delivery process. 119 Example 4.4 Routing flexibility Now, let us look at the impact of the routing flexibility on the throughput. Although structured network is highly desired as mentioned earlier, it is important to have routing flexibility around the endpoints (BNs) to enhance the overall network efficiency. That is, neighboring BNs can communicate directly or use simple routing through the lowest level relay stations without going to the higher layer stations. This is possible with the advances in radio technology that enable today’s wireless devices to have cognitive abilities, which help them learn about the environment, detect their neighbors, and determine the available spectrum bands to utilize [46]. Thus, BS intervention in coordinating the communications between endpoints could be reduced. BN l BS k Lk,q Lr,k RS r BN m BS q Li,k Lq,m Lr,l Lk,j Li,r Li,j BN j BN i Figure 4.5: Routing flexibility: Scenario 1: BN i and BN j communicate directly. Scenario 2: BN i and BN l communicate through RS r. Scenario 3: BN i and BN m communicate through RS r and the BSs k and q. 120 Consider an example when BN i wants to communicate with BNs j, l and m. BN m is out of the footprint (or the cell) covered by BS k that serves BNs i, j, and l, as illustrated in Figure 4.5. We consider the following three scenarios: (i) Communication between BN i and BN j. With the proposed network model, direct communication can be established between BN i and BN j. In this case, the β throughput is Ti1 ∝ exp{−Li,j }. However, in strictly centralized networks including the current cellular systems, where routing flexibility is not employed, BN i has to reach the BS first to communicate with BN j. In this case, the throughput will become β β Ti2 ∝ exp{−(Li,k + Lk,j )}. Clearly, since Li,j < Li,k + Lk,j , then Ti1 > Ti2 . (ii) Communication between BN i and BN l. In our proposed model, the communication can be made through RS r (BN i ⇔ RS r ⇔ BN l). In this case, the throughput β β will be Ti1 ∝ exp{−(Li,r + Lr,l )}. If the transmission is made through the BS, then we need BN i ⇔ BS k ⇔ BN l or BN i ⇔ RS r ⇔ BS k ⇔ BN l. Considering the case when the transmission is made through BN i ⇔ BS k ⇔ BN l, then the throughput β β will be Ti2 ∝ exp{−(Li,k + Lk,l )}. When the same transmit power is used in both cases, we have Ti1 > Ti2 . (iii) Communication between BN i and BN m. Since BN m is not in the same cell as BN i, the communication is made through the BSs, i.e., BN i ⇔ BS k ⇔ BS q ⇔ β β β BN l. In this case, Ti ∝ exp{−(Li,k + Lk,q + Lq,m )}. In this example, BSs are only involved in communications to nodes out of its footprint. Considering the possibility of using low-power transmissions over unlicensed band in scenarios (i) and (ii), the overall network capacity can potentially be increased by allowing endpoint routing flexibility. 121 4.5.2 Delay The quantification of the delay in N-hop networks involves both information theory and queuing theory. The former studies the maximum rate at which each node can transmit over the channel, by considering noise and interference effects, but ignoring the queuing delay that could be experienced at intermediate relays/queues. The latter considers the queuing delay with possible random arrival and departure times at the intermediate relays. The delay in one-hop communication is mainly composed of three parts: (i) The queuing delay is the time between the packet arrives at a node, until it reaches the head of the queue where it can be transmitted. Little’s theorem [101] Q formulates the average queuing delay as Dq = λL , where QL is the average number of q packets in the queue, and λq is the rate at which the packets arrive to the queue. Nodes with finite storage can be modeled as M/M/1/B queues, where the arrivals are memoryless Poisson process with rate λq , the service times are exponentially distributed with rate ϑ, and the storage of each queue is B packets. Let PB be the probability that the queue is full. Note that each node receives a packet only when it is not full, hence the effective arrival rate is λe = λq (1 − PB ). With the effective arrival rate and the mean queue length, the queuing delay can then be obtained using the Little’s theorem [101]. (ii) The back-off delay occurs when a packet is not successfully received due to either full receiver buffer or collisions in the transmission; in this case, the transmitter will retransmit the packet after a back-off time. Collision happens when two or more interfering nodes access the channel at the same time. In structured networks, back-off time can be minimized due to the presence of a centralized control on data transmission, which allows interfering nodes to transmit on a different time slots or different frequency bands. The back-off time can be assumed to be exponentially distributed [135]. The 122 node stays in the back-off state until the channel is idle and the receiver buffer is no longer full. (iii) The transmission delay is the difference between the time data is encoded and transmitted until it is successfully recovered/decoded at the receiver [136]. It depends on the size of the packet and the transmission rate, which is bounded by the information-theoretic capacity. ¯ can be calIn an N-hop wireless network, the average delay of a transmission, D, culated as: ¯= D Pi,l l N � � � ¯ p,m Pr{Pi = p|Ni = l} Pr{Ni = l}, D (4.5) l=1 p=1 m=1 ¯ p,m is the average where Ni denotes the actual number of hops for a transmission, and D delay in the mth hop along the path p. 4.5.3 Energy Efficiency As in Chapter 3, we use the circuitry radio energy dissipation model [113] to evaluate the energy efficiency. In this model, each receiving node consumes Erx (J/bit), and each transmitting node consumes Etx +�pa Lβ (J/bit), where �pa is the energy consumed by the power amplifier, β is the path loss exponent, L is the per-hop distance, and Etx is the energy dissipated in the transmitter electronics. Then the total energy dissipated at a one-hop communication is Etx + �pa Lβ + Erx (J/bit). In an N-hop network, the average energy consumption for a packet transmission, ¯ can be calculated as: E, E¯ = Pi,l l N � � � E¯p,m Pr{Pi = p|Ni = l} Pr{Ni = l}, l=1 p=1 m=1 where E¯p,m is the average energy consumed at the mth hop of path p. 123 (4.6) Example 4.5 - Energy efficiency versus the number of hops In this exam- ple, we compare the average energy dissipation for two network models: (i) SENMA architecture, which is a one-hop centralized network with mobile access, (ii) MC-WSN architecture, which is described in Chapter 3, with K = 3 RCHs and shortest path routing. For energy comparison, in Chapter 3 we mainly focused on the energy dissipated at a sensor node to transmit to its cluster head. Here, we focus on the energy dissipated in the multihop transmissions from a cluster to a sink in MC-WSN. The result is shown in Figure 4.6. It is clear that the N-hop MC-WSN is much more efficient than SENMA networks. The reason is that in SENMA, each SN must first receive a beacon signal from the MA in order to report its data. All sensors within the coverage area of the MA receive the beacon signal, and only one sensor responds each time [17]. The energy dissipation during the beacon reception process contributes significantly to the overall energy consumption for each transmission in SENMA. Remark 4.1 For the α-level N-hop network, the number of hops can be greater than N with probability (1 − α). In this case, we can extend (4.1), (4.5), (4.6) accordingly, by changing N to Nmax , which is the maximum number of hops in a cell. Equations (4.1), (4.5), (4.6) can also be extended directly to the node-to-node communication case. 4.6 4.6.1 Security Perspectives Delay-assisted Network Failure/Attack Detection Consider a particular node i, under normal network conditions, Ni is the number of hops from BN i to the sink, then the delay of node i’s transmission to the sink is �Ni Di = k=1 dk , where dk is the delay in hop k. Note that the average delay is given ¯ i , then this in (4.5). If the actual delay Di is much larger than the average delay D 124 −6 1.2 x 10 Energy dissipated (J/bit) 1 0.8 0.6 0.4 0.2 MC−WSN SENMA 0 1 2 3 4 5 Number of hops in MC−WSN 6 7 Figure 4.6: The energy dissipation (J/bit) vs. the number hops in N-hop MC-WSN, and comparison with the single hop SENMA network. Here, we set the cell radius dc = 100m; for the MC-WSN, the per-hop distance for CHs is 30m; for SENMA, the per-hop distance and the MA coverage radius are equal to 10m; the path loss exponent β = 2, n = 2000, Etx = Erx = 50 nJ/bit, and �pa = 10 pJ/bit/m2 . indicates that either additional hops are utilized at the data delivery, or there is an unexpected large back-off time. In other words, the ratio between the actual delay and the average delay of a transmission can be used as an indicator for the detection of unexpected network failures or hostile attacks. When the network synchronization is achieved, the detection of network failure problems can be implemented by including a time stamp in each packet representing the transmission time of the data. To compute the delay, the sink then compares the time stamp with the actual time of reception. If the delay is greater than a certain 125 threshold, then an exceptional behavior is detected. ˜ i (t). The detection Let the actual delay of BN i’s transmission at time t be D problem can be modeled using the binary hypothesis test. Let H0 be the null hypothesis ˜ i (t) ≤ D ¯ i + δ), and H1 be the alternative that represents normal network conditions (D ˜ i (t) > D ¯ i + δ). That is, hypothesis that represents exceptional network behavior (D H0 : ˜ i (t) ≤ D ¯ i + δ, D (4.7) H1 : ˜ i (t) > D ¯ i + δ, D (4.8) where δ is a pre-defined parameter that reflects the time fluctuation in the system caused by queuing delay, and possible retransmissions due to the channel environment. Let Zi (t) be a binary indicator, such that it is equal to ‘1’ if Ho is true at time t, and equal to ‘0’ when H1 is true. That is, Zi (t) = Define α(t) = �n i=1 Zi (t)/n.   1 Ho is true for node i at time t,  0 H1 is true for node i at time t. (4.9) α(t) can serve as an indicator on how well the network is functioning at time t. Ideally, the network should provide sufficient diversity to ensure that α(t) is close to unity at any time instant t. When an exceptional network condition is detected, more measurements can be scheduled or requested for the network to locate the specific communication failure. 126 4.6.2 Access Authentication: Accountability and Privacy Protection For N-hop networks, authentication can be implemented through a centralized authentication center (AuC) in the device-level. The hybrid network structure and routing diversity also enables the N-hop network to support network-level authentication. For the device-level authentication, the authentication service is initiated by the fixed network and can be implemented through a simple challenge-response based authentication protocol. The authentication requires a shared secret key between each device and the centralized authentication center (AuC). When a wireless device A needs to initiate a communication with another wireless device B, A makes an initial access request to B. The access request should contain the device identity ID, the BS that A accesses and can be authenticated through the AuC. After receiving the access request, B works as a proxy and forwards A’s access request to the fixed BS and the AuC for A to be authenticated. The AuC then issues a random access Challenge and send it to A through the BS and B. Upon receiving the Challenge, A computes the response Response = Ek (Response) based on the A Challenge and the secret key kA shared between A and the AuC. The computed response will be send back to the AuC through B and the BS for authentication. If the authentication is successful, the communication between A and B can be established. Otherwise, the access request from A will be rejected by B. This process only provides authentication of A to B. If two way authentication is required, B can be authenticated to A following the same procedures. For the network-level authentication, the authentication can be split into two phases: the end-user device authentication to network access point (NAP) (such as BS, CH etc.) and the authentication between the NAPs through a mutually trusted 127 network server in the hierarchical structure such as the AuC. The end-user device authentication to the NAP can either be performed by the NAP locally or through the AuC. In both scenarios, the NAP can be viewed as a proxy for the end-user device and can provide end-user privacy protection to hide the communication events between the source and the destination. In addition to authentication and accountability services, compared with traditional centralized network, the routing diversity in hybrid networks make the transmissions more robust under unexpected network failure or hostile attacks. At the same time, the routing diversity can also be exploited to achieve better privacy protection. 4.7 Summary In this chapter, we first revisited the evolution of wireless systems and discussed the general design criteria of wireless networks. It was observed that in order to achieve a good balance among capacity, reliability, delay and flexibility, a network should be sufficiently structured and at the same time should provide adequate ad-hoc flexibility. On the evolution of wireless networks, this is reflected as the merging of centralized and ad-hoc networks, leading to the development of hybrid networks. In an effort to provide a unified framework for existing wireless systems, especially hybrid networks, we introduced the concept of N-hop networks. Under the N-hop framework, we discussed the analytical characterization of network performance in terms of throughput, delay, and energy efficiency, and also looked into the security perspectives on the balance between user accountability and privacy protection. It was shown that the N-hop framework includes most of the existing systems as special cases, and provides a flexible and tractable platform for network design, management, and performance evaluation. We also provided some related topics that may lead to further research. 128 Chapter 5 Conclusions and Future Work 5.1 Conclusions This dissertation considered improving the reliability and efficiency of time-critical communications in wireless sensor networks, under both benign and hostile environments. The main conclusions are summarized in the following. First, in Chapter 2, we considered the q-out-of-m fusion rule for reliable distributed detection in sensor networks with mobile access points (SENMA) under Byzantine attacks. Both static and dynamic attack strategies were discussed, where malicious sensors attack with fixed and time-varying probability, respectively. By exploiting the linear relationship between the network size and the scheme parameters, simple and effective q-out-of-m linear approaches were developed. We also derived a near-optimal closed-form solution for the fusion threshold based on the central limit theorem. Furthermore, we obtained an upper bound on the percentage of malicious nodes that can be tolerated using the q-out-of-m rule. It was found that the upper bound is determined by the sensors’ detection capability and the attack probability of the malicious nodes. We proved that the false alarm rate diminishes exponentially with the network size, even if the percentage of malicious sensors remains fixed. This implies that for a fixed percentage of malicious nodes, we can improve the network performance significantly by increasing the density of the nodes. To further improve the reliability of the data 129 fusion process, we proposed an effective malicious node detection scheme for adaptive data fusion under time-varying attacks, where the malicious sensors are identified and discarded then the fusion parameters are updated accordingly. We analyzed the detection procedure using the entropy-based trust model, and showed that it is optimal from the information theory point of view. It was observed that nodes launching dynamic attacks take longer time and more complex procedures to be detected as compared to those conducting static attacks. The adaptive fusion procedure has shown to provide a significant improvement in the system performance under both static and dynamic attacks. Next, in Chapter 3, we proposed a mobile access coordinated wireless sensor networks (MC-WSN) architecture for reliable, efficient, and time-sensitive information exchange. The proposed MC-WSN exploits the mobile access points (MAs) to coordinate the network through deploying, replacing, and recharging nodes, as well as detecting malicious nodes and replacing them. Not only does MC-WSN resolve the network deployment problem, but it also prolongs the network lifetime actively and provides an efficient framework for time-sensitive information exchange. The hierarchical and heterogeneous structure makes MC-WSN a highly resilient, reliable, and scalable architecture. We provided the optimal topology design for MC-WSN such that the average number of hops from any sensor to the MA is minimized, and analyzed the performance of MC-WSN in terms of throughput, stability, delay, and energy efficiency. It was shown that with active network deployment and hop number control, MC-WSN achieves much higher throughput and considerably lower delay and energy consumption over the conventional SENMA. Finally, in Chapter 4, we introduced the concept of the N-hop networks. Based on the N-hop concept, we proposed a unified framework for wireless networks and discussed general network design criteria for reliable and efficient communications. It was 130 shown that the N-hop framework includes existing network models as special cases, and provides a flexible and tractable platform for network design, management, and performance evaluation. Quantitative characterization of N-hop wireless networks was provided, along with discussions on different security perspectives. It was observed that in order to achieve a good balance between efficiency and reliability, a network should be sufficiently structured and at the same time should provide adequate ad-hoc flexibility. More specifically, the wireless network should have: (i) hierarchical structure, for efficient management, tracking of user accountability, as well as malicious node detection; (ii) multi-layer diversity, for higher reliability under unexpected network failure or malicious attacks; (iii) endpoint routing flexibility, for efficient utilization of the available resources. 5.2 Discussions for Future Work We propose the following directions for future research. Adaptive data fusion with soft decisions under malicious attacks with varying sensors’ detection capabilities • In Chapter 2; interesting results had been drawn on the effect of the network size on the reliability of the distributed detection under Byzantine attacks. For this purpose, hard decision model was mainly considered, where sensors quantize each observation into a single bit. Further research can be conducted to model the worst case Byzantine attacks when soft decisions are used, and on developing reliable distributed detection approaches in this case. • It is also interesting to study the effect of possible varying detection capabilities of sensors on the reliability of the data fusion, and the effect of dividing the 131 cell into smaller regions over which the fusion rule can be applied with highest accuracy. Security enhancements for MC-WSN under malicious attacks • In Chapter 3, an MC-WSN architecture was proposed for reliable and timesensitive information exchange. Detecting malicious sensors under general attack models in the multihop MC-WSN needs further investigations. More specifically, further research is needed to develop secure schemes in MC-WSN to combat different security threats, including various routing attacks and jamming. Trade-off between security and efficiency • Security is generally achieved at the cost of reduced efficiency. For example, to combat Byzantine attacks we need to employ large number of sensors for distributed detection; this would result in increasing the delay in the final decision making process. Also, to improve the privacy protection in multihop networks, routing diversity should be employed, which requires more resources to route the information to the intended destination. It is important to quantify the trade-off between the network efficiency versus its security strength, and explore secure schemes that can achieve a good compromise between them. Further analysis for the N-hop networks • Time-sensitive applications would impose delay constraints on data transmissions. Therefore, further analysis for the N-hop networks under delay constraints is important. Particularly, characterizing the multihop network-level capacity under both delay and power constraints remains an overwhelming research problem that needs further investigations. 132 APPENDICES 133 Appendix A Transmission Probability – Proof of Lemma 3.1 In this appendix, we obtain the uniform transmission probability of CHs within the coverage area of sink k ∈ [0, 1, ..., K] in MC-WSN. We show that when hybrid TDMA/FDMA N is used, the transmission probability P (tki = 1) ≥ N F reqn , ∀i ∈ N k , where nk is the intf k k number CHs transmitting to sink k, N is the set of CHs within the coverage area of sink k, Nintf is the bandwidth reuse measure, and NF req is the number of frequencies available for simultaneous CHs transmissions within the same interference region. The length of the TDMA schedule is the number of slots needed for the sink to receive one packet from all CHs within its coverage area. Since CHs within one hop from the sink relay the traffic of all other CHs within the sink’s coverage area, then the largest length of a scheduling period can be obtained by finding the number of slots these CHs need to forward all the traffic they have (one packet from each source) to the sink. Here, we assume that each node has a packet to transmit and all packets are of the same importance, i.e. periodic data collection is considered. Note that in event driven scenarios, the length of the TDMA schedule could be less than that in the periodic data collection case. First, consider NF req = 1. Then, a CH close to the sink can transmit only if other CHs within the interference region are silent. Hence, the length of the transmission schedule to sink k is: Nintf Sk ≤ � Nh,k (Nf,h,k + 1), (A-1) h=1 where Nh,k is the number of CHs at hop level h from sink k, and (Nf,h,k + 1) is the total number of packets a node at hop level h sends to sink k. Note that the inequality 134 is mainly due to considering the largest number of interfering neighbors, which is when a CH arbitrary close to the sink location is considered [24]. Recall that NCH is the total number of CHs in the cell. Let AT be the total area A of the cell, and Ak be the coverage area of sink k; then, nk = A k NCH . Let Ah,k be T 1 the area served by sink k until hop level h only. Hence, we have : � � Ah,k − Ah−1,k Nh,k � nk , Ak Nf,h,k � Ak − Ah,k nk . Ak Nh,k (A-2) When Nintf = 2, it follows from (A-1) that [24]: Sk ≤ � �  �  A1,k  Ak − A1,k � nk� nk  Ak Ak  A1,k Ak   nk   + 1  �  A2,k − A1,k nk  Ak − A2,k � � nk  Ak Ak  A2,k −A1,k � A1,k ≤ nk + nk 1 − A � � k A1,k ≤ nk 2 − . Ak � Ak  nk   + 1  (A-3) A Since A1,k < Ak , then 0 < A1,k < 1, and we have Sk ≤ 2nk . Similarly, for general k Nintf one can prove that: Sk ≤ Nintf nk . (A-4) Note that if one of the nodes within one hop from sink k transmits the data of CH i to the sink, then this indicates that all intermediate CHs within the routing path from that Nh,k and Nf,h,k are integer values in general, that is why we have the semi-equal sign in A-2. 1 Note 135 i to the sink have transmitted this data. That is P r{tki = 1} = P r{tki,1 = 1, ..., tk k = 1} = P r{tki,1 = 1}. i,N (A-5) i In other words, within a scheduling period of length Sk , all CHs would have transmitted their packets to the sink. Hence, the transmission probability P (tki = 1) = S1 . Thus, k 1 P (tki = 1) ≥ Nintf nk . (A-6) P (tki = 1) ≥ NF req . Nintf nk (A-7) For general NF req , we have 136 Appendix B Traffic Load Calculations used in Proposition 3.3 In this appendix, we calculate the traffic around each sink (CCH/RCH) in MC-WSN, by obtaining the number of clusters at each hop level and the amount of traffic required to be forwarded on average by each cluster head at each hop level. More specifically, O , NI O I we get Nf,h,k f,h,k , Nh,k , and Nh,k , ∀h, k. Traffic around the CCH: Recall that all nodes within the radius Ro route their traffic to the CCH, and the maximum hop distance is Rc . Let AT be the total area of the cell, A0 = πR02 be the area served by the CCH, and Ah,0 = π min{hRc , Ro }2 be the area until the hth hop level from the CCH. Therefore, the total number of cluster heads at the hth hop level from the CCH is: � � Ah,0 − Ah−1,0 Nh,0 � NCH . AT (B-1) Each cluster head at hop level h from the CCH forwards the traffic of Nf,h,0 cluster heads at higher hop levels, where Nf,h,0 � A0 − Ah,0 NCH . AT Nh,0 (B-2) We can obtain the total arrival rate at any CH within the service region of the CCH by substituting with Nf,h,0 in (3.19), which is then used in equations (3.30)-(3.32) to calculate the average delay per packet. 137 Traffic around the RCHs: Here, we analyze the traffic around the RCHs. Without loss of generality, we consider the RCH at θ = 0. Note that, due to the uniformity of the network, other RCHs will have the same amount of traffic at each of the served nodes. A CH with polar coordinates (x, θ), measured from the center of the cell, is at a � distance from the RCH equals to x2 − 2xRt cos(θ) + Rt2 , as illustrated in Figure 3.2. The farthest node at the hth hop level from a RCH is at a distance: � x2 − 2xRt cos(θ) + Rt2 = hRc . (B-3) That is, x2 − 2xRt cos(θ) + Rt2 = (hRc )2 , x2 − 2xRt cos(θ) + Rt2 − (hRc )2 = 0. (B-4) The solutions of x, denoted as xO (θ, h) and xI (θ, h), are functions of the angel θ and the hop level h, and are expressed as: � (hRc )2 − Rt2 sin2 (θ), � xI (θ, h) = Rt cos(θ) − (hRc )2 − Rt2 sin2 (θ), xO (θ, h) = Rt cos(θ) + (B-5) where xO (θ, h) corresponds to a CH at the outer region of the RCH (i.e., xO (θ, h) ≥ Rt ), and xI (θ, h) corresponds to a CH at the inner region of the RCH (i.e., xI (θ, h) < O , NI O I Rt ). In the following, we obtain Nf,h,k f,h,k , Nh,k , and Nh,k , ∀k ∈ {1, ..., K}. Due to the symmetry of the architecture, we get the traffic in the inner and outer regions π ]. It can be seen from of the RCH at θ = 0 focusing on the region where θ = [0, K 138 equation (B-5) that the condition on θ for a valid solution is θ≤ sin−1 � hRc Rt � . (B-6) In the following, we consider the outer region and the inner region separately. 1. For the outer region, we have xO (θ, h) ≥ Rt . It follows from (B-5) that: � (hRc )2 θ ≤ cos−1 1 − 2Rt2 � . (B-7) There are two cases in the outer region: d −R (a) When the number of hops to the RCH is h ≤ � cR t �: In this case, the c number of cluster heads up to hop level h is: T,O Nh,k � 2NCH � θ (h) � x (θ,h) 1 O θ=0 x=Rt fX (x)fθ (θ)dxdθ, (B-8) where θ1 (h) = min � π , sin−1 K � hRc Rt � , cos−1 � (hRc )2 1− 2Rt2 �� . (B-9) This can be seen from equations (B-6) and (B-7), and from the fact that π. the maximum θ within the RCH region under consideration is K d −R (b) When the number of hops to the RCH is h > � cR t �: In this case, there is c a lower bound on the angle θ such that xO (θ, h) ≤ dc . That is, Rt cos(θ) + � (hRc )2 − Rt2 sin2 (θ) ≤ dc , d2c + Rt2 − (hRc )2 ≥ 2dc Rt cos(θ). 139 (B-10) It follows that d2 + Rt2 − (hRc )2 cos(θ) ≤ c , 2Rt dc � � 2 + R2 − (hR )2 d c c t θ ≥ cos−1 . 2Rt dc (B-11) π and K ≥ 2, then θ is inversely proportional to Note that since 0 ≤ θ ≤ K cos(θ). From the above discussion, the number of cluster heads up to the d −R hth hop level from the outer region of the RCH, where h > � cR t �, is: c T,O Nh,k � 2NCH − �� θ1 (h) � xO (θ,h) θ=0 x=Rt � θ (h) � x (θ,h) 2 O θ=0 x=dc where θ1 (h) is defined in (B-9), and θ2 (h) = fX (x)fθ (θ)dxdθ � fX (x)fθ (θ)dxdθ . cos−1 (B-12) � 2 2 � dc +Rt −(hRc )2 . 2Rt dc 2. For the inner region, we have xI (θ, h) < Rt . It follows from (B-5) that: � (hRc )2 θ ≤ cos−1 1 − 2Rt2 � . (B-13) Note that this condition is the same as the one in (B-7). There are two cases in the inner region: R −R (a) When the number of hops to the RCH is h ≤ � tR o �: In this case, the c number of cluster heads up to the hth hop level from the inner region is: T,I Nh,k � 2NCH � θ (h) � R t 1 θ=0 x=xI (θ,h) where θ1 (h) is given in (B-9). 140 fX (x)fθ (θ)dxdθ, (B-14) R −R (b) When the number of hops to the RCH is h > � tR o �: In this case, the c integration is only over the area where x ≥ Ro , which imposes a lower bound on θ. That is, by following a similar procedure, we have: Rt cos(θ) − � (hRc )2 − Rt2 sin2 (θ) ≥ Ro , (Rt cos(θ) − Ro )2 ≥ (hRc )2 − Rt2 sin2 (θ), Rt2 + Ro2 − 2Rt Ro cos(θ) ≥ (hRc )2 . (B-15) It follows that, Rt2 + Ro2 − (hRc )2 cos(θ) ≤ , 2R R � o t � 2 + R2 − (hR )2 R c o t θ ≥ cos−1 . 2Ro Rt (B-16) Therefore, the total number of cluster heads in the inner region up to the R −R hth hop level from the RCH, where h > � tR o �, is: c T,I Nh,k � 2NCH − �� θ1 (h) � Rt θ=0 x=xI (θ,h) � θ (h) � Ro 3 θ=0 x=xI (θ,i) fX (x)fθ (θ)dxdθ � fX (x)fθ (θ)dxdθ , (B-17) � � 2 2 �� Rt +Ro −(hRc )2 −1 where θ3 (h) = max 0, cos . 2R R t o Note that the above integrals over θ do not have closed-form solution, but can be evaluated numerically. From the above discussions, we obtain the number of cluster heads at each hop 141 level from the outer and inner regions as follows: T,O T,O T,I T,I NO h,k = Nh,k − Nh−1,k , NIh,k = Nh,k − Nh−1,k . (B-18) We assume that the traffic load is divided evenly among the CHs at each hop level. Therefore, the average amount of traffic that a cluster head at the hth hop level from O /N I the outer/inner region (Nf,h,k f,h,k ) forwards is: T,O O Nf,h,k = T,O N O − Nh,k N ,k k NO h,k T,I I Nf,h,k = , T,I N I − Nh,k N ,k k NIh,k , (B-19) I where NO k and Nk are the maximum number of hops to RCH k from the outer and inner regions, respectively. 142 BIBLIOGRAPHY 143 BIBLIOGRAPHY [1] A. Bharathidasas and V. Anand, “Sensor networks: An overview,” Technical report, Dept. of Computer Science, University of California at Davis, 2002. [2] C. Chong and S. Kumar, “Sensor networks: evolution, opportunities, and challenges,” Proceedings of the IEEE, vol. 91, no. 8, pp. 1247 – 2056, Aug. 2003. [3] M. Tubaishat, P. Zhuang, Q. Qi, and Y. Shang, “Wireless sensor networks in intelligent transportation systems,” Wireless Communications and Mobile Computing, vol. 9, no. 3, pp. 287 – 302, Mar. 2009. [Online]. Available: http://dx.doi.org/10.1002/wcm.v9:3 [4] C.-Y. Chong and S. Kumar, “Sensor networks: evolution, opportunities, and challenges,” Proceedings of the IEEE, vol. 91, no. 8, pp. 1247 – 1256, 2003. [5] J. Hill, M. Horton, R. Kling, and L. Krishnamurthy, “The platforms enabling wireless sensor networks,” Communications of the ACM, vol. 47, no. 6, pp. 41 – 46, Jun. 2004. [Online]. Available: http://doi.acm.org/10.1145/990680.990705 [6] B. Tavli, K. Bicakci, R. Zilan, and J. Barcelo-Ordinas, “A survey of visual sensor network platforms,” Multimedia Tools and Applications, vol. 60, pp. 689 – 726, 2012. [Online]. Available: http://dx.doi.org/10.1007/s11042-011-0840-z [7] D. T. Fokum, D. Victor, S. Frost, D. Gary, and J. Minden, “An evaluation of sensing platforms used for sensor network research,” Tech. Rep., 2007. [8] J. Polastre, R. Szewczyk, and D. Culler, “Telos: enabling ultra-low power wireless research,” Fourth International Symposium on Information Processing in Sensor Networks, IPSN’05, pp. 364 – 369, Apr. 2005. [9] G. Zhou, C. Huang, T. Yan, T. He, J. A. Stankovic, and T. F. Abdelzaher, “Mmsn: Multi-frequency media access control for wireless sensor networks,” Proceedings 25th IEEE International Conference on Computer Communications INFOCOM’06, pp. 1 – 13, Apr. 2006. 144 [10] Crossbow, “Mica2: Wireless measurement system,” 2004. [11] ——, “Mica2dot: Wireless microsensor mote,” 2003. [12] ——, “Micaz: Wireless measurement system,” 2004. R [13] L. Nachman, R. Kling, R. Adler, J. Huang, and V. Hummel, “The Intel� mote platform: a bluetooth-based sensor network for industrial monitoring,” Fourth International Symposium on Information Processing in Sensor Networks, IPSN’05, pp. 437 – 442, Apr. 2005. [14] A. Zemlianov and G. de Veciana, “Capacity of ad hoc wireless networks with infrastructure support,” IEEE Journal on Selected Areas in Communications, vol. 23, no. 3, pp. 657 – 667, Mar. 2005. [15] G. Zhang, Y. Xu, X. Wang, and M. Guizani, “Capacity of hybrid wireless networks with directional antenna and delay constraint,” IEEE Transactions on Communications, vol. 58, no. 7, pp. 2097 – 2106, Jul. 2010. [16] C.-C. Shen, C. Srisathapornphat, and C. Jaikaeo, “Sensor information networking architecture and applications,” IEEE Personal Communications, vol. 8, no. 4, pp. 52 – 59, 2001. [17] G. Mergen, Z. Qing, and L. Tong, “Sensor networks with mobile access: Energy and capacity considerations,” IEEE Transactions on Communications, vol. 54, no. 11, pp. 2033 – 2044, Nov. 2006. [18] W. Liu, K. Lu, J. Wang, L. Huang, and D. Wu, “On the throughput capacity of wireless sensor networks with mobile relays,” IEEE Transactions on Vehicular Technology, vol. 61, no. 4, pp. 1801 – 1809, May 2012. [19] W. Liu, K. Lu, J. Wang, G. Xing, and L. Huang, “Performance analysis of wireless sensor networks with mobile sinks,” IEEE Transactions on Vehicular Technology, vol. 61, no. 6, pp. 2777 – 2788, Jul. 2012. [20] C. Avram, D. Radu, A. Astilean, and V. Cosma, “Ant routing protocol in a zigbee ad hoc sensors network for radiation level monitoring,” IEEE International Conference on Automation Quality and Testing Robotics, AQTR’10, vol. 3, pp. 1 – 6, May. 145 [21] R. Berry and R. Gallager, “Communication over fading channels with delay constraints,” IEEE Transactions on Information Theory, vol. 48, no. 5, pp. 1135 – 1149, May 2002. [22] P. Gupta and P. Kumar, “The capacity of wireless networks,” IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 388 – 404, Mar. 2000. [23] C. P. Chan, S. C. Liew, and A. Chan, “Many-to-one throughput capacity of IEEE 802.11 multihop wireless networks,” IEEE Transactions on Mobile Computing, vol. 8, no. 4, pp. 514 – 527, April 2009. [24] E. J. Duarte-Melo and M. Liu, “Data-gathering wireless sensor networks: organization and capacity,” Computer Networks, vol. 43, no. 4, pp. 519 – 537, 2003, wireless Sensor Networks. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S1389128603003578 [25] T. Cover and A. Gamal, “Capacity theorems for the relay channel,” IEEE Transactions on Information Theory, vol. 25, no. 5, pp. 572 – 584, Sep. 1979. [26] P. Gupta and P. Kumar, “Towards an information theory of large networks: an achievable rate region,” IEEE Transactions on Information Theory, vol. 49, no. 8, pp. 1877 – 1894, Aug. 2003. [27] H. El Gamal, “On the scaling laws of dense wireless sensor networks: the data gathering channel,” IEEE Transactions on Information Theory, vol. 51, no. 3, pp. 1229 – 1234, Mar. 2005. [28] M. Grossglauser and D. Tse, “Mobility increases the capacity of ad hoc wireless networks,” IEEE/ACM Transactions on Networking, vol. 10, no. 4, pp. 477 – 486, Aug. 2002. [29] S. Gandham, M. Dawande, R. Prakash, and S. Venkatesan, “Energy efficient schemes for wireless sensor networks with multiple mobile base stations,” IEEE Global Telecommunications Conference, GLOBECOM’03, vol. 1, pp. 377 – 381, Dec. 2003. [30] J. Luo and J.-P. Hubaux, “Joint mobility and routing for lifetime elongation in wireless sensor networks,” IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM’05, vol. 3, pp. 1735 – 1746, Mar. 2005. 146 [31] S. Marano, V. Matta, and L. Tong, “Distributed detection in the presence of byzantine attacks,” IEEE Transactions on Signal Processing, vol. 57, no. 1, pp. 16 – 29, Jan. 2009. [32] J. Newsome, E. Shi, D. Song, and A. Perrig, “The sybil attack in sensor networks: analysis & defenses,” Proceedings of the 3rd international symposium on Information processing in sensor networks, pp. 259 – 268, 2004. [Online]. Available: http://doi.acm.org/10.1145/984622.984660 [33] C. Karlof and D. Wagner, “Secure routing in wireless sensor networks: attacks and countermeasures,” IEEE International Workshop on Sensor Network Protocols and Applications, pp. 113 – 127, May 2003. [34] X. Chen, K. Makki, K. Yen, and N. Pissinou, “Sensor network security: a survey,” IEEE Communications Surveys Tutorials, vol. 11, no. 2, pp. 52 – 73, 2009. [35] Y. Zhang, W. Liu, W. Lou, and Y. Fang, “Location-based compromise-tolerant security mechanisms for wireless sensor networks,” IEEE Journal on Selected Areas in Communications, vol. 24, no. 2, pp. 247 – 260, Feb. [36] C. Chen, M. Song, and G. Hsieh, “Intrusion detection of sinkhole attacks in large-scale wireless sensor networks,” IEEE International Conference on Wireless Communications, Networking and Information Security, WCNIS’10, pp. 711 – 716, Jun. [37] Y. L. Sun, W. Yu, Z. Han, and K. Liu, “Information theoretic framework of trust modeling and evaluation for ad hoc networks,” IEEE Journal on Selected Areas in Communications, vol. 24, no. 2, pp. 305 – 317, Feb. 2006. [38] D. Martins and H. Guyennet, “Wireless sensor network attacks and security mechanisms: A short survey,” 13th International Conference on Network-Based Information Systems, NBiS’10, pp. 313 – 320, Sept. 2010. [39] D. Malan, “Crypto for tiny objects,” Tech. Rep., 2004. [40] L. Zhang and T. Li, “Anti-jamming message-driven frequency hopping; part ii: Capacity analysis under disguised jamming,” IEEE Transactions on Wireless Communications, vol. 12, no. 1, pp. 80 – 88, 2013. 147 [41] W. Xu, W. Trappe, and Y. Zhang, “Defending wireless sensor networks from radio interference through channel adaptation,” ACM Transactions on Sensor Networks, vol. 4, no. 4, pp. 1 – 34, Aug. 2008. [Online]. Available: http://doi.acm.org/10.1145/1387663.1387664 [42] M. Abdelhakim, L. Lightfoot, J. Ren, and T. Li, “Distributed detection in mobile access wireless sensor networks under byzantine attacks,” IEEE Transactions on Parallel and Distributed Systems, accepted. [43] M. Abdelhakim, J. Ren, and T. Li, “Mobile access coordinated wireless sensor networks – topology design and throughput analysis,” IEEE Global Communications Conference, GLOBECOM’13, 2013. [44] T. Li, M. Abdelhakim, and J. Ren, “N-hop networks — a general framework for wireless systems,” IEEE Wireless Communications Magazine, accepted. [45] M. Abdelhakim, L. Lightfoot, and T. Li, “Reliable data fusion in wireless sensor networks under byzantine attacks,” IEEE Military Communications Conference, MILCOM’11, Nov. 2011. [46] M. Abdelhakim, L. Zhang, J. Ren, and T. Li, “Cooperative sensing in cognitive networks under malicious attack,” IEEE International Conference on Acoustics Speech and Signal Processing, ICASSP’11, pp. 3004 – 3007, May 2011. [47] Y.-C. Wang and Y.-C. Tseng, “Distributed deployment schemes for mobile wireless sensor networks to ensure multilevel coverage,” IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 9, pp. 1280 – 1294, Sept. 2008. [48] P. Barooah, H. Chenji, R. Stoleru, and T. Kalmar-Nagy, “Cut detection in wireless sensor networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 3, pp. 483 – 490, Mar. 2012. [49] A. Perrig, R. Szewczyk, J. D. Tygar, V. Wen, and D. E. Culler, “Spins: security protocols for sensor networks,” Wireless Networks, vol. 8, pp. 521 – 534, Sept. 2002. [Online]. Available: http://dx.doi.org/10.1023/A:1016598314198 [50] C. Karlof, N. Sastry, and D. Wagner, “Tinysec: a link layer security architecture for wireless sensor networks,” Proceedings of the 2nd international conference on Embedded networked sensor systems, pp. 162 – 175, 2004. [Online]. Available: http://doi.acm.org/10.1145/1031495.1031515 148 [51] L. Lightfoot, J. Ren, and T. Li, “An energy efficient link-layer security protocol for wireless sensor networks,” IEEE International Conference on Electro/Information Technology, EIT 2007, pp. 233 – 238, May 2007. [52] I. Rodhe, C. Rohner, and A. Achtzehn, “n-lqa: n-layers query authentication in sensor networks,” IEEE Internatonal Conference on Mobile Adhoc and Sensor Systems, MASS’07, pp. 1 – 6, Oct. 2007. [53] W. Zhang, N. Subramanian, and G. Wang, “Lightweight and compromiseresilient message authentication in sensor networks,” IEEE 27th Conference on Computer Communications, INFOCOM’08, pp. 1418 – 1426, Apr. 2008. [54] H. Chan, A. Perrig, and D. Song, “Secure hierarchical in-network aggregation in sensor networks,” Proceedings of the 13th ACM conference on Computer and communications security, ACM CCS’06, pp. 278 – 287, 2006. [55] H. Kumar, D. Sarma, and A. Kar, “Security threats in wireless sensor networks,” IEEE Aerospace and Electronic Systems Magazine, vol. 23, no. 6, pp. 39 – 45, Jun. 2008. [56] B. Awerbuch, R. Curtmola, H. D., N.-R. C., and R. H., “Mitigating byzantine attacks in ad hoc wireless networks,” Technical report version 1, Mar. 2004. [57] S. Marano, V. Matta, and L. Tong, “Distributed detection in the presence of byzantine attack in large wireless sensor networks,” IEEE Military Communications Conference, MILCOM’06, pp. 1 – 4, Oct. 2006. [58] O. Kosut and L. Tong, “Distributed source coding in the presence of byzantine sensors,” IEEE Transactions on Information Theory, vol. 54, no. 6, pp. 2550 – 2565, Jun. 2008. [59] G. Latif-Shabgahi, “A novel algorithm for weighted average voting used in fault tolerant computing systems,” Microprocessors and Microsystems, vol. 28, no. 7, pp. 357 – 361, 2004. [60] Y. Brun, G. Edwards, J. Y. Bang, and N. Medvidovic, “Smart redundancy for distributed computation,” 2011 31st International Conference on Distributed Computing Systems, ICDCS’11, pp. 665 – 676, Jun. 2011. 149 [61] S. Wang, K. Yan, and H. Hsieh, “The byzantine agreement under mobile network,” IEEE International Conference on, Networking, Sensing and Control, vol. 1, pp. 46 – 51, Mar. 2004. [62] L. F. G. Sarmenta, “Sabotage-tolerance mechanisms for volunteer computing systems,” Future Generation Computer Systems, vol. 18, pp. 561 – 572, 2002. [63] P. Sridhar, A. Madni, and M. Jamshidi, “Hierarchical aggregation and intelligent monitoring and control in fault-tolerant wireless sensor networks,” IEEE Systems Journal, vol. 1, no. 1, pp. 38 – 54, Sept. 2007. [64] Q. Tian and E. Coyle, “Optimal distributed detection in clustered wireless sensor networks,” IEEE Transactions on Signal Processing, vol. 55, no. 7, pp. 3892 – 3904, Jul. 2007. [65] A. Rawat, P. Anand, H. Chen, and P. Varshney, “Collaborative spectrum sensing in the presence of byzantine attacks in cognitive radio networks,” IEEE Transactions on Signal Processing, vol. 59, no. 2, pp. 774 – 786, Feb. 2011. [66] R. Viswanathan and V. Aalo, “On counting rules in distributed detection,” IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 37, no. 5, pp. 772 – 775, May 1989. [67] R. Niu and P. Varshney, “Performance analysis of distributed detection in a random sensor field,” IEEE Transactions on Signal Processing, vol. 56, no. 1, pp. 339 – 349, Jan. 2008. [68] V. Aalo and G. Efthymoglou, “Decision fusion schemes for wireless sensor networks operating in a nakagami-m fading environment,” IEEE 20th International Symposium on Personal, Indoor and Mobile Radio Communications, PIMRC’09, pp. 2720 – 2724, Sept. 2009. [69] H. Wang, L. Lightfoot, and T. Li, “On phy-layer security of cognitive radio: Collaborative sensing under malicious attacks,” 44th Annual Conference on Information Sciences and Systems, CISS’12, pp. 1 – 6, Mar. 2010. [70] L. Tong, Q. Zhao, and S. Adireddy, “Sensor networks with mobile agents,” IEEE Military Communications Conference, MILCOM’03, vol. 1, pp. 688 – 693, Oct. 2003. 150 [71] H. Urkowitz, “Energy detection of unknown deterministic signals,” Proceedings of the IEEE, vol. 55, no. 4, pp. 523 – 531, Apr. 1967. [72] M. R. Fellows, F. V. Fomin, D. Lokshtanov, F. Rosamond, S. Saurabh, and Y. Villanger, “Local search: Is brute-force avoidable?” Journal of Computer and System Sciences, vol. 78, no. 3, pp. 707 – 719, 2012. [73] M. Abdelhakim, J. Ren, and T. Li, “Reliable cooperative sensing in cognitive networks,” Wireless Algorithms, Systems, and Applications, WASA’12, Springer Berlin Heidelberg, vol. 7405, pp. 206 – 217, 2012. [74] E. R. Love, “64.4 some logarithm inequalities,” The Mathematical Gazette, vol. 64, no. 427, pp. 55 – 57, 1980. [Online]. Available: http://www.jstor.org/stable/3615890 [75] U. Madhow, Fundamentals of digital communication. Press, 2008, p. 483. Cambridge University [76] W. Wang, H. Li, Y. Sun, and Z. Han, “Catchit: Detect malicious nodes in collaborative spectrum sensing,” IEEE Global Telecommunications Conference, GLOBECOM’09, pp. 1 – 6, 2009. [77] A. Ghasemi and E. Sousa, “Collaborative spectrum sensing for opportunistic access in fading environments,” First IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks, DySPAN’05., pp. 131 – 136, 2005. [78] M. Abdelhakim, L. Lightfoot, J. Ren, and T. Li, “Architecture design of mobile access coordinated wireless sensor networks,” IEEE International Conference on Communications, ICC’13, pp. 1720 – 1724, Jun. 2013. [79] I. Maza, F. Caballero, J. Capitan, J. Martinez-de Dios, and A. Ollero, “A distributed architecture for a robotic platform with aerial sensor transportation and self-deployment capabilities,” Journal of Field Robotics, vol. 28, no. 3, pp. 303 – 328, 2011. [Online]. Available: http://dx.doi.org/10.1002/rob.20383 [80] P. Corke, S. Hrabar, R. Peterson, D. Rus, S. Saripalli, and G. Sukhatme, “Autonomous deployment and repair of a sensor network using an unmanned aerial vehicle,” IEEE International Conference on Robotics and Automation, ICRA’04, vol. 4, pp. 3602 – 3608, 26-May 1, 2004. 151 [81] H.-C. Chen, D. Kung, D. Hague, M. Muccio, and B. Poland, “Collaborative compressive spectrum sensing in a U AV environment,” IEEE Military Communications Conference, MILCOM’11, Nov. 2011. [82] J. Luo and A. Ephremides, “On the throughput, capacity, and stability regions of random multiple access,” IEEE Transactions on Information Theory, vol. 52, no. 6, pp. 2593 – 2607, Jun. 2006. [83] G. Mergen and L. Tong, “Maximum asymptotic stable throughput of opportunistic slotted ALOHA and applications to CDMA networks,” IEEE Transactions on Wireless Communications, vol. 6, no. 4, pp. 1159 – 1163, Apr. 2007. [84] A. Behzad and I. Rubin, “High transmission power increases the capacity of ad hoc wireless networks,” IEEE Transactions on Wireless Communications, vol. 5, no. 1, pp. 156 – 165, 2006. [85] A. Gamal, J. Mammen, B. Prabhakar, and D. Shah, “Throughput-delay trade-off in wireless networks,” Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, INFOCOM’04, vol. 1, 2004. [86] M. Nekoui and H. Pishro-Nik, “Throughput scaling laws for vehicular ad hoc networks,” IEEE Transactions on Wireless Communications, vol. 11, no. 8, pp. 2895 – 2905, 2012. [87] H. Wu, C. Qiao, S. De, and O. Tonguz, “Integrated cellular and ad hoc relaying systems: iCAR,” IEEE Journal on Selected Areas in Communications, vol. 19, no. 10, pp. 2105 – 2115, 2001. [88] L. Kleinrock, Communication nets; stochastic message flow and delay. McGrawHill, 1964. [89] W. Szpankowski, Stability Conditions for Some Multiqueue Distributed Systems: Buffered Random Access Systems, ser. Technical report. Purdue University, Department of Computer Sciences, 1992, no. 29. [Online]. Available: http://books.google.com/books?id=DcrHuAAACAAJ [90] R. Rao and A. Ephremides, “On the stability of interacting queues in a multipleaccess system,” IEEE Transactions on Information Theory, vol. 34, no. 5, pp. 918 – 930, Sep. 1988. 152 [91] V. Naware, G. Mergen, and L. Tong, “Stability and delay of finite-user slotted ALOHA with multipacket reception,” IEEE Transactions on Information Theory, vol. 51, no. 7, pp. 2636 – 2656, Jul. 2005. [92] H. Wang and T. Li, “Hybrid ALOHA: A novel mac protocol,” IEEE Transactions on Signal Processing, vol. 55, no. 12, pp. 5821 – 5832, Dec. 2007. [93] R. M. Loynes, “The stability of a queue with non-independent inter-arrival and service times,” Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, pp. 497 – 520, 1962. [94] S. Hanly and D. Tse, “Multiaccess fading channels. ii. delay-limited capacities,” IEEE Transactions on Information Theory, vol. 44, no. 7, pp. 2816 – 2831, 1998. [95] R. Negi and J. Cioffi, “Delay-constrained capacity with causal feedback,” IEEE Transactions on Information Theory, vol. 48, no. 9, pp. 2478 – 2494, 2002. [96] B. W. Conolly, “The waiting time process for a certain correlated queue,” Operations Research, vol. 16, no. 5, pp. 1006 – 1015, 1968. [Online]. Available: http://www.jstor.org/stable/168493 [97] K. Fendick, V. Saksena, and W. Whitt, “Dependence in packet queues,” IEEE Transactions on Communications, vol. 37, no. 11, pp. 1173 – 1183, 1989. [98] E. Modiano, J. Wieselthier, and A. Ephremides, “A simple analysis of average queueing delay in tree networks,” IEEE Transactions on Information Theory, vol. 42, no. 2, pp. 660 – 664, 1996. [99] M. Neely, C. Rohrs, and E. Modiano, “Equivalent models for queueing analysis of deterministic service time tree networks,” IEEE Transactions on Information Theory, vol. 51, no. 10, pp. 3576 – 3584, 2005. [100] G. Gupta and N. Shroff, “Delay analysis for multi-hop wireless networks,” IEEE INFOCOM, pp. 2356 – 2364, 2009. [101] D. Bertsekas and R. Gallager, Data Networks. Prentice-Hall, 1992. [102] L. Galluccio and S. Palazzo, “End-to-end delay and network lifetime analysis in a wireless sensor network performing data aggregation,” IEEE Global Telecommunications Conference, GLOBECOM’09, pp. 1 – 6, 2009. 153 [103] N. Bisnik and A. A. Abouzeid, “Queuing network models for delay analysis of multihop wireless ad hoc networks,” Ad Hoc Networks, vol. 7, no. 1, pp. 79 – 97, 2009. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S1570870507001813 [104] Y. Wang, M. C. Vuran, and S. Goddard, “Cross-layer analysis of the end-toend delay distribution in wireless sensor networks,” IEEE/ACM Transactions on Networking, vol. 20, no. 1, pp. 305 – 318, 2012. [105] A. Sample, D. Yeager, P. Powledge, A. Mamishev, and J. Smith, “Design of an rfid-based battery-free programmable sensing platform,” IEEE Transactions on Instrumentation and Measurement, vol. 57, no. 11, pp. 2608 – 2615, 2008. [106] J. Ren, Y. Li, and T. Li, “Spm: Source privacy for mobile ad hoc networks,” EURASIP Journal on Wireless Communications and Networking, 2010. [107] F. Baccelli, B. Blaszczyszyn, and P. Muhlethaler, “An Aloha protocol for multihop mobile wireless networks,” IEEE Transactions on Information Theory, vol. 52, no. 2, pp. 421 – 436, 2006. [108] S. Choudhury and J. D. Gibson, “Ergodic capacity, outage capacity, and information transmission over Rayleigh fading channels,” Information Theory and Applications Workshop, 2007. [109] A. Abdrabou and W. Zhuang, “Service time approximation in IEEE 802.11 single-hop ad hoc networks,” IEEE Transactions on Wireless Communications, vol. 7, no. 1, pp. 305 – 313, 2008. [110] C. Goldschmidt, “The chen-stein method for convergence of distributions,” Masters-level essay, University of Cambridge, 2000. [111] C.-S. Chang, “Stability, queue length, and delay of deterministic and stochastic queueing networks,” IEEE Transactions on Automatic Control, vol. 39, no. 5, pp. 913 – 931, 1994. [112] A. Somasundara, A. Kansal, D. Jea, D. Estrin, and M. Srivastava, “Controllably mobile infrastructure for low energy embedded networks,” IEEE Transactions on Mobile Computing, vol. 5, no. 8, pp. 958 – 973, Aug. 2006. 154 [113] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “An application-specific protocol architecture for wireless microsensor networks,” IEEE Transactions on Wireless Communications, vol. 1, no. 4, pp. 660 – 670, Oct. 2002. [114] “1900 to 1999,” http://www.deutsches-telefon-museum.eu/1900.htm, Dec. 2007. [115] L. H. Anderson, “The first walkie-talkie radio - an affectionate look back in time and some thoughts about the first true fabled walkie-talkie,” Jun. 2005. [116] R. Frenkiel, “Creating cellular: A history of the AMPS project (1971-1983) [History of Communications],” IEEE Communications Magazine, vol. 48, no. 9, pp. 14 – 24, 2010. [117] D. H. Ring, “Mobile telephony - wide area coverage - case 20564,” 1947. [118] “IEEE Standard for Local and metropolitan area networks-Part 16: Air Interface for Fixed Broadband Wireless Access Systems,” IEEE Std 802.16-2004, 2004. [119] “3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (E-UTRA) and Evolved Universal Terrestrial Radio Access Network (E-UTRAN); Overall description; Stage 2 (Release 10),” 3GPP TS 36.300 V10.4.0 (2011-06), 2011. [120] I. Chlamtac, M. Conti, and J. J.-N. Liu, “Mobile ad hoc networking: imperatives and challenges,” Ad Hoc Networks, vol. 1, no. 1, pp. 13 – 64, 2003. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S1570870503000131 [121] I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine, vol. 40, no. 8, pp. 102 – 114, 2002. [122] F. Hu, M. Jiang, L. Celentano, and Y. Xiao, “Robust medical ad hoc sensor networks (masn) with wavelet-based ECG data mining,” Ad Hoc Networks, vol. 6, no. 7, pp. 986 – 1012, 2008. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S157087050700145X [123] A. Zadeh, B. Jabbari, R. Pickholtz, and B. Vojcic, “Self-organizing packet radio ad hoc networks with overlay (soprano),” IEEE Communications Magazine, vol. 40, no. 6, pp. 149 – 157, 2002. 155 [124] “IEEE Draft Standard for Information Technology-Telecommunications and information exchange between systems-Local and metropolitan area networksSpecific requirements-Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications Amendment 10: Mesh Networking,” IEEE P802.11s/D10.0, March 2011, pp. 1 – 379, 2011. [125] G. Neonakis Aggelou and R. Tafazolli, “On the relaying capability of nextgeneration GSM cellular networks,” IEEE Personal Communications, vol. 8, no. 1, pp. 40 – 47, 2001. [126] K. Doppler, M. Rinne, C. Wijting, C. Ribeiro, and K. Hugl, “Device-to-device communication as an underlay to lte-advanced networks,” IEEE Communications Magazine, vol. 47, no. 12, pp. 42 – 49, Dec. 2009. [127] P. Janis, C. Yu, K. Doppler, C. Ribeiro, C. Wijting, K. Hugl, O. Tirkkonen, and V. Koivunen, “Device-to-device communication underlaying cellular communications systems,” International Journal of Communications, Network and System Sciences, vol. 2, no. 3, pp. 169 – 178, Jun. 2009. [128] M.-H. Han, B.-G. Kim, and J.-W. Lee, “Subchannel and Transmission Mode Scheduling for D2D Communication in OFDMA Networks,” IEEE Vehicular Technology Conference, VTC 2012, pp. 1 – 5, 2012. [129] H.-Y. Hsieh and R. Sivakumar, “On using peer-to-peer communication in cellular wireless data networks,” IEEE Transactions on Mobile Computing, vol. 3, no. 1, pp. 57 – 72, 2004. [130] A. Damnjanovic, J. Montojo, Y. Wei, T. Ji, T. Luo, M. Vajapeyam, T. Yoo, O. Song, and D. Malladi, “A survey on 3gpp heterogeneous networks,” IEEE Wireless Communications, vol. 18, no. 3, pp. 10 – 21, 2011. [131] J. Sydir and R. Taori, “An evolved cellular system architecture incorporating relay stations,” IEEE Communications Magazine, vol. 47, no. 6, pp. 115 – 121, 2009. [132] A. C. Guyton and J. E. Hall, Textbook of medical physiology. Saunders, 2000. Philadelphia, [133] T. Cover and A. Gamal, “Capacity theorems for the relay channel,” IEEE Transactions on Information Theory, vol. 25, no. 5, pp. 572 – 584, sep 1979. 156 [134] Y. Chen and J. Andrews, “An upper bound on multihop transmission capacity with dynamic routing selection,” IEEE Transactions on Information Theory, vol. 58, no. 6, pp. 3751 – 3765, june 2012. [135] N. Bisnik and A. Abouzeid, “Queuing network models for delay analysis of multihop wireless ad hoc networks,” Proceedings of the international conference on Wireless communications and mobile computing, IWCMC’06, pp. 773 – 778, 2006. [Online]. Available: http://doi.acm.org/10.1145/1143549.1143704 [136] R. Berry and R. Gallager, “Communication over fading channels with delay constraints,” IEEE Transactions on Information Theory, vol. 48, no. 5, pp. 1135 – 1149, 2002. 157