UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Secure and efficient wireless ad hoc networking Khabbazian, Majid 2008

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
24-ubc_2008_fall_khabbazian_majid.pdf [ 6.87MB ]
Metadata
JSON: 24-1.0066825.json
JSON-LD: 24-1.0066825-ld.json
RDF/XML (Pretty): 24-1.0066825-rdf.xml
RDF/JSON: 24-1.0066825-rdf.json
Turtle: 24-1.0066825-turtle.txt
N-Triples: 24-1.0066825-rdf-ntriples.txt
Original Record: 24-1.0066825-source.json
Full Text
24-1.0066825-fulltext.txt
Citation
24-1.0066825.ris

Full Text

Secure and Efficient Wireless A d Hoc Networking by M a j i d Khabbazian B . S c , Sharif University of Technology, 2002 M . S c , The University of Vic tor ia , 2004 A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F Doctor of Philosophy in The Faculty of Graduate Studies (Electrical and Computer Engineering) The University Of Br i t i sh Columbia (Vancouver) August, 2008 © M a j i d Khabbazian 2008 Abstract Wireless ad hoc networks have been emerged to support applications, in which it is required/desired to have wireless communications among a variety of devices without relying on any infrastructure or central managements. In ad hoc networks, wireless devices, simply called nodes, have l imited transmis- sion range. Therefore, each node can directly communicate with only those within its transmission range and requires other nodes to act as routers in or- der to communicate with out-of-range destinations. One of the fundamental operations in ad hoc networks is broadcasting, where a node sends a message to a l l other nodes in the network. This can be achieved through flooding, in which every node transmits the first copy of the received message. How- ever, flooding can impose a large number of redundant transmissions, which can result in significant waste of constrained resources such as bandwidth and battery power. One of the contributions of this work is to propose ef- ficient broadcast algorithms which can significantly reduce the number of redundant transmissions. We also consider some of the security issues of ad hoc networks. In particular, we carefully analyze the effect of the wormhole attack, which is one of the most severe threats against ad hoc networks. We also propose a countermeasure, which is an improvement over the exist- ing timing-based solutions against the wormhole attack. Finally, in the last chapter, we propose novel point compression techniques which can be used in El l ip t i c Curve Cryptography ( E C C ) . E C C can provide the same level of security as other public key cryptosystems (such as R S A ) with substantially smaller key sizes. Smaller keys can result in smaller system parameters, bandwidth savings, faster implementations and lower power consumption. These advantages make E C C interesting for ad hoc networks wi th restricted devices. Table of Contents Abstract i i Table of Contents i i i List of Tables iv List of Figures v Acknowledgements v i Dedication v i i Statement of Co-Authorship v i i i 1 Introduction and Background 1 1.1 Introduction and Motivat ion 1 1.2 Wireless A d Hoc Networks 2 1.2.1 Modeling Wireless A d Hoc Networks 2 1.2.2 Broadcasting and Routing 2 1.2.3 Wormhole Attack 3 1.3 El l ipt i c Curve Cryptography 4 1.4 Thesis Contribution 5 Bibliography 7 2 Efficient Broadcasting in Wireless A d Hoc Networks . . . . 9 2.1 Introduction 9 2.2 System Model 11 2.3 A n Efficient Neighbor-Designating Broadcast Algor i thm . . . 12 2.3.1 Algor i thm Structure 12 2.3.2 Forwarding-Node Selection Algor i thm 13 2.3.3 Reducing the Number of Forwarding Nodes 22 2.3.4 Maximiz ing the M i n i m u m Node Weight of B-coverage Set 22 2.3.5 Similarity W i t h A Topology Control Algor i thm . . . . 24 2.4 A Highly Efficient Self-Pruning broadcast algorithm 27 2.4.1 Algor i thm Structure 27 2.4.2 A Responsibility-Based Scheme 28 2.4.3 A Property of the Proposed R B S 32 2.5 Simulation 37 2.5.1 Average Number of Nodes Selected by the Proposed 37 2.5.2 Probabil ity of Broadcast using the Proposed R B S . . . 38 2.5.3 Performance of Proposed Neighbor-Designating 42 2.6 Summary 48 Bibliography 49 3 Localized Broadcasting with Bounded 52 3.1 Introduction 52 3.1.1 Related Work 53 3.1.2 Our Contribution 55 3.2 System Model 56 3.3 Broadcast Algorithms Based on 1-hop Neighbor Information . 57 3.3.1 Neighbor-Designating Algorithms 57 3.3.2 Self-Pruning Algorithms 60 3.4 A n Efficient Self-Pruning Broadcast A lgor i thm 61 3.4.1 Analysis of the Proposed Broadcast Algor i thm . . . . 63 3.4.2 Efficient Algorithms for Computing the Responsibility Condit ion 67 3.4.3 Reducing Bandwidth Requirements 69 3.5 Relaxing Some of the System-Model Assumptions 72 3.5.1 Broadcasting Under Uncertain Position Information . 73 3.5.2 Relaxing the Homogeneous Network Assumption . . . 80 3.5.3 Broadcasting in Three-Dimensions 81 3.6 Simulation 82 3.6.1 Reducing Bandwidth Overhead 82 3.6.2 Performance of the Proposed Broadcast Algor i thm . . 82 3.7 Summary 88 Bibliography 89 4 Wormhole Attack in Wireless A d H o c Networks 91 4.1 Introduction 91 4.2 Related Work 93 4.3 Wormhole Attack Analysis 95 4.3.1 Approximating the Length of the Shortest Path . . . . 96 4.3.2 Targeting al l of the nodes in the Network 97 4.3.3 Targeting a Particular Node in the Network 103 4.4 Wormhole Attack Analysis for a Generic Network 107 4.5 Wormhole Attack Countermeasure I l l 4.6 Summary 114 Bibliography 115 5 Double Point Compression 117 5.1 Introduction 117 5.2 EUiptic Curves: Definition and Operations 119 5.3 Point Compression 120 5.3.1 Double Point Compression 121 5.3.2 A n Extension to Triple Point Compression 123 5.3.3 Compressing Mult ip le Points 127 5.4 Point Mult iphcat ion 127 5.4.1 F ixed point multiphcation ( F P M ) 127 5.4.2 Random Point Mult iphcat ion ( R P M ) 128 5.4.3 Extending R P M Algorithms 130 5.5 Part ia l ly Random Point Mult iphcat ion ( P R P M ) 131 5.5.1 Speeding up P R P M 132 5.5.2 Performance Analysis of the P R P M Algor i thm . . . . 1 3 4 5.5.3 Parallel Processing of the P R P M Algor i thm 138 5.6 Summary 139 Bibliography 140 6 Summary and Conclusion 142 Bibliography 146 Appendices A List of Publications 147 List of Tables 2.1 Simulation parameters 44 2.2 Algorithms used in the simulation 45 3.1 Simulation parameters 84 5.1 Elhpt ic curve point addition, P3 = Pi + P2 120 5.2 El l ipt i c curve point inversion 120 5.3 Triple Point Compression 126 5.4 Cost of the R P M algorithm 136 5.5 Cost of the P R P M algorithm for n = 2 137 5.6 Cost of the P R P M algorithm f o r n = 3 137 5.7 Cost of the P R P M algorithm for n = 4 137 List of Figures 2.1 A bulged slice around A 15 2.2 Left bulged slice of B and right bulged slice of C around A. . 15 2.3 Upper bound on the distance between nodes inside a bulged slice 16 2.4 Illustration of Lemmas 2.2 and 2.3 17 2.5 The counterexample for ct = ^ 26 2.6 A counterexample for a = | 26 2.7 A n example of an R B S decision 30 2.8 A n instance of using the proposed broadcast algorithm 31 2.9 Finding a lower bound for A{I{VA,R, VB,R, T>QQB)) 35 2.10 Average number of nodes selected by the proposed slice-based algorithm 38 2.11 Probabihty of broadcast for R = 300m 39 2.12 Probabil i ty of broadcast for R = 400m 40 2.13 Probabihty of broadcast for R = 500m 40 2.14 Probabihty of broadcast for R = 600m 41 2.15 Broadcasting nodes in a 1000 x lOOOm^ square area wi th 400 nodes 41 2.16 Ratio of broadcasting nodes vs. total number of nodes 45 2.17 Ratio of broadcasting nodes vs. transmission range 46 2.18 Ratio of broadcasting nodes vs. total number of nodes 46 2.19 Average delivery ratio vs. probability of message-reception failure 47 2.20 Average delivery ratio vs. probability of message-reception failure 47 3.1 A n example of a node on the network boundary 58 3.2 Two worst-case examples for Theorem 3.1 59 3.3 A worst-case example for Theorem 3.2 61 3.4 A n example of self-pruning based on the responsibility condition. 63 3.5 Three co-centered disks; 6 DQ R and A^g. e DQBR - DQ m- 66 3.6 Partit ioning the network into square cells 78 3.7 The ratio ^ ^ ^ ^ ^ x 100 against the total number of neighbors. 83 3.8 Broadcasting nodes in a 10^ x lO^m^ square area with 400 nodes. 85 3.9 Ratio of broadcasting nodes vs. transmission range 85 3.10 Ratio of broadcasting nodes vs. total number of nodes 86 3.11 Average delay vs. total number nodes 86 3.12 Ratio of broadcasting nodes of the proposed algorithm 87 3.13 Ratio of broadcasting nodes of the proposed algorithm in a network 87 4.1 F inding a path between 5 and 97 4.2 Partit ioning the network into regions 72-1 and 7̂ 2 98 4.3 Computing the area of Us using polar coordinates 101 4.4 Percentage of affected communications across the network. . . 102 4.5 Partit ioning a network with several attackers into Voronoi Cells. 103 4.6 Computing the area of TZM 105 4.7 Percentage of affected communications to / f rom the target node. 107 4.8 Unreachable region for the target node under attack 108 4.9 Percentage of maximum number of affected communications . . . I l l 5.1 Performance comparison of Algorithms 5.2 and 5.3 135 Acknowledgements First and foremost, I would like to acknowledge my thesis supervisor, Pro - fessor Vi jay Bhargava, for his guidance and support. M y respectful gratitude goes to my committee: Professor Ian Blake, Professor Lutz Lampe, Victor Leung, Professor Br ian Marcus and Professor Vincent Wong, for giving valuable suggestions, providing constructive criticism, and proofreading the thesis. M y P h D experience was made more enjoyable by my friends and colleagues from the ITS lab. I would like to thank al l of them for their friendship, help with research problems and our fun discussions and lab outings. Last but not least, I would like to thank my parents and my wife for their unconditional love, encouragement and support. Dedication To my lovely wife and our little princess statement of Co-Authorship M a j i d Khabbazian is the primary author of the papers presented in this work. For al l these papers, M r . Khabbazian identified and proposed the research topic, performed the literature survey and research, analyzed the data, performed the simulations and prepared the manuscripts under the supervision and direction of Professor Vi jay Bhargava (and Professor Aaron Gull iver for the last chapter). M r . Khabbazian was assisted in preparing the papers presented in Chapter 4 and Chapter 5 by M r . Hugues Mercier and Professor Gulliver, respectively. A l l this work has been done completely during M r . Khabbazian's P h . D . program. None of the papers presented in this work have been received credit or presented in any other thesis work. Chapter 1 Introduction and Background 1.1 Introduction and Motivation In various scenarios, it is required or desirable to have wireless commu- nications between different devices (simply called nodes) without relying on any centralized infrastructure. For example, in battlefields or in emer- gency/rescue operations, it is often impractical to have an infrastructure and to rely on centralized and organized connectivity. Many of such scenarios can be considered as applications of wireless ad hoc networks. A wireless ad hoc network can be seen as a collection of self-organizing nodes that can communicate over relatively l imited bandwidth wireless links. Each node is equipped wi th a transceiver with l imited transmission range and thus, has to rely on other nodes in order to communicate with destinations outside its transmission range. To establish a communication, the sender first needs to discover a route to the destination node. It then requires al l the intermediate nodes on the route to act as a router and forward the packets towards the destination. In ad hoc networks, nodes may move, enter or exit the network. Therefore, the network topology can change and thus an established route (hence the communication) may become broken. In this case, a new route may need to be established through a route discovery phase. Wireless devices in ad hoc networks have typically l imited resources such as battery lifetime, bandwidth and computational power. Therefore, it is crucial to design efficient methods for ad hoc networks in order to save these scarce resources. Also, wireless ad hoc networks are vulnerable to several at- tacks. In real environments, a malicious node can easily jo in the network and attack it by simply violating the protocol specifications. Identity spoofing, message tampering, eavesdropping, rushing attack [1] and wormhole attack 2] are a few examples of the attacks that can be employed by malicious nodes. Devising security solution for wireless ad hoc networks is not t r iv ia l due to the network specific characteristics such as open environment, dy- namic topology, lack of centralized infrastructure and l imited bandwidth, battery lifetime and computational power. The aim and motivation of this work is to construct novel methods in an attempt to improve the security and efficiency of ad hoc networks. 1.2 Wireless A d Hoc Networks 1.2.1 Modeling Wireless A d Hoc Networks A wireless ad hoc network can be modeled as a directed graph in which each vertex represents a wireless node and there is an edge from vertex Vi to V2 if and only if V2^s corresponding node is within the transmission range of t?i's corresponding node. In general, the wireless devices may have different transmission ranges. Moreover, two nodes within transmission ranges of each other may not be able to communicate because of, for example, presence of an obstacle. However, to achieve strong theoretical results, it is widely assumed that nodes have identical transmission range R and that two nodes are connected if their Euclidean distance is not greater than R. Using these assumptions, the network can be modeled by a unit disk graph. 1.2.2 Broadcasting and Routing Broadcasting and routing are two fundamental operations in ad hoc networks. In broadcasting, a single node sends a message to al l other nodes in the network. The simplest way of broadcasting is v ia flooding. In flooding, each node transmits the received message to al l its neighbors (the nodes within its transmission range) if it has not received the message before and drops the message otherwise. Clearly, flooding finally terminates and a l l nodes receive the message if the network is static and connected and if there is no error or collision in transmissions. However, this is achieved at the cost of one transmission per each single node in the network. In practice, not a l l the nodes are required to transmit the message in order to deliver it to al l the nodes in the network. In particular, the number of redundant transmissions (broadcasts) significantly increases as the average number of neighbors of each node increases. There are many alternative broadcast algorithms proposed to reduce the number of transmissions. In Chapters 2 and 3, we discuss some of the best existing broadcast algorithms and propose two localized broadcast algorithms. Routing algorithms are responsible for providing end-to-end communica- tions in ad hoc networks. There are numerous routing protocols proposed for ad hoc networks [3]. These protocols can be divided into two main cate- gories: Proactive (Table-Driven) and Reactive (On-Demand) routing proto- cols. Proactive routing protocols maintain a constant network view by saving routes to al l possible destinations in a few tables and updating them every time the network topology changes. Using proactive routing protocols, nodes can quickly start communication as there is no latency in route discovery. However, they can cause a substantial overhead when the mobility rate or the number of nodes in the network is high. In reactive routing protocols, a route discovery is performed only when a new data communication needs to be established. Consequently, routing overhead is significantly reduced as there is no need to maintain routes, which are not used. A d Hoc On-Demand Distance Vector Routing ( A O D V ) [4] and Dynamic Source Routing (DSR) [5] are two well-known examples of on-demand routing protocols. Bo th A O D V and D S R protocols consist of two major activities: route discovery and route maintenance. Route discovery phase is initiated when the source node has no val id route to the destination. In this phase, the source node broadcasts a Route Request ( R R E Q ) packet. When the destination node receives the R R E Q packet, it replies to the source node with a Route Reply ( R R E P ) packet. Packets in A O D V only contain the address of the destination node whereas in D S R they also include the address of al l the intermediate nodes. 1.2.3 Wormhole Attack As mentioned earlier, ad hoc networks are vulnerable to many different at- tacks. The wormhole attack is one of the most severe attacks that can form a serious threat against ad hoc networks. The wormhole attack is typically launched by two (or more) malicious nodes located far from each other. In this attack, the malicious nodes transfer the received packets to each other through a long "v i r tua l " link between them. The link can be formed using an in-band (tunneling) or out-of-band communications and can attract many packets since it can transfer packets between far apart locations with short delays and/or small number of hops. This can be considered as a useful ser- vice from the malicious nodes if they do not take advantage of the v irtual l ink. However, in practice, the malicious nodes can employ this l ink to ana- lyze the network traffic or to make a denial-of-service attack by, for example. selectively dropping the packets. Unfortunately, the attackers do not need to compromise any node to launch this attack and the attack cannot be coun- tered with cryptography alone. Moreover, as we wi l l analytically show in Chapter 4, using this attack, the malicious nodes can control/disrupt many communications in the network. The existing solutions against wormhole attack often try to bound the distance a packet can travel by using location or t iming information. For example, in timing-based solutions [2, 6], the sender attempts to bound the packet traveling distance or the distance to the receiver by, for instance, timestamping the packet or through a fast bit exchange between itself and the receiver. There are some other techniques which use different approaches such as using directional antennas [7] or graph topology distortion [8] in order to detect wormhole attacks. In Chapter 4, we briefly explain some of these solutions against the wormhole attack and propose a countermeasure which is an improvement over the existing timing-based methods. 1.3 Elliptic Curve Cryptography El l ipt i c curve cryptography ( E C C ) [9] is widely regarded as the strongest asymmetric cryptosystem for a given key length. In other words, E C C can provide the same level of security as other public key cryptosystems (such as R S A ) with substantially smaller key sizes. Smaller keys can result in smaller system parameters, bandwidth savings, faster implementations and lower power consumption. These advantages make elliptic curve cryptogra- phy appropriate for ad hoc networks with restricted devices such as mobile phones. E C C is based on arithmetic of elliptic curves. A n elliptic curve E over the field F is a curve in the so called "long WeirestraB form" E -.y^ + aixy + asy = + a^x^ + a^x + ae, (1.1) where a i , . . . , a 6 e F . Let ChariJF) denote the characteristic of the field F . The above equation can be simplified to E : y'^ = x^ + ax + b and E : y'^ + xy = x^ + ax"^ + b when Char{¥) 5̂  2,3 and Char{F) = 2, respectively. Clearly, each point on this curve can be represented by (x, r/), where x and y are called the a;-coordinate and ^/-coordinate of the point, respectively. A n elliptic curve point can also be represented using its a;-coordinate and a an extra bit. Having the x-coordinate of the point, the y-coordinate can be computed by solving the elliptic curve equation. Since it is a quadratic equation, there wi l l be two possible solutions; thus the extra bit is needed to distinguish the correct solution. This simple technique is called single point compression and is patented by Certicom Corporation. In Chapter 5, we propose a double point and a triple point compression schemes, which allow a compact representation of elliptic curve points without the computational cost associated with the single point compression. The double point and triple point compression schemes can be employed to save about 25% and 33% of bandwidth/memory, respectively. 1.4 Thesis Contribution In this section, we explain the organization of this work along wi th our con- tributions in designing efficient and secure algorithms. The main objective of this work is to develop efficient algorithms and secure schemes for wireless ad hoc networks. As mentioned earlier, broad- casting is a fundamental primitive in ad hoc networks. In broadcasting, many nodes may get involved in transmitting a message. Consequently, it can sig- nificantly affect the network performance. The simplest way of performing a broadcast is v ia flooding. In flooding, each node transmit the message once. This can cause a huge amount of redundant transmission particularly in dense networks. Unfortunately, it is not possible, in general, to remove al l redundant transmissions as the problem of minimizing the total number of required transmissions is N P - H a r d when the network is modeled using a unit disk graph. Many broadcast algorithm have been proposed in the liter- ature to reduce the number of redundant transmissions. Among the existing methods, localized broadcast algorithms are more attractive as they can cope with the network topology changes. In Chapters 2 and 3, we propose two efficient localized broadcast algorithms. The first proposed algorithm, pre- sented in Chapter 2, is an improvement over Liu 's algorithm [10] which is one of the best broadcast algorithms in its category. In the same chapter, we propose another broadcast algorithm with the objective of reducing the total number of transmissions. We demonstrate that the second proposed algorithm is very successful in achieving this objective for the case when the nodes are randomly distributed. However, we show that, similar to many existing algorithms, the proposed algorithm cannot guarantee a good bound on the total number of transmissions in the worst case. In Chapter 3, we prove that many existing broadcasting algorithms are not able to guarantee both full delivery and a good bound on the total number of transmissions. Nevertheless, we extend our second proposed algorithm and prove that it can achieve both full delivery and a constant approximation ratio to the minimum number of required transmissions. We also propose some techniques to reduce bandwidth and computational overhead of the algorithm. Moreover, we relax several system model assumptions or replace them wi th more practical ones. Chapters 4 and 5 deal with the security of ad hoc networks. In Chapter 4, we analyze the effect of the wormhole attack in shortest-path routing proto- cols w i th the objective of drawing a more precise picture of the attack's pos- sible damage. We show that two malicious nodes can control/disrupt a large percentage of the communications in the network if they place the wormhole strategically. We also consider and analyze the case where more than two malicious nodes are involved in the wormhole attack. We then propose a timing-based countermeasure and show that it does not have the shortcom- ings of the existing timing-based solutions such as the need for having tightly synchronized clocks, predicting predicting the sending time and computing signature while having to timestamp the message with its transmission time. In Chapter 5, we introduce two compression schemes that can be used to reduce the memory and bandwidth requirements in storing and transmitting the elliptic curve points. In practice, single point compression scheme may be employed to reduce the memory/bandwidth requirement. However, sin- gle point compression, patented by Certicom Corporation, requires a square root operation which is a computationally expensive operations in some fi- nite fields. In contrast to single point compression scheme, decompression of our schemes does not require any square root operation. Therefore, our schemes can be used, rather than single point compression scheme, when square root operation is computationally expensive. In the same chapter, we also introduce a new approach to reduce the computational overhead of the elliptic curve cryptography at the cost of slightly increasing the bandwidth overhead. This approach can be used to speed up elliptic curve cryptography in any devices, particularly those wi th constrained computational power or servers overloaded with elliptic curve encryption or key agreement requests. Finally , we conclude this work in Chapter 6. Bibliography 1] Y . C. H u , A . Perrig, and D . B . Johnson, "Rushing attacks and defense in wireless ad hoc network routing protocols," In Proc. of ACM Workshop on Wireless Security (WiSe), pp. 30-40, 2003. - — - , "Packet leashes: A defense against wormhole attacks in wireless ad hoc networks," In Proc. of IEEE INFOCOM, 2003. 3] D . Agrawal and Q. Zeng, Introduction to Wireless and Mobile Systems. Brooks /Cole Publishing, 2002. 4] C. Perkins, " A d hoc on demand distance vector ( A O D V ) routing (internet-draft)," 1997, internet Draft, draft-ietf-manet-aodv-OO.txt. [5] D . Johnson and D. Mal tz , "Dynamic source routing in ad hoc wireless networks," in Mobile Computing, Imielinski and K o r t h , Eds. Kluwer Academic Pubhshers, 1996. 6] S. Capkun, L . Buttyan, and J . P. Hubaux, " S E C T O R : Secure tracking of node encounters in multi-hop wireless networks," In Proc. of the first ACM workshop on Security of ad hoc and sensor networks, 2003. [7] L . H u and D. Evans, "Using directional antennas to prevent wormhole attacks," In Proc. of Network and Distributed System Security Sympo- sium, 2004. [8] R. Maheshwari, J . Gao, and S. R. Das, "Detecting wormhole attacks in wireless networks using connectivity information," In Proc. of IEEE INFOCOM, 2007. 9] N . Kobl i tz , "Elhpt ic curve cryptosystems," Math. Comp., vol. 48, pp. 203-209, 1987. [10] H . L i u , P. Wan , X . J ia , X . L i u , and F . Yao, "Efficient flooding scheme based on 1-hop information in mobile ad hoc networks," In Proc. of IEEE INFOCOM, 2006. Chapter 2 Efficient Broadcasting in Wireless A d Hoc Networks 2.1 Introduction Broadcasting is a fundamental communication operation, in which one node sends a message to a l l other nodes in the network. Broadcasting is widely used as a basic mechanism in many ad hoc network protocols. For exam- ple, ad hoc on-demand routing protocols, such as A O D V [11] and D S R [12], typically use broadcasting in their route discovery phase. Broadcasting is also used for topology updates, network maintenance or simply for sending a control or warning message. The simplest broadcast algorithm is flooding, in which every node broadcasts the message when it receives it for the first time. Using flooding, each node receives the message from al l its neighbors in a collision-free network. Therefore, the broadcast redundancy significantly increases as the average number of neighbors increases. High broadcast re- dundancy can result in high power and bandwidth consumption in the net- work. Moreover, it increases packet collisions, which can lead to additional transmissions. This can cause severe network congestion or significant per- formance degradation, a phenomenon called the broadcast storm problem 13]. Consequently, it is crucial to design efficient broadcast algorithms to reduce the number of required transmissions in the network. A set of nodes is called a Dominating Set (DS) if any node in the network either belongs to the set or is a 1-hop neighbor of a node in the set. The set of broadcasting nodes forms a Connected Dominating Set (CDS) . Therefore, the min imum number of required broadcasts is not less than the size of the min imum C D S . Unfortunately, finding the minimum C D S is N P - h a r d , even for the unit disk graphs [14, 15]. However, there are some distributed A version of this chapter has been accepted for publication. M . Khabbazian and V . K . Bhargava, Efficient Broadcasting in Mobile A d Hoc Networks, IEEE Transactions on Mobile Computing^ 2008. algorithms to find a minimum C D S with even constant approximations [16, 17]. These algorithms can be employed to find a small-sized C D S that can be used as a virtual backbone for broadcasting in ad hoc networks. However, this approach is not efficient in networks with frequent topology changes, as maintaining a C D S is often costly [18 . The main objective of efficient broadcast algorithms is to reduce the num- ber of transmissions while keeping the bandwidth and computational over- head as low as possible. One approach to classify broadcast algorithms is based on the neighbor information they use. Some broadcast algorithms such as flooding and probabilistic broadcast algorithms [19, 20] do not rely on neighborhood knowledge. These algorithms cannot typically guarantee 100% delivery and/or eflPectively reduce the number of transmissions. More- over, to decide whether or not to broadcast, they may use a threshold (such as probability of broadcast) which may not be easy to find for different net- work situations. In the second category, broadcast algorithms require to have 2-hop or more neighbor information. The broadcast algorithms in this cate- gory can reduce the number of transmissions in the network and guarantee 100% delivery [21, 22, 23]. However, they may induce high overhead in highly dynamic networks as they need to maintain 2-hop network connectivity. In this chapter, we propose two broadcast algorithms based on 1-hop neighbor information. The first proposed algorithm is a neighbor-designating (or sender-based) algorithm. In neighbor-designating algorithms, the broad- casting nodes select a subset of their neighbors to forward the message. We compare our proposed broadcast algorithm to one of the best neighbor- designating broadcast algorithms that use 1-hop information [18]. In [18], L i u et al. proposed a broadcast algorithm that reduces the number of trans- missions and achieves local optimality by selecting the minimum number of forwarding nodes with minimum time complexity O ( n l o g n ) , where n is the number of neighbors. We show that this optimality only holds for a subclass of neighbor-designating broadcast algorithms employing 1-hop i n - formation, and prove that our proposed neighbor-designating algorithm can achieve 100% dehvery with time complexity 0 ( n ) . Moreover, Liu 's algo- r i thm selects n forwarding nodes in the worst case, while our proposed a l - gorithm selects 11 nodes in the worst case. Based on our simulation results, our neighbor-designating algorithm results in fewer transmissions than does Liu 's algorithm. A l l these nice properties are achieved at the cost of slightly increase in end-to-end delay. Therefore, our first proposed algorithm is pre- ferred to L iu ' s algorithm when the value of n is typically large and it is important to bound the packet size. We also propose a self-pruning (also called receiver-based) broadcast algo- r i thm in this chapter. In self-pruning algorithms, the receiver decides whether or not to broadcast the message. Our proposed self-pruning algorithm is a novel broadcast algorithm that can significantly reduce the number of trans- missions in the network. We show that using our proposed self-pruning algorithm, two close neighbors are not likely to broadcast the same message. In other words, we prove that the probability of broadcast for a node NA exponentially decreases when the distance between NA and its broadcasting neighbor decreases, or when the density of nodes increases. Based on our experimental results, the number of broadcasts using our self-pruning algo- r i thm is less than one of the best-known approximations for the minimum number of required broadcasts. The rest of this chapter is organized as follows. In Section 2.2, we describe the system model and network assumptions. In Section 2.3, we discuss our proposed neighbor-designating broadcast algorithm and its characteristics. We propose a simple and highly efficient self-pruning broadcast algorithm in Section 2.4 and prove an interesting property of the algorithm. In Section 2.5, we verify the theoretical results using simulation and compare the number of forwarding nodes of our proposed broadcast algorithms wi th that of one of the best existing broadcast algorithms and an approximated lower bound of opt imal solution. Finally , we provide a summary in Section 2.6. 2.2 System Model Our system model is very similar to that used by L i u et al. [18]. We assume that a l l nodes are located in a 2-D plane and have a transmission range of R. Therefore, the topology of the network can be represented by a unit disk graph. We assume that the network is connected. Two nodes are considered neighbors if they are in transmission range of each other. We suppose that each node knows its location v ia a localization technique such as Global Positioning System (GPS) or the lightweight techniques summarized in [24]. Each node periodically broadcasts a very short Hello message, which includes its id and position. Thus, each node gets the position of its neighbors as well. In the Med ium Access Control ( M A C ) layer, we assume that scheduling is done according to the p-persistent C S M A / C A protocol, which I E E E 802.11 is based on in the broadcast mode. In the p-persistent C S M A / C A protocol. when a node has a message to transmit, it initiates a defer timer by a random number and starts hstening to the channel. If the channel is busy, it continues to listen unti l the channel becomes idle. When the channel is idle, it starts decrementing the defer timer at the end of each time unit. The message is broadcast when the timer expires. 2.3 A n Efficient Neighbor-Designating Broadcast Algorithm 2.3.1 Algorithm Structure Our first proposed broadcast algorithm is a neighbor-designating algorithm, i.e., each sender selects a subset of nodes to forward the message. Each message can be identified by its source id and a sequence number incremented for each message at the source node. Algor i thm 2.1 is a general neighbor- designating broadcast algorithm and indicates the structure of our proposed neighbor-designating broadcast algorithm. Upon expiration of the timer, the algorithm requests the M A C layer to schedule a broadcast. The message scheduled in the M A C layer is buffered and then broadcast wi th a probability p. This adds another delay (i.e., the M A C layer delay) in broadcasting the message. The M A C layer delay in I E E E 802.11 is a function of several factors including the network traffic. Note that there is a chance that a node changes its decision (regarding the selected nodes or regarding whether to broadcast) during the M A C layer delay due to receiving other copies of the message. This chance is not negligible when the delay in the M A C layer is comparable to the average value of the timer set in the broadcast algorithm. As stated in [25], one solution to this problem is a cross-layer design in which the network layer is given the ability to modify or remove packets that are present in the M A C layer queue. This solution allows the broadcast algorithms to perform close to their ideal performance even for very small average timer values [25 . In Chapters 2 and 3, we assume that either the M A C layer delay is negligible compared to the average delay set by the algorithm, or the network layer (hence the algorithm) is able to modify or remove packets buffered in the M A C layer queue. The neighbor-designating broadcast algorithms can be divided into two subclasses. In the first subclass, each node decides whether or not to broad- cast solely based on the first received message and drops the rest of the same messages that it receives later. Liu 's algorithm falls in this subclass. In Liu 's algorithm, each node selects the smallest subset of its 1-hop neighbors with the maximum coverage area, where the coverage area of a set of nodes is the union of their transmission coverage. Clearly, i f the selected neigh- bors broadcast the packet the transmission of non-selected neighbors would be redundant, hence they are not required to broadcast the packet. L i u et al. proved that their selection algorithm has the optimal time complexity O ( n l o g n ) . In the second subclass of neighbor-designating broadcast algorithms, each node can decide whether or not to broadcast after each message reception. However, i f a node broadcasts a message, it wi l l drop the rest of the same messages that it receives in future. Therefore, each message is broadcast at most once by a node using the broadcast algorithms in both subclasses. Our first proposed broadcast algorithm falls in this subclass of neighbor- designating broadcast algorithms. We show that the proposed algorithm can reduce both the computational time complexity of selecting the forwarding nodes and the maximum number of selected nodes in the worst case. A lgor i thm 2.1 shows the basic structure of our proposed neighbor-designating broadcast algorithm. As shown in Algor i thm 2.1, each node schedules a broadcast for a received message if the node is selected by the sender and if it has not broadcast the same message before. Clearly, each message is broadcast at most once by a node, which is similar to L iu ' s algorithm. How- ever, in Liu ' s algorithm, each node may only schedule a broadcast when it receives a message for the first time. In contrast, in Algor i thm 2.1, a broad- cast schedule can be set at any time. For example, a message can be dropped after the first reception but scheduled for broadcast the second time. Clearly, the main design issue in Algor i thm 2.1 is how to select the forwarding nodes. 2.3.2 Forwarding-Node Selection Algorithm Let us consider point A as the node A^^ and a circle CA,R centered at A with a radius R as the transmission range of NA- We use AB to denote the distance between two points A and B. Before delving into the algorithm description and proofs, we need to define the following terms: Definition 2.1 (Bulged Slice). As illustrated in Figure 2.1, we define a bulged slice around A as the intersection area of three circles with radius R and centers A, M and N, where AM = R, 'AN = R, MN = R. Note that Algorithm 2.1 A general neighbor-designating algorithm 1: Extract the required information from the received message M 2: if M has been broadcast before or does not contain node's id then 3: drop the message 4: else 5: set a defer timer 6: end if 7: When defer timer expires 8: Select a subset of neighbors to forward the message 9: At tach the list of forwarding node to the message 10: Schedule a broadcast in any bulged slice AMN we have /.MAN = |. Definition 2.2 (Right/Left Bulged Slice). As shown in Figure 2.2, let A and B be two points such that 0 < AB ^ R, and AMN be a bulged slice around A. Suppose that the point B is on one of the arcs AM or AN of the bulged slice AMN. In this case, AMN is called the right bulged slice of B around A if it contains the | clockwise rotation of point B around A and is called its left bulged slice around A, otherwise. Definition 2.3 (Bulged Angle). Let Bx and 62 be two bulged slices around A. The bulged angle /.A{I3I,B2) is defined to be equal to0^a<2nifB2 is a a anti-clockwise rotation of Bi around A. Definition 2.4 (B-coverage Set). A subset of neighbors of N^ is called a B-coverage set of NA if any non-empty bulged slice around A contains at least one node from the set. A bulged slice is empty if there is no node inside it. Definition 2.5 (Slice-Based Selection Algorithm). A forwarding-node selection algorithm is called a slice-based selection algorithm (or slice-based algorithm) if for any node NA, it selects a B-coverage set of it. Figure 2.1: A bulged slice around A. Figure 2.2: Left bulged slice of B and right bulged slice of C around A. A node can have several different B-coverage sets. Therefore, there are more than one slice-based selection algorithms. For example, a tr iv ia l slice-based selection algorithm would be one that selects al l of the neighbors as the B-coverage set. Clearly, this algorithm wi l l result in flooding if it is used as the forwarding-node selection scheme in Algor i thm 2.1. In this section, we first show that Algor i thm 2.1 can achieve 100% dehvery if it uses any slice-based algorithm to select the forwarding nodes. We then present an efficient sUce-based algorithm that selects 11 nodes in the worst case and has computational complexity 0 ( n ) , where n is the number of neighbors. Lemma 2.1. For any two points Pi and P2 inside a bulged slice, we have P^2^R- Proof. As shown in Figure 2.3, the hne passing through P i and P2 intersects the bulged slice AMN at P{ and P^. Clearly, P1P2 ^ P{P^. Therefore, to prove the lemma it is sufficient to show that P1P2 ^ R- This is easy to show if both P[ and P2 are on the same arc of the bulged slice. Thus, without loss of generality, we can assume that P{ and P2 are on the arcs AM and AN, respectively. Let us consider the perpendicular bisector of the line segment P[M (Line L). Line L passes through N because NM = NP{ = R. Since the point Pg is on the arc AN, the line segment M P g wi l l cross the hne L at a point Q. Using triangle inequality, we have P[F^ ^ {QF2 + Wi) = [QH + QM) = P2M = R. Note that Q is on the line L, hence QP{ = QM. • Figure 2.3: Upper bound on the distance between nodes inside a bulged slice. Consider two points A and B such that R < AB ^ 2 P . As shown in Figure 2.4, the line segment AB intersects the circle CA,R at point Q. Let AQM and AQN be the left and right bulged slices of Q around A , respectively. The following lemmas hold: L e m m a 2.2. A point P is inside the bulged slice AQM or AQN if AP ^ R and BP ^R. Proof. It is easy to show that for any triangle AABC, AM ^ AB or AM ^ AC, where M is a point on the line segment BC. Consequently, in the triangle APAB (shown in Figure 2.4) we have PQ^AP^R or PQ^BP^R. Therefore, PQ ^ R. Thus based on the bulged slice definition, the point P is inside the bulged slice AQM or AQN. • Figure 2.4: Illustration of Lemmas 2.2 and 2.3. Lemma 2.3. For any point P ^ A inside the bulged slice AQM or AQN, we have 'BP <BÂ. Proof. Using triangle inequality we get 'BP ^'BQ + 'QP + R = BA. The equality holds only when BP = BQ + QP and QP = R, or simply when P = A. • Theorem 2.1. In a collision-free network, Algorithm 2.1 can achieve 100% delivery if it uses a slice-based selection algorithm to select the forwarding nodes. Proof. Using Algor i thm 2.1, each node broadcasts the message at most once. Therefore, broadcasting wil l eventually terminate. By contradiction, sup- pose there is at least one node that has not received the message after the broadcasting termination. Let us consider the following set: A = {{Nx, A y , Nz)\Nx has broadcast the message, Nz has not received the message and NY is the neighbor of both Nx and Nz}- Suppose Ns is the node that initiated broadcasting and NT is a node that has not received the message. The network is connected, thus there is a path between Ns and Nr. Clearly, we can find two neighbor nodes NQ, NB along the path from NT to A^^ such that Nc has not received the message, while NB has received it . Suppose that NB has received the message from NA- Consequently, {NA,NB, NC) e A , thus A 0. A s a result, 3(A^^/, NB', NC) e A s.t. y{Nx, Ny, Nz) e A : A'C ^ XZ. (2.1) Obviously, NA' and Nc are not neighbors, because Nc has not received the message. Thus, A'C > R. Using Lemma 2.2, B' is inside the bulged sUce A'PiP2 or A'PiPs, where P i is the intersection of line segment A'C and the circle CA',R and A'PxP2 and A'PiP^ axe the left and the right bulged shces of Pi around A', respectively. Without loss of generality, assume that B' is inside the bulged shce A'PiP2. Since NA' has at least one neighbor (i.e., NB') in this shce, there must be a selected node N^ in the shce that has forwarded the message. Using Lemma 2.1, we get B'D ^ R; hence, nodes No and NB' are neighbors. Therefore, (No, N B ' , Nc) e A . However, this contradicts (2.1) because using Lemma 2.3 we have DC < A'C. • Algor i thm 2.2 shows our proposed slice-based selection algorithm. Sui> pose that node A^^ uses the proposed algorithm to select the forwarding nodes from its neighbors. Let us assume that NA stores all of its neighbors' ids and locations in an array of length n , where n is the number of neighbors. The algorithm selects the first node A^ ĵ randomly from the array. The first node can also be selected deterministically by, for example, selecting the node that is the farthest away from A^^. Let JCBA{P) and TZBA{P) denote the left bulged slice and right bulged slice of P around A, respectively. Suppose that Nsi is the last node selected by the algorithm. To select the next node, the algorithm iterates through the array and selects the node Ns^^•^ such that it is inside the slice CBA{Si), /.A{CBA{Si),CBA{Si+i)) # 0 and ViVfl inside CBA{Si) : LA{CBA{Si),CBA{B)) ^ /A{CBA{Si),CBA{Si+i))- If there is no such node, the algorithm selects Nsi^^ such that VA^B inside CA,R '• /LA{CBA{Si),nBA{Si+i)) ^ LA{CBA{Si),nBA{B)). (2.2) (2.3) The algorithm terminates by selecting the last node Ns^ if Ns^ is inside CBA{SI) or Ns, is inside £ 5 ^ ( 5 ^ ) or Sm+i = Sy. Algorithm 2.2 A slice-based selection algorithm Input: ListA[l... n]: List of al l neighbors of A''^ Output : A B-coverage set of A^^: {Ns^} ind *— 1 z <-0 repeat ang-max •<— 0 ang-min <— 27r Nsi *— ListA[ind] chk false for j = 1; J ^ length(ListA) ; J + + do if ListA[j] is in CBA{Si) then if /-Aij^l^AiSi), CBA{ListA[j])) > angjmax then chk true indjmax <— j angjmax *— /-A{J^I^A{Si), CBA{ListA{3\)) end if else if /-A{CBA{Si),TZBA{ListA[3])) < angjmin then ind-min <— j ang-min *- Z.AiCBAiSi),nBAiListA[j])) end if end if end for if chk then ind <— indjmax else ind *— ind-min end if until Si is in CBA{ListA[ind]) O R ListA[ind] is in CBA{SI) if # 1 then end if Lemma 2.4. Suppose the proposed algorithm selects m nodes { , A ^ ^ ^ , N s ^ } . For any 1 ^ i < m — 2, we have Proof. Based on (2.2), (2.3) and the algorithm termination condition, we can show that AA{CBA{S^),CBAiSi+2)) > ^A{CBA{Si),LBA{Si+x)) for any 1 ^ i < m - 2. B y contradiction, assume that AA{CBA{S,),CBA{S,^2))^\. Therefore, Si+2 is inside £S^(S'i). Thus, using (2.2) we have Z.A{CBA{Si),CBA{Si+2)) ^ ^AiCBAiSi),CBA{Si+i)) which is a contradiction. • Theorem 2.2. The proposed slice-based selection algorithm will select at most 11 nodes. Proof. B y contradiction, assume that the algorithm selects more than 11 nodes. Therefore, 5 i i is not in CBA{SI). Using Lemma 2.4, we get 5 AA{CBA{S,),CBA{Sn)) = 2 ( ^A( / :^A ( 5 2 , - I ) , / : f i A ( 5 2 i + i ) ) ) > 5 x ^ . i=i Therefore, LA{CBA[Sn), CBA{SI)) < (27r - 5 X f ) = f . Consequently, is inside CBA{Sn), thus the proposed shce-based algorithm wi l l terminate after selecting ^ n . • The above theorem gives an upper bound on the number of nodes selected by the proposed selection algorithm. In Section 2.5, using simulation we show that the average number of selected nodes (when the nodes are distributed uniformly) is less than 6. Theorem 2.3. Time complexity of the proposed slice-based selection algo- rithm is 0{n), where n is the number of neighbors. Proof The algorithm selects the first node in 0(1) . To select each of the other nodes, the algorithm performs 0{n) operations by checking all the neighbors in the array. Therefore, the complexity of the algorithm is 0{m x n) , where m is the number of selected nodes. Using Theorem (2.2) we have m ^ 11, thus the time complexity of algorithm is 0 ( n ) . • 2.3.3 Reducing the Number of Forwarding Nodes In the sender-based broadcasting algorithms, each broadcasting node at- taches a list of its selected forwarding nodes to the message before broad- casting it . This procedure wi l l increase the bandwidth and power required to broadcast the message. As shown earher, our proposed shce-based selection algorithm reduces the number of selected forwarding nodes to 11 in the worst case. In this section, we show how to further reduce the number of selected nodes. Recall that the proposed slice-base algorithm selects a subset of A^^'s neighbors such that there is at least one selected node in any non-empty bulged slice around A. Suppose NA extracts the list of the forwarding nodes from each message it receives. Let CA be a subset of NA''S neighbors that has broadcast the message or been selected by other nodes to forward it . Since al l of the selected forwarding nodes are required to broadcast the message, it is sufficient for A^^ to find a subset of its neighbors SA such that any non-empty bulged slice around A contains at least one node from SA'O CA- Algor i thm 2.2 can be simply extended to achieve this in 0(n). Note that the extended algorithm can start with a node from CA and select any node in CA as soon as it appears in the left bulged shce of the previously selected node. Finally , the extended algorithm removes al l of the nodes in CA horn the set of selected nodes. 2.3.4 Maximizing the Minimum Node Weight of B-coverage Set Suppose node NA assigns a weight to each of its neighbors. The weight can represent the neighbor's battery lifetime, its distance to NA, the average delay of the node, the level of trust or a combination of them. In some scenarios, we may desire to find a B-coverage set such that its minimum node weight is maximum or its maximum node weight is minimum among that of al l B-coverage sets. For example, assume that the weight of each node represents its battery lifetime in a wireless network. It may be desirable to select the nodes with a higher battery lifetime to forward the message in order to keep the nodes with a lower battery hfetime alive. Algor i thm 2.3 shows how to find a B-coverage set such that its minimum node weight is maximum among that of all B-coverage sets. A similar approach can be used to find a B-coverage set such that its maximum node weight is minimum. Algori thm 2.3 Maximiz ing the minimum node weight Input: ListA[l • • .n]: List of al l neighbors of A^^ Output : A B-coverage set of NA wi th highest minimum node weight 1: SListA sort{ListA) {Sort the neighbor nodes by their weights} {SList[i] ^ SList[j] ^i^j] 2: H^n; T^l; m ^ [f ] 3: St Algorithm^2.2{SList[l]) 4: if St is a B-coverage set for A^^ then 5: return SLis t [ l 6: end if 7: while H>T+ldo 8: St <— AlgorithmJ2.2(SList[l.. .m]) {Pass m nodes with the highest weights to Algor i thm 2.2 as the input} if St is a B-coverage set for NA then H else T m 9 10 11 12 13 14 15 16 17 end if end while return ( A l g o r i t h m J 2 . 2 ( 5 L i s i [ l . . . H])) Algor i thm 2.3 first sorts the nodes by their weights in decreasing order. Then, in each step it passes m nodes with the highest weights to Algo- r i thm 2.2 as input and gets a set of (at most 11) nodes as output, where 1 ^ m ^ n is an integer init ial ly set to \^]. If the output set is a B-coverage set, A lgor i thm 2.3 sets H to m and decreases m to f ^ ^ ] , where T and H are variables init ial ly set to 1 and n , respectively. Otherwise, it sets T to m and increases m to f^^^] . After a finite number of steps we get H = T + 1. Algor i thm 2.3 then returns the output of A l g o r i t h m _ 2 . 2 ( 5 L i s t [ l . . . H]). Corollary 2.1. Algorithm 2.3 will select at most 11 nodes. Proof. The proof is clear, as Algor i thm 2.3 returns an output of Algor i thm 2.2 (Line 17). • Theorem 2.4. Time complexity of Algorithm 2.3 is 0 ( n logn) . Proof. A lgor i thm 2.3 requires O ( n l o g n ) operations to sort the fist of neigh- bors ListA[l.. .n]. The computational complexity of Algor i thm 2.2 is 0 ( n ) . Therefore, Algor i thm 2.3 performs 0 (n ) operations in each iteration of the while loop. The while loop terminates after O(logn) iterations because it uses a binary search approach to find the minimum value of H. Consequently, the order of Algor i thm 2.3 is 0 ( n l o g n -I- l o g n x n). • Theorem 2.5. Minimum weight of nodes of the B-coverage set selected by Algorithm 2.3 is maximum among that of all B-coverage sets. Proof. Suppose that Stmin is a B-coverage set such that the minimum weight of nodes in Stmin is greater than or equal to that of other B-coverage sets. Let Nx s Stjnin be the node with the minimum weight in Stmin- Assume Ny\ has K neighbors with weights greater than or equal to the weight of Nx- Therefore, the output of Algorithm_2.2(5Lzsf [ 1 . . . K]) is a B-coverage set. Note that Algor i thm 2.3 finds the minimum H such that the output of A l g o r i t h m _ 2 . 2 ( S ' L i s t [ l . . . / / ] ) is a B-coverage set for NA- Therefore, H and thus the minimum weight of nodes of the B-coverage set selected by Algor i thm 2.3 is greater than or equal to the weight of Nx- • 2.3.5 Similarity With A Topology Control Algorithm In [26] and [27], the authors proposed a cone-based topology control algo- r i thm, where each node makes local decisions about its transmission power. The objective of the algorithm is to minimize the transmission power of each node without violating the network connectivity. In order to do that, each node NA transmits with the minimum power Pa, such that in every non- empty cone of degree a around NA, there is some node that NA can reach with power P^. A cone is non-empty, if there is at least a node in the cone that NA can reach using its maximum power. For ct = y , they proved that the network remains connected if the cone-based algorithm is employed. Suppose that we use cones instead of bulged slices in the proposed forwarding- node selection algorithm. Therefore, the algorithm wi l l select the forwarding node set such that any non-empty cone of degree a around NA contains at least one node from the forwarding node set. Surprisingly, this algorithm wi l l not guarantee full delivery. Figure 2.5 shows a counterexample for the case where a = Figure 2.6 shows that even for a = |, full dehvery cannot be guaranteed. In both Figures 2.5 and 2.6, the node A^i initiates broadcasting and selects only NB and Nc to forward the message. Suppose that No is close enough to the point M such that it is the only node that can reach A''^;. In this case. NE w i l l not receive the message because No is not selected by neither NB nor A^^ to forward the message. Note that the cone-based and the forwarding-node selection algorithms use different approaches. In the cone-based algorithm, a node NA increases its power from zero unti l there is a node in each non-empty cone around NA- However, in the forwarding-node selection algorithm, a node A^^ selects some nodes (the forwarding nodes) unti l there is a selected node in each non-empty bulged slice around NA-  2.4 A Highly Efficient Self-Pruning broadcast algorithm In this section, we propose a novel self-pruning broadcast algorithm that can significantly reduce redundant broadcasts in the network. A s mentioned ear- lier, i n self-pruning broadcast algorithms the receiver of the message decides whether or not to broadcast the message. Therefore, a potential advantage of self-pruning broadcast algorithms over neighbor-designating ones is that they do not increase the size of the message by adding a list of forwarding nodes. 2.4.1 Algorithm Structure Algor i thm 2.4 shows a general approach used in several self-pruning broad- cast algorithms [23, 28]. Our proposed self-pruning broadcast algorithm em- ploys this approach. Clearly, the main design issue of Algor i thm 2.4 is to determine whether or not to broadcast a received message. A tr iv ia l algo- r i thm is to refrain broadcasting if and only if al l the neighbors have received the message during the defer period. Although this algorithm is simple to implement, it has l imited effect in reducing the number of redundant broad- casts. Suppose NA'S defer time expires at ^Q . Using the above strategy, node NA w i l l broadcast if some of its neighbors (at least one) have not re- ceived the message by ô- However, this broadcast is redundant if al l such neighbors receive the message from other nodes after time to. This scenario typically occurs when to is small compared to the maximum defer time. In the next section, we introduce a responsibility-based scheme (RBS) that can significantly reduce the redundant broadcasts. Algori thm 2.4 A general self-pruning algorithm 1: Extract the required information from the received message M 2: if M has been received before then 3: drop the message 4: else 5: set a defer timer 6: end if 7: W h e n defer timer expires 8: decide whether or not to schedule a broadcast 2.4.2 A Responsibility-Based Scheme Algor i thm 2.5 shows the proposed Responsibility-Based Scheme (RBS) . The main idea of A lgor i thm 2.5 is that a node avoids broadcasting if it is not responsible for any of its neighbors. A node NA is not responsible for a neighbor A^B if NB has received the message or if there is another neighbor Nc such that Nc has received the message and NB is closer to A^^ than it is to A^i - Suppose NA stores ids of al l its neighbors that have broadcast the message during the defer period. When executed by a node A ^ i , A lgor i thm 2.5 first uses this information to determine which neighbors have not received the message (Lines 1-9 of A lgor i thm 2.5). It then returns false if and only if it finds a neighbor NB that has not received the message and AB^BC for any NA'S neighbor Nc that has received the message. The output of R B S determines whether or not the broadcast is redundant. Algori thm 2.5 A responsibility-based scheme (RBS) Input: List A'. List of a l l neighbors of A'^, and Lists'- List of broadcasting neighbors Output : true or false Liste •<— List A for i = l\i ^ length(l /zsic) ; i++ do for J = 1; j ^ length(ListB) ; do if dist(l/zsic[î], ListB\jy) ^ R then removeElement(Lzstc[î], Liste) break end if end for end for Listo <— List A — Liste for i = l\i ^ length(Lzstc) ; ^++ do check •«— true for j = 1; j ^ length(Lzsi£)); j++ do if dist{Listc[i], Listoij]) ^ dist(Lisic[«], A^^) then check <— /a / se break end if end for if check then return (false) end if end for return (true) Example 2.1. As shown in Figure 2.7, NA has five neighbors. Suppose that NA has received a message from Np. Note that NA has the position of all its neighbors. Therefore, it can easily find that NE and ND have received the message but NB and Nc have not. As shown in Figure 2.7, NA is not required to broadcast because BE <RÂ and 'CD <CJ. Figure 2.7: A n example of an R B S decision. Example 2.2. Figure 2.8 shows an example of using the proposed self- pruning algorithm in a network with 33 nodes. In this example, the node S initiates the broadcast. It is easy to see that the nodes Ax .. .A-j are not re- quired to broadcast based on the responsibility condition. Therefore, they can immediately drop the packet after they receive it from S. Other neighbors of S initiate a defer timer with a random number. Thus, the next broadcasting node is random (it is Fi in this example). Note that after Fi's transmis- sion, some other nodes, which were previously set a defer timer, may drop the packet. For example, node Bi would be no longer responsible for any of its neighbors after Fx's transmission. At last, as shown in Figure 2.8, only 7 nodes (represented by stars) will broadcast the packet. Figure 2.8: A n instance of using the proposed broadcast algorithm. Theorem 2.6. In a collision-free network, Algorithm 2.4 can achieve 100% delivery if it uses the proposed responsibility-based scheme to determine whether or not to broadcast. Proof. Using Algor i thm 2.4, each node broadcasts a message at most once. Therefore, broadcasting wi l l eventually terminate. B y contradiction, sup- pose there is at least one node that has not received the message after the broadcasting termination. Let us consider the set A = {iNx,NY)\Nx and NY are neighbors, Nx has received the message and Ny has not received the message} Suppose Ns is the node that initiated broadcasting and NT is a node that has not received the message. The network is connected, thus there is a path between Ns and NT- Clearly, we can find two neighbor nodes NB and A^^ along the path from A ^ to Ng such that NB has not received the message, while NA has. Consequently, {NA, NB) e A , thus A # 0 . As a result, 3{NA',NB')eA s.t. \f{Nx, Ny) e A : WW ^XZ. (2.4) Clearly, NA' has not broadcast since NB' has not received the message. There- fore^ there must be a node Nc> such that Nc has received the message and C'B' < A'B' ^ R. This result contradicts to (2.4), since {Nc, NB') 6 A . • Theorem 2.7. Time complexity of the proposed RBS is 0{v?), where n is the number of neighbors. Proof. A lgor i thm 2.5 consists of two parts. In the first part (Lines 1-9), the algorithm generates a list of neighbors that have not received the message {Liste)- Clearly, the time complexity of this part is 0{kn), where 1 <k is the number of broadcasting neighbors. In the second part, the algorithm checks whether there is a node NB such that NB has not received the message and BA ^ BC for any neighbor Ne e Listn- The time complexity of this part is 0{lm), where 0 ^ / ^ n is the number of neighbors that have not received the message and 1 ^ m ^ n is the number of neighbors that have received it . Therefore, the complexity of the algorithm is 0{lm + kn). • 2.4.3 A Property of the Proposed RBS In the simulation section (Section 2.5), we show that the proposed R B S can significantly reduce the number of transmissions in the network. In particu- lar, our simulation shows that using R B S , the average number of broadcasts is less than one of the best-known approximations for the minimum number of required broadcasts. To justify this, we prove a property of the proposed R B S . Assume that nodes are placed randomly inside a square area of size L x L using a homogeneous planar Poisson distribution. Therefore, nodes are independently and uniformly distributed in the area. Moreover, we have {ÔT)''e~^'^ Pr6(number of nodes in area r = k) = -—— , ki where 5 is the density of nodes [29, 30]. Suppose node NB receives the message from A^^ for the first time. For simplicity, assume that circle CA,2R is completely inside the square area. Corollary 2.2 shows that the probability that NB broadcasts the message exponentially decreases when the distance AB decreases or when the node density 6 increases. This result is further confirmed by simulation in Section 2.5. Example 2.3. Suppose R = 250m, L = 1000m andSL'^ = 300 (i.e., there are about 300 nodes in the network). Let Prb{BrdB) be the probability that NB broadcasts the message after receiving it from NA • Using Theorem 2.8 we get PrbjBrdB) ^ 1.26 xlO'^, Prh{Brd^^ 1.4 x 10"^ and PrbiBrdg) ^ 10'^ when AB = 100m, AB = 80m and AB = 60m, respectively. Let 1^1,712,.. .Ilk he k non-overlapping regions inside the network. Sup- pose that C,Ti is the event, CT^ = {The region contains at least one node}. Since the nodes are placed by homogeneous planar Poisson distribution, the events CT̂ ^ are independent [30]. Consequently, we have Prh{U.Xn.,...Xii,) = Prh{UÙPrh{C,n2)...Prh{Cn,). (2.5) Lemma 2.5 generalizes (2.5) to the case where the regions may overlap. L e m m a 2.5. Let TZi,TZ2, • • - TZk be k regions inside the network. We have PrbiCnrXn,, • • •, C7^J ^ Pr6(C7^JPr6(C7e,) • • • PrbiCn,)- Proof. The proof is by induction on the number of regions. The lemma is true if the number of regions is one (i.e., k = I). Suppose that the inequality holds for A; = d regions. We have Pfb{Cni,Cn2', • • • ) (njCiZd+i) = PfKCni-TZd+iXni-nd+t,- • •, Cna-TZd+i), (2.6) where is the complement of CTÎ  and Ri — Rj is the collection of al l points inside Ri and outside Rj. Note that PfKCiii> C7e2) • • • ) CnjCTZi-nd+i> C7i2-na+i> • • •. Cud-'R-d+i) = ^• Thus Prb{CTz^,Cn2,..., CTJJ ^ Pr6(C7ei-7e,+i, C7̂ 2-7̂ d+i> • • • > C7^d-7^d+l)• (2-7) It follows from (2.6) and (2.7) that Prb{Cn,Xn2, • • • Xn,) ^ PrKC7^„ CT^,, • • •, C7ejC7e.,J- (2.8) We have PrKCnx, C7e„ . •. , Cn,) = PrbiCn.jPrbiCn.Xn,, • • •, CnXn,,,) + Prb{Cn,JPrb{Cn,XiZ2, • • •, CnjCn,,,)- Therefore, using (2.8) we get PrbiCn^jPrbiCn^^Cn^, Cn.lCn,^,) ^ ( l - P r 6 ( C 7 ^ , , J)Prfe(C7t„ CT^., • • •, Cn,)- Thus, using induction hypothesis we get Prb{(:Ti„Cn2,---,Cn^,Cn^^,) ^ Prb{Cn,jPrbi(:ii„Cn2,---,Cii,)^ Prb{Cn:)Prh{^n2) • • • Prb{Cn,)Prb{Cn,,x). a L e m m a 2.6. Let VA,R and VB,R he two disks with radius R and centers A and B, respectively. Suppose AB ^ R. As shown in Figure 2.9, consider a point Q such that R < QA and QB ^ R. Let T>QQ^ he a disk with radius QB. We have -KÇR - ÂBy A(I(VA,R,VB,R,VQ;QS)) where X{VA,R,'DB,R,T>QQ^) is the intersection of disks VA,R, T>B,R andDggg and A{R) is the area of region R. Proof. For any point P on the circle CA,R we have BP^AP-AB = R- AB. Therefore, as shown in Figure 2.9, the disk 2^B,(R_ÂB) inside I{T>A,R, DB,R). Consequently, we have A{I{VA,R,VB,R,VQ^QB)) ^ HnT^BXR-ÂB)^'^Q,QB))- Since QA ^ R, using triangle inequality we get QB^QA-AB^R-AB. Therefore, we have /LQBC ^ ^ and AQBD ^ - and hence ACBD ^ Therefore, A ( / ( P • Figure 2.9: Finding a lower bound for A{I(VA,R,'DB,R,'DQQ^)). Theorem 2.8. Suppose d ^ R is the distance between two nodes NA and NB- We have Prb{Brd) ^ 1 - e-^'"' , where Prb{Brd) is the probability that NB broadcasts the message after re- ceiving it from NA, and -y = A{VB,R) - A{I{VA,R,'DB,R)) is the area of the hatched crescent shown in Figure 2.9. Proof. Node NB is not required to broadcast if and only if C * : V T V Q 6 A : 3Np inside I{VA,R, VB,R, VQ^QB), where A = {Nx\ÂX > RandBX ^ R}. Note that the nodes' positions have Poisson distribution. Therefore, using Lemma 2.6 we get Prb{3Np inside I{VA,R,VB,R,VQ^QB)) = Thus 00 Prb{Brd) = 1 - Prh{C) = 1 - 2 P^K\^\ = k)Prb{Ç.*\{\k\ = k)). fe=0 where |A| is the cardinality of the set A . Therefore, using (2.9) and Lemma 2.5 we get Prb{Brd) ^ 1 - 2 (1 - e - ^ " ^ ) * ^ = 1 - e " ^ ^ ^ " ' ^ , fc=0 where 7 is the area of the hatched crescent in Figure 2.9 (collection of al l points Q,QA> R and QB ^ R) 7 = A(VB,R) - A{X{VA,R,VB,R)) = R^-n - 2 a r c c o s ( ^ ) ) + d^ i î^ _ (^)2. • Corollary 2.2. Using Theorem 2.8, we get PrbiBrd) ^ S^e-'""^, Proof, consider the function f{x) = 3: + e-^ - L It is easy to show that f{x) has a global minimum at a; = 0. Therefore, we have l-e-"" for any real number a;. As a result, we get • It is also possible that node NB receives the message from more than one neighbor in its defer period. In this case, the number of A^b's neighbors that have received the message increases and the number of that have not received the message decreases. Consequently, the probability that NB is required to broadcast the message further decreases compared to the case where NB receives the message from only one neighbor. In Chapter 3, we prove that R B S can guarantee that the number of forwarding nodes is within a constant factor of the optimal solution (minimum C D S ) , if it is provided with part ia l information about 2-hop neighbors. 2.5 Simulation 2.5.1 Average Number of Nodes Selected by the Proposed Sliced-Based Algorithm In Section 2.3, we proved that the proposed forwarding-node selection algo- r i thm selects 11 nodes in the worst case. In practice, the number of selected nodes is typically less than 11. To avoid the complexity of mathematical analysis, we used simulation to find the average number of selected nodes. For a given number of neighbors 1 < n 160, we randomly put n points inside a circle wi th radius R. We then ran the proposed selection algorithm and obtained the number of selected nodes. To get the average number of selected nodes, we ran simulation 10^ times for each given n. As shown in Figure 2.10, the average number of selected nodes is less than 6 and ap- proaches 5 when n increases. Note that the proposed sliced-based selection algorithm does not necessarily select a B-coverage with a minimum number of nodes. However, there is a sliced-based selection algorithm that can find a B-coverage with a minimum number of nodes in O ( n l o g n ) and can conse- quently reduce the average number of selected nodes. It is worth mentioning that Figure 9 shows the average number of selected nodes by the source node (the node that initiates the broadcasting). For the rest of broadcasting nodes, the average number of selected nodes is at least one less than that for the source node because of the optimization technique introduced in Section 2.3. 1.5 i ! 1 1 1 1 1 1 1 20 40 60 so 100 120 140 160 Number of neighbors Figure 2.10: Average number of nodes selected by the proposed shce-based algorithm. 2.5.2 Probability of Broadcast using the Proposed RBS Suppose that the proposed self-pruning algorithm is used for broadcasting in the network. Assume that node NB receives a message from N^ for the first time. It has been proven that the probability of NB broadcasting the mes- sage {Prb{BrdB)) exponentially decreases when the distance AB decreases or when the node density 5 increases. We used simulation to confirm this theoretical result. For the simulation, we considered two nodes N^ and A''^ with distance 0 < d ^ R from each other. We uniformly placed nodes with density S inside the network and checked whether or not NB was required to broadcast the message. We ran simulation 10^ times for a given 5 and R. We then estimated Prb{BrdB) by the ratio of the number of times NB was required to broadcaist over total number of runs. Figures 2.11-2.14 show the simulation results for several values of Ô, d and R. A s shown in these figures, the probability of broadcast exponentially decreases when d decreases or when 8 increases. For example, when R = 300m and 5 = 4 x 10"^, the probability of broadcast is 0.1 for d = 250m and reduces to 10"** for d = 200m. This property can justify why the proposed self-pruning algorithm can significantly reduce the number of transmissions in the network. Figure 2.15 illustrates an instance of using R B S for the case where R = 300m, 5 = A y. IQ"^ and nodes are placed in a square area of 1000 X lOOOm^. As shown in Figure 2.15, only 9 nodes (represented by stars) among 400 nodes broadcast the message. Figure 2.11: Probabil ity of broadcast for R = 300m. Figure 2.12: Probabil ity of broadcast for R = 400m. Figure 2.13: Probability of broadcast for R — 500m. Figure 2.14: Probabil ity of broadcast for R = 600m. 600 800 1000 Figure 2.15: Broadcasting nodes in a 1000 x lOOOm^ square area with 400 nodes. 2.5.3 Performance of Proposed Neighbor-Designating and Self-Pruning Algorithms The main objective of efficient broadcast algorithms is to reduce the number of transmissions. Therefore, we considered the ratio of broadcasting nodes over the total number of nodes as the metric to evaluate the performance of proposed broadcast algorithms. Using the ns-2 simulator, we evaluated this metric against two parameters: transmission range and node density. In each simulation run, we uniformly distributed N nodes in a 1000 x 1000 square area, where N = 5 x (network area). A randomly generated topology was discarded if it leaded to a disconnected network. Only one broadcasting occurred in each simulation run by a randomly selected node. Table 2.1 summarizes some of the parameters used in ns-2. As shown in the table, the tota l number of nodes, N, varies within 25 — 1000 and the transmission range varies within 50 - 300 m. A s a result, the simulation covers very sparse and very dense networks as well as the networks with large diameters. Table 2.2 shows the name and brief description of the algorithms used (in the simulation) for performance comparison. Figures 2.16 and 2.17 show the average ratio of broadcasting nodes for 100 separate runs. The performance of our proposed algorithm is compared with the performance of Liu 's algorithm [18] and the Edge Forwarding a l - gorithm [31]. Using the Edge Forwarding algorithm, each node NA divides its transmission coverage into six equal-size sectors Ap . , where 1 ^ z ^ 6. If NA receives a new broadcast from another node, say N B , it first determines the part it ion of A ^ , say Bp., in which it is located. As the basic forwarding rule, the node NA forwards the message if there exist at least one partit ion Api^ such that no other host can be found in Bp. r\Ap^. Using the basic and advanced forwarding rules proposed in [31], a node is not typically required to forward the packet unless it is close to the transmission perimeter of the broadcasting node. In [18], L i u et al. showed that the number of redundant broadcasts using their broadcast algorithm is significantly lower than that of previous notable broadcast algorithms [31, 32]. A s proved earlier, our proposed neighbor- designating algorithm has lower computational complexity and selects fewer forwarding nodes than Liu 's algorithm. The simulation results, shown in Figures 2.16 and 2.17, indicate two interesting facts. First , our proposed neighbor-designating algorithm does not require more broadcasts than Liu ' s proposed broadcast algorithm. Secondly, the number of transmissions using R B S is significantly lower than the number associated with the other imple- mented algorithms. In fact, as shown in Figures 2.16 and 2.17, this number is even less than one of the best-known approximations (ratio 8 approxi- mation) for the minimum number of required broadcasts [16]. Note that in R B S , the probability that two close nodes broadcast the same message is very low. As a result, the number of broadcasting nodes is statistically bounded in a finite region (e.g., the transmission range of a node). However, using the slice-based and Liu 's algorithm, the chance that two close nodes broadcast the same message is not negligible. For example, using Liu 's a l - gorithm, a node NA selects the smallest subset of its 1-hop neighbors wi th the maximum coverage area, where the coverage area of a set of nodes is the union of their transmission coverage. As expected, most of the nodes around the transmission boundary of A^^ wi l l be selected by A^^ since they often have contributions in the maximum coverage area of A^^'s 1-hop neighbors. Therefore, it is likely for Liu 's algorithm to select two close nodes around the transmission boundary of a node. We repeated the simulation to consider a few more scenarios. In the first scenario, we changed the node distribution from uniform to a 2-dimensional Gaussian distribution. Bo th center and variance of the Gaussian distribu- tion were randomly selected for each run. The variance was selected from the range 200-400 to avoid very dense population of nodes around the center of the distribution. A s shown in Figure 2.18, the number of broadcasting nodes decreases for al l the broadcast algorithms when a Gaussian distribution is used to distribute the nodes in the region. The simulation results indicate that the R B S algorithm sti l l performs significantly better than other broad- cast algorithms considered in this work. In the second scenario, we used uniform distribution to distribute the nodes and evaluated the impact of message-reception failure on the perfor- mance of broadcast algorithms. We considered two networks of 100 and 400 nodes. The probability of message-reception failure was assumed to be equal and independent for each node in the network. For both networks, the maximum transmission range was set to 250m. Figures 2.19 and 2.20 compare the average delivery ratio of the broadcast algorithms for different probabilities of message-reception failure. A s shown in these figures, the Edge Forwarding algorithm is the most robust broadcast algorithm against message-reception failure. This is because the impact of message loss is less when the broadcast redundancy is high. Interestingly, the robustness of the R B S algorithm significantly improves as the node density increases. The simulation results indicate that the slice-based algorithm is the least robust broadcast algorithm against message-reception failure. This is mainly due to the fact that the slice-based algorithm selects a small number of nodes (less than 6 on average) to forward the message. Therefore, when the probability of message-reception failure is high, it is very likely that most of the selected nodes fail to receive and thus, forward the message. Final ly , we simulated the broadcast algorithms in a mobile wireless set- tings. The nodes were init ial ly distributed using a uniform distribution. In the simulation, we used random walk mobility model and set the maximum velocity to lOm/s . We fixed the transmission range to 250m and varied the total number of nodes within 25 — 1000. The simulation results indicate that al l the broadcast algorithms considered in this chapter can achieve a high delivery ratio (above 95% on average) for N ^ 50, where N is the total number of nodes in the network. This is mainly because the implemented broadcast algorithms make broadcasting decisions "on-the-fly". For N = 25, the implemented algorithms failed to achieve a high delivery ratio because the network could easily get disconnected due to nodes' mobility. Clearly, broadcast algorithms cannot achieve high delivery ratio in such scenarios. It is worth mentioning that for N 50, the ratio of broadcasting nodes is almost the same as the case where there is no mobility (see Figure 2.16). Parameter Value Simulator M A C Layer Propagation Model Packet Size Bandwidth Size of Square Area Transmission Range Number of Nodes ns-2 (version 2.27) I E E E 802.11 two-ray ground 256 bytes 2 Mb/sec 1000 X lOOOm^ 50-300m 25-1000 Table 2.1: Simulation parameters Algorithm Brief Description Reference Edge Forwarding Liu ' s A l g . Ratio-8 Approx. Slice-Based A l g . R B S A l g . Nodes divide their transmission range into six equal sectors Each node selects the smallest subset of its neighbors with maximum coverage A non-localized algorithm that gives an approx. factor 8 to M C D S . It is used as a benchmark. Our proposed neighbor-designating algorithm Our proposed self-pruning algorithm [31] [10] [16] Section 2.3 Section 2.4 Table 2.2: Algorithms used in the simulation Total number of nodes Figure 2.16: Ratio of broadcasting nodes vs. total number of nodes (uniform distribution). - RBS Algorittm - Ratio-8 ApproxImiUonI -Sllc«-B.»«l Alaorithm - Uu'« AlgorKtim • Edfla Forwirdlng 100 150 200 2S0 TrammlMlon range (meter) 300 Figure 2.17: Ratio of broadcasting nodes vs. transmission range (uniform distribution). 200 - RBS Algorithm - R«tio-a Approximation - Sllce-B«Md Algorithm - Uu'» Algorithm - Edg» Forwarding 400 600 Total number of nodes 800 1000 Figure 2.18: Ratio of broadcasting nodes vs. total number of nodes (Gaussian distribution). Probability of message-reception failure Figure 2.19: Average delivery ratio vs. probability of message-reception failure (A^ = 100). Probability of message-reception failure Figure 2.20: Average delivery ratio vs. probability of message-reception failure (A^ = 400). 2.6 Summary In the first part of this chapter, we proposed a forwarding-node selection algorithm that selects at most 11 nodes in 0 ( n ) , where n is the number of neighbors. This l imited number of nodes is an improvement over Liu 's a l - gorithm, which selects n nodes in the worst case and has time complexity O ( n l o g n ) . Moreover, we showed that our proposed forwarding-node selec- tion algorithm results in fewer broadcasts in the network. In the second part of the chapter, we proposed an efficient self-pruning a l - gorithm and showed why it significantly reduces the number of forwarding nodes in the network. Interestingly, the 2-hop-based version of our proposed self-pruning algorithm can guarantee constant approximation to the optimal solution (minimum C D S ) . To the best of our knowledge, this is the first broadcast algorithm that constructs a connected dominating set (CDS) "on- the-fly" and can guarantee both full delivery and a constant approximation ratio to the optimal solution. Bibliography 11] c. Perkins, " A d lioc on demand distance vector ( A O D V ) routing (internet-draft)," 1997, internet Draft, draft-ietf-manet-aodv-OO.txt. [12] D . Johnson and D. M a l t z , "Dynamic source routing in ad hoc wireless networks," in Mobile Computing, Imielinski and K o r t h , Eds. Kluwer Academic Publishers, 1996. 13] S. N i , Y . Tseng, Y . Chen, and J . Sheu, "The broadcast storm problem in a mobile ad hoc network," In Proc. ACM International Conference on Mobile Computing and Networking (MOBICOM), pp. 151-162, 1999. 14] M . Carey and D. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness. New York, N Y , U S A : W . H . Freeman & Co. , 1990. 15] B . Clark , C. Colbourn, and D. Johnson, "Uni t disk graphs," Discrete Mathematics, vol. 86, pp. 165-177, 1990. [16] P. Wan, K . Alzoubi , and O. Frieder, "Distributed construction of con- nected dominating set in wireless ad hoc networks," In Proc. of IEEE INFOCOM, 2002. 17] S. Funke, A . Kesselman, U . Meyer, and M . Segal, " A simple improved distributed algorithm for minimum C D S in unit disk graphs," ACM Trans. Sensor Networks (TOSN), vol. 2, no. 3, pp. 444-453, 2006. 18] H . L i u , P. Wan, X . J ia , X . L i u , and F. Yao, "Efficient flooding scheme based on 1-hop information in mobile ad hoc networks," In Proc. of IEEE INFOCOM, 2006. [19] Y . Tseng, S. N i , and E. Shih, "Adaptive approaches to relieving broad- cast storms in a wireless multihop mobile ad hoc networks," In Proc. International Conference on Distributed Computing Systems (ICDCS), pp. 481-488, 2001. 20] Y . Sasson, D . Gavin, and A . Schiper, "Probabilistic broadcast for flood- ing in wireless mobile ad hoc networks," In Proc. IEEE Wireless Com- munications and Networking Conference (WCNC), pp. 1124-1130, 2003. [21] W . Lou and J . W u , "Double-covered broadcast ( D C B ) : a simple rehable broadcast algorithm in manets," In Proc. of IEEE INFOCOM, pp. 2084- 2095, 2004. 22] J . W u and F . Da i , "Broadcasting in ad hoc networks based on self- pruning," In Proc. of IEEE INFOCOM, 2003. 23] W . Peng and X . L u , " O n the reduction of broadcast redundancy in mobile ad hoc networks," In Proc. ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pp. 129-130, 2000. 24] T . He, G. Huang, B . B l u m , J . Stankovic, and T . Abdelzaher, "Range- free localization schemes in large scale sensor networks," In Proc. ACM International Conference on Mobile Computing and Networking (MO- BICOM), pp. 81-95, 2003. 25] A . Keshavarz-Haddad, V . Ribeiro, and R. Riedi , " D R B and D G C B : ef- ficient and robust dynamic broadcast for ad hoc and sensor networks," In Proc. of IEEE Conference on Sensor, Mesh and Ad Hoc Communi- cations and Networks (SECON), June 2007. 26] R. Wattenhofer, L . L i , P. Bah l , and Y . Wang, "Distributed topology con- trol for power efficient operation in multihop wireless ad hoc networks," In Proc. of IEEE INFOCOM, pp. 1388-1397, 2001. 27] L . L i , J . Halpern, P. Bah l , Y . Wang, and R. Wattenhofer, " A cone-based distributed topology-control algorithm for wireless multi-hop networks," IEEE/ACM Transactions on Networking, vol. 13, pp. 147-159, 2005. 28] M . Sun, W . Feng, and T . L a i , "Broadcasting in ad hoc networks based on self-pruning," In Proc. of IEEE Global Telecommunications Conference (GLOBECOM), pp. 2842—2846, 2001. 29] A . Papouhs, Probability and statistics. Prentice-Hall , Inc., 1990. 30] R. Chang and R. Lee, " O n the average length of delaunay triangula- tions," BIT Numerical Mathematics, vol. 24, pp. 269-273, 1984. [31] Y . C a i , K . Hua , and A . Philhps, "Leveraging 1-hop neighborhood knowl- edge for efficient flooding in wireless ad hoc networks," In Proc. IEEE International Performance, Computing, and Communications Confer- ence (IPCCC), pp. 347-354, 2005. 32] J . W u and H . L i , " O n calculating connected dominating set for efficient routing in ad hoc wireless networks," In Proc. International Workshop on Discrete Algorithms and Methods for Mobile Computing and Com- munications (DialM), pp. 7-14, 1999. Chapter 3 Localized Broadcasting with Bounded Transmission Redundancy 3.1 Introduction In this chapter, we carefully analyze and explore our proposed self-pruning broadcast algorithm (presented in Chapter 2) for the case where each node is provided with partial information about its 2-hop neighbors. After a brief introduction, we explain the related work in more details and specify the contribution of this work. A s discussed in Chapter 2, broadcasting is a fundamental communication primitive, which has many applications, including route discovery in wireless ad hoc routing protocols, and is frequently used to adapt network changes caused by the dynamic nature of ad hoc networks. Unfortunately, it is not practical to design a delivery-guaranteed broadcast algorithm that eliminates al l redundant transmissions. This is because the problem of finding the min imum Connected Dominating Set (CDS) in a unit disk graph can be reduced to the problem of eliminating al l of the redundant transmissions. It is well known that finding the M i n i m u m C D S ( M C D S ) of a unit disk graph is N P - h a r d in general [33, 34]. Note that every C D S can be used as a backbone of the network to broadcast the message. O n the other hand, the forwarding nodes in the delivery-guaranteed broadcast algorithms form a C D S . Therefore, broadcast algorithms can be used to find a C D S if a source node is selected to initiate the broadcast. Consequently, the problems of finding a minimum C D S and of designing an optimum broadcast algorithm can be reduced to each other. A version of this chapter has been accepted for publication. M . Khabbazian and V . K . Bhargava, Localized Broadcasting with Guaranteed Delivery and Bounded Transmission Redundancy, IEEE Transactions on Computers, 2008. To reduce the number of redundant transmissions broadcast algorithms typically impose some bandwidth overhead to, for example, collect neighbor information v ia message exchanges. It is desirable to reduce this bandwidth overhead to improve the practicahty of the broadcast algorithm for ad hoc networks wi th frequent topology changes. In [35], the authors prove that every distributed algorithm for constructing a non-trivial C D S has the lower message complexity bound of Q{N\ogN), where A'' is the number of nodes and the message size is a constant multiple of the number of bits representing the node ids (a C D S is said to be t r iv ia l if it consists of al l nodes). Let us define a distributed broadcast algorithm as a non-trivial broadcast algorithm if the forwarding nodes always form a non-trivial C D S . In this chapter, we show that the same lower bound does not hold for non-trivial broadcast algorithms, although they are closely related to the problem of finding a non-tr ivial C D S . In fact, we show that an extension of our proposed non- tr iv ia l broadcast algorithm requires 0{N) messages, where the message size is a constant. Moreover, we show that the number of forwarding nodes using the extended algorithm is within a constant factor of the optimum solution (i.e., min imum C D S ) . Computational overhead also plays an important role in designing efficient broadcast algorithms. Flooding is an ideal broadcast algorithm in terms of computational overhead, since each node requires almost no computation (it simply broadcasts the first copy of the received message). The existing broad- cast algorithms typically require some computation for selecting forwarding nodes or for self-pruning. In this chapter, we show how to efficiently imple- ment the proposed broadcast algorithm using some computational geometry techniques to reduce the computational overhead. 3.1.1 Related Work Different approaches can be used to classify the existing broadcast algo- rithms. One approach is based on whether or not they use a previously constructed backbone. One solution for reducing the number of redundant transmissions is to form a connected dominating set of nodes and use them as a backbone to broadcast the message. As mentioned earlier, finding the M i n - imum C D S ( M C D S ) is an N P - h a r d problem. However, there are distributed algorithms to find a small-sized C D S wi th constant approximation ratio to the M C D S [35, 36]. The main drawback of this solution is that maintaining a C D S is often costly in networks with frequent topology changes [37]. The second approach to classifying the existing broadcast algorithms is based on whether global or local information is employed by the algorithm. A n algorithm is global if it uses whole or partial global state information. O n the other hand, a distributed algorithm is localized if it is based on solely local information. It is clear that global broadcast algorithms are not appropriate for mobile ad hoc networks due to the dynamic nature of the network. In addition, they may not scale well when the number of nodes in the network increases. The localized broadcast algorithms typically use A; ^ 0 rounds of infor- mation exchange to collect fc-hop neighbor information. Therefore, they can be classified based on the number of rounds of information exchanges. These algorithms can be further categorized based on whether or not they use any "side information" piggybacked in the packets. Our proposed algorithm is based on one round of information exchange but uses partial 2-hop neigh- bor information obtained by extracting the information piggybacked in the packets. Some broadcast algorithms do not require any information exchange (i.e., A; = 0). Flooding and probabilistic broadcast algorithms such as [38] and [39] fit in this category. Probabilistic algorithms cannot typically guarantee full delivery. However, they can reduce the number of redundant transmissions at low communication overhead and have great potential in unreliable commu- nication environments. To decide whether or not to broadcast, probabilistic broadcast algorithms often use a threshold (such as probability of broadcast). Choosing a correct value of threshold is difficult. Moreover, the optimal value of the threshold may change due to network topology changes. A n adaptive approach to this problem was presented in [40 . Most existing localized broadcast algorithms use k rounds of neighbor i n - formation, where A; ^ 1 is a small number. These algorithms can be further divided into neighbor-designating (sender-based) and self-pruning (receiver- based). In neighbor-designating algorithms [37, 41], the forwarding status of each node is determined by other nodes. In other words, each broad- casting node selects a subset of its A;-hop neighbors to forward the message. The main design challenge for neighbor-designating algorithms is to choose a small subset of nodes to forward the message. For example, in [37], the au- thors proposed a broadcast algorithm based on 1-hop neighbor information that selects the smallest subset of its 1-hop neighbors with the maximum coverage area, where the coverage area of a set of nodes is the union of their transmission coverage. W h e n 2-hop neighbor information is available, it can be extended to select the minimum number of 1-hop neighbors that cover al l 2-hop neighbors. This procedure is known as the minimum forwarding set problem. There are heuristic algorithms in the literature that give a constant approximation ratio to the minimum forwarding set problem [42]. However, as shown in [41], even an optimal solution to this problem may not result in a small-sized C D S in the network. In [41], the authors extended the minimum forwarding set problem to the case where the complete 2-hop topology infor- mation is available. Note that two rounds of information exchange provide part ial topology information for the 2-hop neighbor set. To get complete 2- hop topology information, each node must either get the position information of the 2-hop neighbors or perform three rounds of information exchange [41]. The authors show that their proposed algorithm can provide a probabilis- tic constant approximation ratio to M C D S , but point out that it performs poorly when the network becomes extremely dense. In the self-pruning algorithms, each node determines its status (forwarding/ forwarding) using local information [43, 44, 45]. Clearly, the main design challenge wi th regard to self-pruning algorithms is to find an effective self- pruning condition. Different self-pruning conditions have been proposed in the literature. For example, one simple self-pruning condition is whether a l l the neighbors have received the message before the defer timer expiration. Similar to the neighbor-designating algorithms, the existing self-pruning algo- rithms do not provide a constant approximation ratio to the optimal solution ( M C D S ) . 3.1.2 Our Contribution In the first part of the chapter, we consider two general structures com- monly used in neighbor-designating and self-pruning algorithms based on 1-hop neighbor information. We show that using these structures, we are not able to guarantee both full delivery and a good bound on the number of forwarding nodes in the network. A n open question is whether localized broadcast algorithms can provide both full delivery and constant approxima- tion to the optimal solution ( M C D S ) . As mentioned earher, finding M C D S is an N P - h a r d problem. In the absence of global network information, this problem becomes even more challenging. It is a common belief that localized broadcast algorithms (e.g. self-pruning algorithms) cannot guarantee a con- stant approximation ratio to the optimal solution [43, 46]. One contribution of this chapter is to show that localized broadcast algorithms are in fact able to guarantee a reasonable bound on the number of forwarding nodes. In particular, we prove that our proposed self-pruning algorithm can pro- vide full delivery as well as guaranteeing a constant approximation ratio to the opt imal solution ( M C D S ) if the nodes are allowed to piggyback informa- tion wi th the broadcast packet. We design efficient algorithms wi th nearly opt imum computational complexity to compute the proposed self-pruning condition. It is proved in [35] that every distributed algorithm for constructing a non- tr iv ia l C D S has a lower message complexity bound of Q{NlogN), where N is the number of nodes and the message size is a constant multiple of the number of bits representing the node ids. We show that the same message complexity lower bound does not apply to the non-trivial broadcast algo- rithms. In fact, we show that the message complexity of an extension of our proposed algorithm is 0{N), where N is the number of nodes and the mes- sage size is a constant. We prove that the extended broadcast algorithm can also guarantee full delivery and a constant approximation ratio to M C D S . We show how to reduce the bandwidth requirements by reducing the amount of piggybacked information in each broadcast packet. We relax sev- eral system-model assumptions, or replace them with practical ones, to i m - prove the practicality of the proposed broadcast algorithm. Finally, we verify the analytical results using simulation and provide a comparison with one of the best broadcast algorithms based on 1-hop information. The simulation results show that the proposed broadcast algorithm performs better than what was analytically guaranteed for the worst case. 3.2 System Model In this section, we describe the system-model assumptions which are similar to those presented in Chapter 2. We discuss how to relax some of these assumptions in Section 3.5. We consider a wireless network as a collection of N nodes represented by- points located at their positions in a 2-D plane. Each node is equipped wi th an omni-directional antenna that has radio transmission range of R. Two distinct nodes are called neighbors if they are in transmission range of each other (i.e., the Euclidean distance between them is less than or equal to R). We assume that each node is able to obtain its position using an existing positioning technique, such as the Global Positioning System (GPS) . Each node periodically broadcasts a short Hello message containing its unique id and its position. Therefore, each node knows the position of its 1-hop neighbors as well. To prove that a broadcast algorithm guarantees full delivery, we assume that nodes are static during the broadcast and that the Medium Access C o n - trol ( M A C ) layer is ideal, i.e., there are no transmission errors such as coll i - sion and contention. In addition, we assume that the network is connected. A broadcast algorithm can be considered a delivery-guaranteed broadcast algorithm if it guarantees full dehvery under these assumptions. Note that without these assumptions, even flooding may not achieve full delivery. 3.3 Broadcast Algorithms Based on 1-hop Neighbor Information In this section, we consider two general structures commonly used in neighbor- designating and self-pruning algorithms based on 1-hop neighbor information. These structures require one round of information exchange and employ only 1-hop neighbor information to make decision. We show that using these structures we are not able to guarantee both full delivery and a good bound on the number of forwarding nodes in the network. 3.3.1 Neighbor-Designating Algorithms Algor i thm 3.1 shows a general structure of neighbor-designating broadcast algorithms based on 1-hop neighbor information. A s shown in Algor i thm 3.1, each node schedules a broadcast for a received message if the node is selected by the sender and if it has not received the same message before. Let us rep- resent a node A ^ ^ wi th a point A located at its position and use PQ to denote the Euclidean distance between two points P and Q. Suppose Algor i thm 3.1 is used as the basic structure in a dehvery-guaranteed broadcast algorithm based on 1-hop neighbor information. Let P be a point such that AP ^ R and for every node A ^ B NA in the network BP > R. Recall that each node uses 1-hop neighbor information, thus only A ^ i knows whether or not there is a node at the position of point P. Consequently, NA must be selected to forward the message in order to guarantee full delivery. For example, suppose NA is a node on the boundary of the network. As shown in Figure 3.1, let L be a line containing A such that all the nodes are either on the hne or one side of it . This situation occurs, for instance, when A is a vertex of the network convex hull [47]. Consider a point P on the other side of the line L such that AP = R and APIL. It is clear that BP > R for every node NB NA- Therefore, NA has to be selected to forward the message. This implies that most of the nodes around the boundary of the network (including al l the nodes on the convex hull [47 of the network) wi l l broadcast the message if Algor i thm 3.1 is used as the basic structure in a delivery-guaranteed broadcast algorithm based on 1-hop neighbor information. Consequently, neighbor-designating algorithms based on 1-hop neighbor information may not be efficient if a large number of nodes (compared to the total number of nodes) are located around the boundary of the network. The following theorem shows that a broadcast algorithm based on 1-hop neighbor information cannot guarantee both full delivery and a good bound on the number of forwarding nodes if it uses Algor i thm 3.1 as its basic structure. Convex Hull Figure 3.1: A n example of a node on the network boundary. Theorem 3.1. Suppose Algorithm 3.1 is used as the basic structure in a delivery-guaranteed broadcast algorithm based on 1-hop neighbor information. The ratio of the number of broadcasting nodes over the minimum number of required broadcasts can be as large as N, where N is the number of nodes in the network. Proof. As shown in Figure 3.2, suppose that al l the nodes are located on a line segment AB of length R or on a circle CQ R with a radius ^, where R is the radio transmission range. For every node NA, we can find a point Algorithm 3.1 A general structure of neighbor-designating algorithms 1: Extract the required information from the received message M 2: if M has been received before or does not contain node's id then 3: drop the message 4: else 5: set a defer timer 6: end if 7: W h e n defer timer expires 8: Based on 1-hop neighbor information: 9: Select a subset of neighbors to forward the message 10: At tach the list of forwarding nodes to the message 11: Broadcast the message P outside the network boundary such that AP = R and AP is orthogonal to the line segment AB/Circle CQ R. It is easy to show that BP > R for every node NB ¥= NA- Therefore, a l l of the nodes wi l l broadcast the message. However, one broadcast is enough to transmit a message to al l the nodes in the network for each scenario. Consequently, the ratio of broadcasting nodes over the minimum number of required broadcasts is N. • R B t Scenario 1 Scenario 2 Figure 3.2: Two worst-case examples for Theorem 3.1. 3.3.2 Self-Pruning Algorithms Algor i thm 3.2 shows a general structure of self-pruning broadcast algorithms based on 1-hop neighbor information. Using this structure, a node schedules a broadcast for the first received copy of the message. When the defer timer expires, the node may refrain from broadcasting the message if a certain self-pruning condition is satisfied. Theorem 3.2 shows that this structure cannot guarantee both full delivery and a good bound on the number of forwarding nodes. Note that in Algor i thm 3.2, no information is piggybacked with the broadcast packet. A n extension of Algor i thm 3.2 is to allow nodes to piggyback some information in the broadcast packet. Clearly, this extension of A lgor i thm 3.2 is stronger than both Algor i thm 3.1 and Algor i thm 3.2. In the next section, we show that a broadcast algorithm based on 1-hop neighbor information can guarantee both full delivery and a good bound on the number of forwarding nodes (a constant approximation ratio to M C D S ) if it employs this extension of Algor i thm 3.2. Theorem 3.2. Suppose Algorithm 3.2 is used as the basic structure in a delivery-guaranteed broadcast algorithm based on 1-hop neighbor information. The ratio of the number of broadcasting nodes over the minimum number of required broadcasts is 9{N) in the worst case. Proof. Consider the case where al l the nodes are on two circles C Q E and CQ m centered at O wi th radii f and respectively. A s shown in F i g - ure 3.3, suppose that for every node A ^ . on CQ R there is a corresponding node on CSR (and vice versa) such that AiBi = R. B y contradiction, suppose that neither A'^. nor Ajg. broadcast the message. Note that A'^. and do not share any neighbor. Since they have only 1-hop neighbor information and there is no information piggybacked in the broadcast packet, N^i (or A^B. ) cannot be sure whether its corresponding node has received the message. Therefore, in order to guarantee full delivery, either A^^. or A^g. has to broadcast the message. However, only a constant number of trans- missions is enough to send the message to all the nodes. Therefore, the ratio of broadcasting nodes over the minimum number of required broadcasts is e{N). • Figure 3.3: A worst-case example for Tlieorem 3.2. Algori thm 3.2 A general structure of self-pruning algorithms 1: if the message M has been received before then 2: drop the message 3; else 4: set a defer timer 5: end if 6: W h e n defer timer expires 7: Decide whether or not to broadcast M 3.4 A n EfRcient Self-Pruning Broadcast Algorithm In the previous section, we considered two structures typically used in the broadcast algorithms based on 1-hop neighbor information. We showed that these structures cannot guarantee the following properties simultaneously: • full network delivery • good bound on the number of broadcasting nodes A n open question is whether a localized broadcast algorithm (e.g., a neighbor- knowledge-based broadcast algorithm) is able to guarantee these properties. In this section, we propose a novel self-pruning broadcast algorithm based on one round of information exchange that not only guarantees full delivery but also a constant approximation ratio to the optimal solution ( M C D S ) . As its basic structure, the proposed broadcast algorithm (Algorithm 3.3) uses a simple extension of Algor i thm 3.2 in which each node is allowed to piggyback some information within the broadcast packet. In Algor i thm 3.3, each node adds a list of its 1-hop neighbor ids and positions into the broadcast packet. Upon receiving a packet, this information is extracted and used to determine the node's status (forwarding/non-forwarding) based on the following self- pruning condition. Definition 3.1 (Responsibility Condition) . Node NA is pruned (has non- forwarding status) if it is not responsible for any of its neighbors. Node NA is not responsible for its neighbor NB if NB has received the message or if there is another node Nc such that Nc has received the message and NB is closer to Nc than NA- Algorithm 3.3 The proposed broadcast algorithm 1: Extract the required information from the received packet 2: A d d the broadcasting node and its 1-hop neighbor information (except the node's own information) to the list Listfff 3: if the message has been received before then 4: drop the message 5: else 6: set a defer timer 7: end if 8: W h e n defer timer expires 9: if the responsibility condition is satisfied then 10: Remove the previous information attached to the message 11: A t tach the list of 1-hop neighbors to the message 12: Broadcast the packet 13: end if Suppose NA computes a list of nodes that have received the message {List^^) by collecting the information piggybacked in the broadcast packets. To check the responsibility condition, A^^ can first determine which neighbors have not received the message. The responsibility condition is then satisfied if and only if there is a neighbor A^^ that has not received the message and VA^c e List^'' : ÂB^CB. In Section 3.4.2, we describe efficient algoritlims for computing the respon- sibihty condition. Example 3.1. As shown in Figure 3.4, NA has six neighbors. Suppose that NA has received the message from N^. Recall that NA extracts the list of NH'S neighbors from the received packet. Therefore, it knows that N E , Np and No have received the message and N B , NC and N^ have not. According to the responsibility condition, NA is not required to broadcast because BE<BA, CF<CÂ and DG < DA (or DF < DA). Figure 3.4: A n example of self-pruning based on the responsibility condition. 3.4.1 Analysis of the Proposed Broadcast Algorithm In this section, we prove that Algor i thm 3.3 can achieve full delivery and a constant approximation ratio to M C D S . In order to prove these properties, we gissume that nodes are static during the broadcast, the networks is con- nected and the M A C layer is ideal, i.e., there is no communication error. As mentioned earlier in Section 3.2, even flooding cannot guarantee full delivery without these assumptions. Theorem 3.3. Algorithm 3.3 guarantees that all the nodes in the network will receive the message. Proof. Using Algor i thm 3.3, each node broadcasts the message at most once. Therefore, broadcasting wil l eventually terminate. B y contradiction, sup- pose there is at least one node that has not received the message after the broadcast termination. Let us consider the set A = {{Nx, NY)\NX and Ny are neighbors, Nx has received the message and Ny has not received the message} Suppose Ns is the source node (the node that initiated the broadcast) and NT is a node that has not received the message. The network is connected, thus there is a path between Ns and NT- Clearly, we can find two neighbor nodes NB and A^^ along the path from NT to Ns such that NB has not received the message, while NA has. Consequently, {NA,NB) e A , thus A 7̂  0 . As a result, 3{NA',NB') e A s.t. V( iVx, Ny) e A : WB' ^ XY. (3.1) Clearly, NA' has not broadcast since NB' has not received the message. There- fore, there must be a node Nc such that Nc has received the message and C^' < ^ R. This result contradicts to (3.1), since {Nc, NB') e A. • L e m m a 3.1. Using Algorithm 3.3, the number of broadcasting nodes inside a disk DQ E with a radius j is bounded by a constant. Proof A s shown in Figure 3.5, consider three disks DQ R, DQ SR and DQBR, centered at O with radi i j , ^ and ~ , respectively. Let us define ni-n2 = {P\P e Ui and P i U^}, where TZi and 7̂ -2 are two regions and P is a point. Suppose k is the minimum number such that for every set of k points Pi e DQ 5R — DQ SH, 1 ^ Z ^ A;, ' 4 ' 4 we have 3Pi,Pj: i^j and PiPj ^ - . Note that the area Dn - Dr, m can be covered with a constant number of ^ ' 4 ^ ' 4 disks w i t h radius f . If the number of points inside DQ SR - DQ m is greater 4 ' 4 ' 4 than the number of covering disks, at least one covering disk wi l l contain more than one point. For two points Pi and P j inside a disk with a radius J , we have P i P j ^ f . Therefore, k is bounded by a constant (the number of covering disks plus one). We prove that the number of broadcasting nodes inside DQ R is less than ' 4 or equal to k. B y contradiction, suppose that there are more than A; broad- casting nodes inside DQ R. Let NA^ e DQ R, 0 ^ i ^ k he the first A; -I- 1 broadcasting nodes ordered chronologically based on their broadcast time. Based on the responsibility condition, for every node NA, there is a corre- sponding neighbor NB, such that A^^. ^ List^^ and AiBi ^ CBi for every node Nc e List^^^, where Listff^ is the hst of nodes that have received the message based on NA/S collected information. Note that every node inside DQ wiU receive the message after NAQ'S broadcast. Therefore, NB, i DQ^^R for 1 ^ z ^ A;. O n the other hand, iV^. is a neighbor of NA, , thus NB, e DQBR . Consequently, VI A;: NB, e DQSR - DQSR- It follows that VI ^ z ^ A; : > ^ . (3.2) Suppose 1 ^ z < J ^ A;. The nodes A^^. and A^i^. are neighbors, because AiAj ^ ^. Recall that NA, piggybacks the list of its neighbors within the broadcast packet. Therefore, NB, e List^'f; , thus NB- NB.- It follows that NBX - - - Â Bfc are A; different points inside DQ BR — DQ SR . Therefore ' 4 ' 4 3 N B „ N B , - - i<j and B^Bj^^- (3.3) This is a contradiction, because Ajg. 6 List^^ and based on (3.2) and (3.3) R AjBj > => AjBj > BiBj. Thus, according to the responsibility condition, NA^ is not responsible for NBy • Theorem 3.4. Algorithm 3.3 gives a constant approximation ratio to the optimal solution (MCDS). Proof. Clearly, a disk with radius R can be covered with a constant number of disks with radius f . Therefore, based on Lemma 3.1, the number of broadcasting nodes inside a disk with radius R is bounded by a constant Cmin- Let \MCDS\ be the number of nodes in the M C D S . Each broadcasting node is inside the transmission range of at least one node in t h M C D S . O n the other hand, the number of broadcasting nodes inside the transmission range of each node in the M C D S is bounded by Cmin- Therefore, the total number of broadcasting nodes is not more than Cmin x \MCDS\. • Figure 3.5: Three co-centered disks; A ^ ^ . e DQ R and A ^ B . e DQ SR - DQ SR. The foUowing theorem shows that the message complexity of the pro- posed broadcast algorithm is 0(N), where A'' is the total number of nodes in the network and each message contains a node's id and its position. In Section 3.5, we wi l l show that the message size can be reduced to a con- stant number of bits by removing the node id from the message and using a constant number of bits to represent each node's position. Theorem 3.5. The message complexity of Algorithm 3.3 is 0{N), where N is the total number of nodes in the network and each message contains a node's id and its position. Proof. There are two types of messages used in the proposed broadcast a l - gorithm. First , each node broadcasts its id and position in a short Hello message. Second, each broadcasting node piggybacks the list of its 1-hop neighbor ids and positions into the broadcast packet. We wi l l consider this packet as n separate messages, where n is the number of 1-hop neighbors of the broadcasting node. Therefore, each message contains exactly one node's id together with its position. As shown in the proof of Theorem 3.4, the number of broadcasting neighbors of each node is bounded by a constant Cmin- Therefore, each node's id and position appears in at most Cmin + 1 messages, including the Hello message. Consequently, the total number of messages is not more than (Cmin + I) x N. • 3.4.2 EfRcient Algorithms for Computing the Responsibility Condition The problem of computing the responsibihty condition can be expressed by the following geometry problem: Definition 3.2 (Closest-Point Problem ( C P P ) ) . LetV = {PQ, P I , . . . , Pm} and Q = { Q i , Qa, • • •, <5n} be two disjoint sets of points. Is there a point Q e Q such that yPeV: QPo^ QPl The closest-point problem attempts to establish whether or not PQ is the closest point in V to at least one point in Q. One approach to solving C P P is to find the closest point in V to every point in Q. The tr iv ia l algorithm for finding the closest point in P to a query point Q 6 Q is to compute the distance from Q to ah the points in "P, keeping track of the "closest point so far". Clearly, using this algorithm, the computational complexity of solving the C P P would he 0{mxn). F inding the closest point in P to a query point Q e Q is a well-known problem called the Nearest Neighbor Search (NNS) problem. To solve the N N S problem, several space-partitioning methods, including kd-tree and the Voronoi diagram [47], can be used. A kd-ixee is a data structure used for organizing points in fc-dimensional space. A fcrf-tree for the set of 2-D points V can be constructed in O ( m l o g m ) . Moreover, the computational complexity of a query is O( logm) [47]. Therefore, using A;d-tree, the C P P can be solved in 0 ( m l o g m + n l o g m ) . Similarly, we can use the Voronoi diagram to solve C P P . The Voronoi diagram is a partitioning of a plane with n generating points into convex polygons called Voronoi cells, such that each cell contains exactly one generating point and every node in the cell is closer to the generating point of the cell than to other generating points. It is known that the Voronoi diagram can be constructed in 0{n log n) and that each cell has 0{n) edges in the worst case. Therefore, using the set of points V as the generating points, the Voronoi diagram can be generated in 0 ( m log m). The node PQ is the closest node in P to a query point Q if and only if Q is in the Voronoi cell of PQ. We can check whether a query point Q is in the Voronoi cell of PQ in O( logm) , since the Voronoi cell of Po is a convex polygon with at most 0 ( m ) edges. Therefore, the C P P can be solved in 0 ( m log m + n l o g m ) using the Voronoi diagram. Note that we only need to compute the Voronoi cell of PQ. The Voronoi cell of PQ can be computed in 0 ( m l o g / i ) , where h is the number of edges of the cell. The average number of vertices of a Voronoi cell is less than six [47], thus is a constant on average. Therefore, the average case computational complexity of this approach is 0 ( m + n). Suppose PQ is not the closest point in V to any node in Q. In this case, Q{n) is a lower bound for every algorithm to solve the C P P for sets V and Q, because the algorithm cannot ignore any node in the set Q. O n the other hand, every algorithm to solve the C P P has to consider al l the points in V if PQ is the closest point in P to a node in Q. Thus, f2(m) is also a lower bound for such algorithms. Considering both cases, it follows that fl{m+n) is a lower bound for every algorithm to solve the C P P . We described algorithms that compute the C P P in 0 ( ( n + m ) l o g m ) , in the worst case. These algorithms are nearly optimal in terms of computational complexity, because log m is a small factor in practice. Moreover, by constructing the Voronoi ceU of PQ, we showed that the C P P can be solved in 0{n + m) in the average case. Theorem 3.6. The worst-case complexity of computing the responsibility condition is 0{Ac].ogAG), where Ac is the maximum node degree of the network. Proof. Based on Algor i thm 3.3, a node A^^ stores the broadcasting neigh- bors' information and their 1-hop neighbors' information (except Ayi's i n - formation) in List^^. The node NA can compute List^°^^^'^, the list of its neighbors that have not received the message, in 0 ( / x n), where 1 ^ / n is the number of broadcasting neighbors and n is the total number of neighbors. Consider the set of points V={Po,Pl,...,Pm} where P Q is located at the position of NA and P i , P 2 , . . . , PT„ are located at the positions of the nodes in List^^. Suppose Q = {Qi,Q2,...,Qk} is the set of points located at the position of the nodes in List%°^^^'^. As mentioned earlier, by constructing the Voronoi cell of P Q , we can compute the C P P in 0{{m + k)\ogm) for sets V and Q. Clearly, the responsibility condition is satisfied if and only if there exists a point Q s Q such that V P 6 P : QPQ^ QP. As shown in the proof of Theorem 3.4, I (the number of broadcasting neigh- bors of NA) is bounded by a constant. Moreover, we have k ^ n, m ^ I x Ac and n ^ A ^ , where A Q is the maximum node degree of the network. There- fore, the complexity of computing the responsibility condition is 0{l X n) + 0{{m+k) logm) = O ( A G l o g A G ) . Note that the C P P can be solved in 0{k + m) in the average case. Therefore, the average complexity of computing the responsibility condition is 0{l xn) + 0{m + k)^ 0{AG). • 3.4.3 Reducing Bandwidth Requirements In Algor i thm 3.3, each forwarding node piggybacks the list of its 1-hop neigh- bors in the broadcast packet. In this section, we show how a forwarding node can reduce bandwidth overhead by piggybacking a list of a subset of its 1-hop neighbors. Definition 3.3 (Representative Set). LetV be a set of points {Pi, P2, • • •, P„} inside a circle CO,R- The set S ^ V is a representative set for V if for every point Q outside CO,R (i.e., UQ> R) 3P'eS s.t. yPeV: PV^PQ- A representative set Smin ofV is called the minimum representative set ofV if'Smin hcis ihe minimum cardinality among all the representative sets ofV. Definition 3.4 (Representative Neighbor Set). We say P is the cor- responding point of the node Nx if P is located at the position of Nx. Let V be the set of corresponding points of NA'S neighbors. A subset of NA'S neighbors is called a representative neighbor set if their corresponding point set is a representative set ofV. The set of NA'S representative neighbors with the minimum number of nodes is called the minimum representative neighbor set. L e m m a 3.2. In Algorithm 3.3, a forwarding node can piggyback a list of its representative neighbors instead of the list of all its neighbors, without affecting the forwarding status of any other node in the network. Proof. Let List^^ be a list of representative nodes of NA- Suppose NA piggybacks List^^ instead of the list of al l its neighbors and NB i List^^ is a neighbor of NA- The node NB is required in computing the responsibility condition of AT^'s neighbor Nç if Nc has a neighbor ND that has not received the message and BD < CD. Note that Nr, is not a neighbor of NA since all of N A S neighbors have received the message. Therefore, ND is outside CA,R, where CA,R is the transmission range of NA- Based on the definition of representative neighbor set, there exists a node NE e List^^ such that ED^BD ED< CD. Therefore, for each neighbor of NA required in computing the responsibility condition of Nc, we can find a node in List^^^ that leads to the same result. • Lemma 3.2 shows that forwarding nodes can save bandwidth by piggy- backing the list of their representative neighbors instead of the list of al l their neighbors. Clearly, finding the minimum representative neighbor set is equivalent to computing the minimum representative set of P , where V is the set of points corresponding to the node's neighbors. Let us denote the Voronoi diagram of V by V o r ( P ) . Assume that Cell{P) is the set of vertices of the ceU of Vor('P) that corresponds to a point P eV. Note that Cell{P) includes a vertex Va^ "at infinity" if the Voronoi cell of P has an infinite edge. Theorem 3.7 shows that the minimum representative set of V is unique and can be computed in 0{\V\ log\V\). L e m m a 3.3. Suppose V is a set of points inside the circle Co R and Synin is the minimum representative set ofV. We have PeSmin « JVBCell{P): OV > R. Proof. Suppose that V V ^ 6 Cell{P) : OV ^ R. In this case, the entire Voronoi cell of P w i l l be inside the circle CQ^R. There- fore, for every point Q outside the circle we have 3 P ' e V : P'Q ^ PQ, because Q is outside the Voronoi cell of P. Consequently, P is not required to be i n a representative set of V, thus it is not in the minimum representative set of V. Now, suppose that 3V 6 Cell{P) : OV > R. Since the point P is inside the circle, the line segment PV crosses the circle in a point U. Consider a point Q on the line segment UV such that Q ¥= U and Q ^ V. Clearly, Q is outside the circle CO,R, i.e., OQ > R. Since the Voronoi cell of P is a convex polygon, the point Q is inside the cell and is not located on any edge of i t . Therefore, we have V P ' e V\{P} : PQ < P'Q. Consequently, P must be in every representative set of V including its m i n i - mum representative set. • Theorem 3.7. Suppose V is a set of points inside a circle CO,R- The mini- mum representative set ofV is unique and can he computed m 0(|P| log Proof. Based on Lemma 3.3, a point P is in the minimum representative set of V if and only if 3V 6 Cell{P) : ÔV > R. There is a single Voronoi diagram associated wi th each set of generating points. Therefore, the minimum representative set is unique. From Lemma 3.3, it also follows that the minimum representative set of P is a subset of every representative set of V. To compute the minimum representative set of V, we first compute the Voronoi diagram Vor(7'). For each Voronoi cell, we then check whether it has a vertex outside the circle CO,R- The Voronoi diagram of V can be computed in 0(|P| log [Pj). Moreover, the average number of vertices of a cell is less than six [47]. In other words, the total number of vertex-checking operations is less than 6 x Therefore, the complexity of computing the representative set is 0{\V\ log 1̂ 1) + 0{\V\) = 0{\V\ log\V\). a In the worst case, we have \Smin\ = I'Pl, where Smin is the minimum representative set of V. This situation occurs, for example, when all the points in V are located in a line segment or on a circle. However, it can be shown that hm M ^ i l i l ) ^ 0, IPHoo \V\ where E{\Smin\) is the expected cardinality of the minimum representative set of V. In order to avoid complex analytical analysis, we used simulation to analyze E{\Smin\)- The simulation results are presented in Section 3.6. Suppose that the forwarding nodes can piggyback a list of their repre- sentative neighbors instead of the list of al l their neighbors. In this case. Theorem 3.8 shows that a node can simply avoid broadcasting if it is not in the list of the nodes piggybacked in at least one received packet. Theorem 3.8. A node can set its status to non-forwarding for a message M if it receives M in a packet that does not list NA as a representative node. Proof. Suppose NA receives the message from node NB and that NA is not in the list of NB^S representative nodes piggybacked i n the packet. We prove that NA& status is non-forwarding based on the responsibility condition. NAS status is non-forwarding if al l of its neighbors have received the message, so we assume that this is not the case. Suppose Nc is a neighbor of A^^ that has not received the message. Therefore, Nc is not a neighbor of N B , hence it is outside CB,R, where CB,R is the transmission range of NB- Since NA is not in the representative neighbor set of N B , there exists a node No ^ NA such that ND is in the representative neighbors set of NB and DC ^ AC. Note that DC AC, because based on Lemma 3.3, the Voronoi cell of the point A is inside CB,R. Therefore, DC < AC. It follows that NA is not responsible for any of its neighbors and therefore has a non-forwarding status. • 3.5 Relaxing Some of the System-Model Assumptions The assumptions made in Section 3.2 are often used in the existing broadcast algorithms in order to model the network. Some of these assumptions are not practical. For example, a node may obtain its position using the Global Positioning System (GPS) . However, the position is not accurate due to several sources of error including positioning error and the l imited number of bits used to represent the position. In this section, we discuss how to relax some of the system-model assumptions or replace them with more practical ones in order to improve the practicality of our proposed broadcast algorithm. We show that al l of the extensions of the proposed algorithm can provide both ful l delivery and a constant approximation ratio to the optimal solution under the new assumptions. 3.5.1 Broadcasting Under Uncertain Position Information As mentioned earlier, the assumption of having the precise position is not practical. In practice, there are several sources of error. For example, the position information obtained by G P S typically includes some errors, which vary between different G P S devices. Another source of error is roundoff error or representation error, which is associated with the fact that a finite number of bits is used to represent the position information. Typically, each node in the network is able to reduce the representation error by assigning a fairly large number of memory bits to represent a number. However, to reduce the bandwidth and power overhead, it is desirable to use as few bits as possible to represent the position information added in the Hello messages or the broadcast packets. In this section, we show that a constant number of bits suffices to maintain the main properties of the proposed algorithm. Let 5 be an upper bound on the maximum position error and S S an upper bound for maximum error in computing the distance between two points. Suppose that £ is known by a l l the nodes in the network. We have A B - £ ^ T{ÂB) ^JB + £, (3.4) where T{AB) is the approximated distance between the points A and B. Algor i thm 3.4 shows how to compute the responsibility condition under un- certain position information. Let List^^^^ be the list of N^s neighbors, List^°^^'^ be the list of AT^'s neighbor that have not received the message and List^^ be the list of nodes that have received the message, i.e., al l of the broadcasting nodes together with their 1-hop neighbors. Algor i thm 3.4 returns true if and only if NA has a neighbor NB e List^°^^'^ such that ViVc e List^^ : T(ÂB) -S^ T{BC) + S. (3.5) The output of A lgor i thm 3.4 determines whether the responsibility condition is satisfied. Algorithm 3.4 Computing the responsibihty condition under uncertain po- sition information Input: List%''^, Listy^'^'^, Listfif and the max error c Output : true or false 1: for i = 1; 2 ^ length (Listf^*^=); ++i do 2: dist{ListfS'^^\il ID) 3: chk <— true 4: for j = 1; j ^ length(Lzsif^'=); ++j do 5: if dist(Lz5^f^*^^'=[i],List%^[3\) <d-2£ then 6: chk <— false 7: break 8: end if 9: end for 10: if (chk) then 11: return true 12: end if 13: end for 14: return false Theorem 3.9. Algorithm 3.3 guarantees full delivery under uncertain posi- tion information if it uses Algorithm 3.4 to compute the responsibility condi- tion. Proof. The proof is similar to that of Theorem 3.3. The broadcasting wi l l eventually terminate, since each node transmits the message only once. B y contradiction, suppose there is a node that has not received the message after termination of broadcasting. Let us consider the set A = {{Nx, NY)\NX and Ny are neighbors, Nx has received the message and Ny has not received the message} Suppose Ns is tiie source node and NT is a node tliat has not received the message. The network is connected, thus there is a path between Ns and NT- Clearly, we can find two neighbor nodes NB and A^^ along the path from NT to Ns such that NB has not received the message, while A^^ has. Consequently, (A^^, NB) e A , thus A 7̂  0 . A s a result, 3(A^^/, NB') e A s.t. \/{Nx, Ny) e A : WB' ^ XY. (3.6) Node NB' has not received the message, hence it is not a neighbor of any broadcasting node. Consequently, NA' does not consider NB' as a node that has received the message. Clearly, NA' has not broadcast since NB' has not received the message. Considering the responsibility condition, it follows that there is a node Nc' such that Nc has received the message and T{WC') + S < T{AB') - S. Using (3.4) we get WC' < J^B'. This result contradicts (3.6), since {Nc, NB') S A . • Theorem 3.10. Using Algorithm 3.4 to compute the responsibility condi- tion, the proposed broadcast algorithm (Algorithm 3.3) guarantees a constant approximation ratio to the optimum solution under uncertain position infor- mation if £ = J — XR, where 0 < A ^ | and j is bounded by a constant number. Proof. We show that the number of broadcasting nodes inside a disk DQ R with a radius j is bounded by a constant. Using the same approach used in the proof of Theorem 3.4, it then follows that the total number of broadcast- ing nodes is bounded by a constant factor of that of the optimum solution. Let DQ |, DQ m and DQ SR be three disks centered at O with radi i ~, ^ and respectively. Suppose k is the minimum number, such that for every set of k points Pj e DQ^R — DQ3E, 1 ^ i ^ A;, we have 3Pi, Pj : i^ j and ^ ^ A P . Note that j is bounded by a constant, so the area DQ5R — DQÎR can be covered with a constant number of disks with radius If the number of points inside D Q - D Q m is greater than the number of covering disks, at ' 4 ' 4 least one covering disk wi l l contain more than one point. For two points Pi and P2 inside a disk wi th radius we have P1P2 ^ \R. Therefore, k is bounded by a constant (the number of covering disks plus one). We prove that the number of broadcasting nodes inside D Q R is less than or equal to k. B y contradiction, suppose that there are more than k broadcasting nodes inside D Q R. Let e D Q R, 0 ^ i ^ k he the first k + 1 broadcasting ' 4 ' 4 nodes ordered chronologically based on their broadcast time. Based on the responsibility condition, for each node A ^ ^ . there is a corresponding neighbor NB^ such that iVg. ^ List^^^ and V A ^ c e List^^^ : r{AiBi) r{BiC) + S, where List^^ is the list of nodes that have received the message based on A ' ^ . ' s collected information. Suppose 1 < j ^ k. Nodes A T ^ . and NAJ are neighbors, because AiAj ^ ^. Recall that A ^ ^ . piggybacks the hst of al l its neighbors within the broadcast packet. Therefore, NB- e List^^^ , thus NBi # NBJ • Note that every node Nc e D Q 3R w i l l receive the message after A^Ao's broadcast, because A Q C ^ R. Therefore, Nc is in the list of nodes piggybacked by NAÇ, in the broadcast packet. Thus n^i^k: Nee List^^. It follows that V I A ; : N B . ^ D Q ^ - O n the other hand, A ^ B . is a neighbor of A ^ i ^ , thus NB^ e D Q 5R . Conse- quently, Thus, V I A;: NB^ e DQ5E - DQm- R yi^i^k: AiBi > - . ( 3 . 7 ) There are A; different nodes NB^ • • • NB,, inside D Q SR - D Q ZR. Therefore, ' 4 ' 4 3 A ^ B . , A ^ B . : i<j and BiBj ^ XR. ( 3 . 8 ) From ( 3 . 4 ) we have TiB^Bj) + B^j + 2£. Thus, using (3.8) we get R r{BiBj) + S ^ - + S. (3.9) O n the other hand, we have AjBj > ^. Hence, r{AjBj) - £ > ^ - 2 £ . (3.10) Since £ ^ f , we have Thus, based on (3.9) and (3.10) we get R ^ R ^ ^ V{BiBj) +e < V{AjBj) - S This result is a contradiction, because based on (3.5), Â ^̂ . is not responsible iox NBJ. • Example 3.2. Suppose that ^ ^ f • Therefore, we have where A ^ ^ . Note that 72) is bounded by a constant. Thus, based on Theorem 3.10, the proposed broadcast algorithm can guarantee a constant approximation ratio to the optimal solution if the maximum error S is less than or equal to f . A s shown in Theorem 3.10, A lgor i thm 3.3 can guarantee a constant ap- proximation ratio to M C D S if the maximum error is bounded by a factor of the transmission range. As a result, employing the same approach used in the proof of Theorem 3.5, we can show that the message complexity of A lgor i thm 3.3 under uncertain position information is sti l l 0{N), where N is the total number of nodes in the network and each message contains a node id and its position. Note that node ids can be simply removed from the message without affecting the functionality of the proposed broadcast algorithm. It is because the responsibility condition is based solely on the approximate/precise position information of the nodes. Suppose that aU of the nodes in the networfc are in an L x L square area. Clearly, each node requires an infinite number of bits in general to precisely represent its position. However, allowing errors in position information, node position can be represented by a l imited number of bits, provided that the size of square area is finite. For example, assume that we allow the maximum position error of aR. As shown in Figme 3.6, the L x L square area can be partitioned into r L V2aR ] X f y ^ l grid cells of size y/2aR x ^/2aR. Let the tuple (/, J ) denote the coordinate of the cell in the grid. For instance, (1,1) indicates the bottom left cell of the gird. Suppose each node uses the coordinate of the cell in which it is located to indicate its position. In this case, the position of the node can be estimated by the position of the center of the cell. Therefore, the number of bits required to represent the approximate position is at most [lg2 V2aR J V V2aR , 21g2 and the maximum position error is one-half of the cell diagonal, i.e., V2{V2aR) = aR. Note that the number of bits required to represent the approximate position increases as ~ increases. yJall — • (2.1) (2.2) Position error (1,1) (1.2) M a x i m u m position on Figure 3.6: Partit ioning the network into square cells. Lemma 3.4. Suppose that the node NA is required to send its position with the maximum error aR to its neighbor NB • In this case, NA requires only a constant number of bits to represent its position if ^ is bounded by a constant. Proof. Suppose (i,j) is the coordinate of the cell in which NA is located and that the side of each grid cell is \/2aR. Node NA can transmit the tuple (z m o d a ^ J + 2 ) , i m o d a ^ J + 2)) a a to node NB- Suppose {i,j) and are the coordinates of two different cells such that i = i' m o d ( [ ^ J + 2 ) , and j^f m o d ( [ ^ J + 2 ) . Let Pi and P^ be two points inside the cells and respectively. It is easy to show that ^ 2 ^ ( L ^ J + 1) X {V2aR) = > P^2> 2R. It follows that a circle with radius R cannot intersect both cells. Therefore, NB can uniquely identify the cell using the tuple {i m o d a ^ J + 2 ) , j m o d ( [ ^ J + 2)). a a Consequently, NA is required to transmit only \ a J a bits, which is constant if ^ is bounded by a constant. Node NB can ap- proximate the position of NA by taking the position of the center of the cell. • A s mentioned earlier, the message complexity of A lgor i thm 3.3 is 0{N) under uncertain position information if the maximum position error is bounded. Moreover, using Lemma 3.4 , it follows that the size of each message can be reduced to a constant number of bits by removing the node id and using a constant number of bits to represent the approximate position. In [35], the authors proved that every distributed algorithm for constructing a non-trivial C D S has the lower message complexity bound of ^(NlogN), where TV is the number of nodes and the message size is a constant multiple of the number of bits representing the node ids. Al though finding a non-trivial C D S and designing a non-trivial broadcast algorithm are closely related problems, our results show that the same message complexity lower bound does not apply for the non-trivial broadcast algorithms. 3.5.2 Relaxing the Homogeneous Network Assumption In practice, devices may have different transmission ranges. Suppose G' is a graph for which there is a link from A^^ to NB if NB is in transmission range of N^.. Let G be an undirected graph obtained by removing uni - directional links of the graph G'. We assume that G is connected and define two nodes as neighbors if there is a link between them in G (i.e., they are in transmission range of each other). Note that many wireless medium access control protocols, such as I E E E 802.11, require bi-directional links. Let us use P^v^ to denote a lower bound of A^i's transmission range. Suppose each node includes the lower bound of its transmission range in the Hello message. Moreover, assume that the forwarding nodes include the lower bounds of their neighbors' transmission ranges in the broadcast packets. The responsibility condition of node A^^ is satisfied if A^^ has a neighbor A^^ such that NB has not received the message, and for every node Nc that has received the message AB ^CB or CB> RNC- Using a similar approach as that used in the proof of Theorem 3.3, we can show that Algor i thm 3.3 guarantees ful l delivery in a heterogeneous network if it employs the new responsibility condition. Suppose Rmin is a lower bound for the transmission ranges of al l the nodes in the network and Rmax is an upper bound. The following theorem shows that the proposed broadcast algorithm can sti l l guarantee a good bound on the number of forwarding nodes in a heterogeneous network if is bounded by a constant. Theorem 3.11. The proposed broadcast algorithm can guarantee a constant approximation ratio to the optimal solution in a heterogeneous network if #^ is bounded by a constant. Proof. Let D^R^, D^ZR^ and DQ R^^J^^^ be three disks centered at O w i th radi i ^^f^ and + Rmax, respectively. Suppose k is the minimum number such that for every set of k points Pi e D „ R ^ ^ ^ , ^ - D^ 3R^i„, 1 ^ z ^ fc, we have Pmin 3Pi, Pj-. i^ j and PiPj ^ Note that is bounded by a constant, so the area D^ R „ J „ , „ —D^^ SR. mm 4 'T.-^max ^ , 4 can be covered wi th a constant number of disks wi th radius If the number of points inside D„ R^J^ , ^ - D „ 3 f l ^ ^ „ is greater than the number of covering disks, at least one covering disk wi l l contain more than one point. For two points P i and P2 inside a disk wi th radius we have P1P2 ^ Therefore, k is bounded by a constant (the number of covering disks plus one). Using a technique similar to that used in the proof of Lemma 3.1, we can show that the number of broadcasting nodes inside D Q R^J^ is less than ' 4 or equal to k. Since is bounded by a constant, a disk with radius Rmax can be covered with a constant number of disks with radi i Rmin- It follows that the total number of broadcasting nodes is bounded by a constant factor of that of the optimum solution (refer to the proof of Theorem 3.4). • 3.5.3 Broadcasting in Three-Dimensions We assumed in Section 3.2 that the nodes are placed in a 2-D plane. In gen- eral, the nodes can be located in 3-D space, as the network area may not be perfectly flat. In this case we assume that the nodes are provided with their position in 3-D. Interestingly, al l the properties of the proposed broadcast algorithm are preserved in 3-D. Assuming AB as the Euclidean distance of two points in 3-D, we can use the proof of Theorem 3.3 to show that Algo - r i thm 3.3 guarantees full dehvery in 3-D space. Note that the transmission range of a node in 3-D is a sphere. Replacing circles by spheres in the proofs of Lemma 3.1 and Theorem 3.4, we can similarly argue that Algor i thm 3.3 guarantees a constant approximation ratio to tlie optimal solution in 3-D. Finally , using a technique similar to that used for 2-D, we can show that, in 3-D, the proposed algorithm not only preserves its main properties under un- certain position information (provided that the maximum error is bounded) but also can benefit from the proposed bandwidth-overhead reduction tech- nique introduced in Section 3.4.3. 3.6 Simulation 3.6.1 Reducing Bandwidth Overhead A s shown in Section 3.4.3, a forwarding node can piggyback the list of a subset of its neighbors (its representative neighbor set) instead of a l l of them without violating the status (forwarding/non-forwarding) of any other node in the network. To avoid the complexity of mathematical analysis, we used simulation to find the average cardinality of the minimum representative set. For a given number of neighbors 1 ^ n < 500, we randomly put n points inside a unit circle and computed the minimum representative set Smin- To get the average cardinality E{\Smin\), we ran the simulation lO"* times for each given n. Figure 3.7 shows the ratio x 100. A s shown in Figure 3.7, the ratio •̂ d'̂ ™"-!) decreases as the number of neighbors increases. For instance, the minimum number of representative nodes is on average less than 50% of total number of nodes when n ^ 33. 3.6.2 Performance of the Proposed Broadcast Algorithm To verify the theoretical results, we used the ns-2 simulator to compute the average number of forwarding nodes. In ns-2, the total size of the data packet was fixed to 256 bytes and the bandwidth of the wireless channel was set to 2 M b / s . In each simulation run, we uniformly distributed N nodes in a 1000 X 1000 square area. A randomly generated topology was discarded if it leaded to a disconnected network. Only one broadcast was initiated in each simulation run by a randomly selected node. Table 3.1 summarizes some of the parameters used in ns-2. Figure 3.8 illustrates an instance of using the proposed algorithm for the case where R = 300m, N = 400 and nodes are placed in a square area of Figure 3.7: The ratio ^il^^^^l) x 100 against the total number of neighbors. 1000 X lOOOm^. As shown in this figmre, only 10 nodes (represented by stars) among 400 nodes broadcast the message. Figures 3.9 and 3.10 show the ra - tio of the number of broadcasting nodes over the total number of nodes. To get the results shown in Figure 3.9, we varied the transmission range from 50 to 300 meters and fixed the total number of nodes to 1000. Figure 3.10 shows the result of the experiment for which the transmission range was fixed to 250 meters and the total number of nodes varied from 25 to 1000. We compared the performance of our proposed algorithm with that of the broadcast algorithm proposed in [37]. In [37], L i u et al. showed that the number of broadcasting nodes using their proposed flooding algorithm is sig- nificantly lower than that of previous notable broadcast algorithms [48, 49 . We also considered the ratio-8 approximation of M C D S [35] as a benchmark. As shown in Figures 3.9 and 3.10, our proposed broadcast algorithm can significantly reduce the number of forwarding nodes. Moreover, it slightly outperforms the ratio-8 approximation. In Chapter 2, we proved that using a weaker version of the proposed broadcast algorithm the probability of two neighbor nodes transmitting the same message exponentially decreases when the distance between them decreases or when the node density increases. This property can further justify why the proposed broadcast algorithm can significantly reduce the number of transmissions in the network. Another metric evaluated using simulation was the algorithm delay, which we define as the time between the first and the last transmission in a single message broadcast. Figure 3.11 shows the average delay of our proposed algorithm and compares it with that of Liu 's broadcast algorithm. As shown in this figure, the average delay of our broadcast algorithm is 80% to 50% of that of Liu 's algorithm when the total number of nodes varies from 50 to 1000. We also evaluated the performance of the proposed algorithm when there is uncertainty in position information. We set the transmission range to R = 250 meters and fixed the maximum position error to aR, where 0.01 ^ a ^ 0.15. Figure 3.12 shows the average number of broadcasting nodes for a given a when the number of nodes varies within 25 — 1000. As shown in Figure 3.12, the performance of the broadcast algorithm slightly degrades as the maximum position error increases. Finally, we evaluated the performance of the proposed algorithm for the case where nodes can have different trans- mission ranges. In the simulation, we randomly placed 25 ^ N ^ 1000 nodes in the network. The transmission range of each node was selected randomly from the interval [i?^i„,250], where Rmin < 250 is the minimum transmis- sion range. The value of Rmin varied within 150 to 250 meters. A s shown in Figure 3.13, the simulation results indicate that the performance of the proposed broadcast algorithm shghtly decreases as Rmin decreases. Based on the simulation results shown in Figure 3.9, this effect is expected as the number of transmissions increases when the transmission range decreases. Parameter Value Simulator M A C Layer Propagation Model Packet Size Bandwidth Size of Square Area Transmission Range Number of Nodes ns-2 (version 2.27) I E E E 802.11 two-ray ground 256 bytes 2 Mb/sec 1000 X lOOOm^ 50-300m 25-1000 Table 3.1: Simulation parameters Figure 3.8: Broadcasting nodes in a 10^ x lO^m^ square area wit l i 400 nodes. Figure 3.9: Rat io of broadcasting nodes vs. transmission range. 1r 4 I Proposed Algorithm Figure 3.10: Rat io of broadcasting nodes vs. total number of nodes. Figure 3.12: Rat io of broadcasting nodes of the proposed algorithm with uncertain position information. .R^«=150 meters =175 meters -R^=225 meters 400 600 Total number of nodes 1000 Figure 3.13: Ratio of broadcasting nodes of the proposed algorithm in a network with nodes having different transmission ranges. 3.7 Summary We considered two general structures typically used in broadcast algorithms based on 1-hop neighbor information. We showed that a broadcast algorithm cannot guarantee both full delivery and a good bound on the number of transmissions if it uses any of these structures. It is commonly believed that a locahzed broadcast algorithm is not able to guarantee a good bound on the number of transmissions. We presented a localized broadcast algorithm based on 1-hop information and proved that it guarantees both full delivery and a constant approximation ratio to the optimal solution. The proposed broadcast algorithm has low message and computational complexities. In fact, we proved that the message complexity of the proposed algorithm is less than the lower message complexity bound of finding a non-trivial C D S and that its computational complexity is nearly optimal. Moreover, we proposed a technique to further reduce the bandwidth overhead. We then relaxed several system-model assumptions, or replaced them with practical ones, to improve the practicality of the broadcast algorithm. Finally, we verified the analytical results using simulation. Bibliography 33] M . Garey and D. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness. New York, N Y , U S A : W . H . Freeman & Co. , 1990. 34] B . Clark , C. Colbourn, and D . Johnson, "Uni t disk graphs," Discrete Mathematics, vol. 86, pp. 165-177, 1990. [35] P. Wan, K . Alzoubi , and O. Prieder, "Distributed construction of con- nected dominating set in wireless ad hoc networks," In Proc. of IEEE INFOCOM, 2002. 36] S. Funke, A . Kesselman, U . Meyer, and M . Segal, " A simple improved distributed algorithm for minimum C D S in unit disk graphs," ACM Trans. Sensor Networks (TOSN), vol. 2, no. 3, pp. 444-453, 2006. 37] H . L i u , P. Wan, X . J i a , X . L i u , and F . Yao, "EfRcient flooding scheme based on 1-hop information in mobile ad hoc networks," In Proc. of IEEE INFOCOM, 2006. [38] Y . Tseng, S. N i , and E . Shih, "Adaptive approaches to relieving broad- cast storms in a wireless multihop mobile ad hoc networks," In Proc. International Conference on Distributed Computing Systems (ICDCS), pp. 481-488, 2001. 39] Y . Sasson, D. Gavin, and A . Schiper, "Probabihstic broadcast for flood- ing in wireless mobile ad hoc networks," In Proc. IEEE Wireless Com- munications and Networking Conference (WCNC), pp. 1124-1130, 2003. 40] P. Kyasanur, R. Choudhury, and I. Gupta , "Smart gossip: A n adap- tive gossip-based broadcasting service for sensor networks," In Proc. IEEE International Conference on Mobile Adhoc and Sensor Sysetems (MASS), pp. 91-100, 2006. 41] J . W u , W . Lou , and F . Da i , "Extended multipoint relays to determine connected dominating sets in manets," IEEE Trans, on Computers, vol. 55, no. 3, pp. 334-347, 2006. 42] G . Calinescu, I. Mandoiu , P . - J . Wan , and A . Zelikovsky, "Selecting for- warding neighbors in wireless ad hoc networks," Mobile Networks and Applications, vol. 9, no. 2, pp. 101-111, 2004. [43] J . W u and F . Da i , "Broadcasting in ad hoc networks based on self- pruning," In Proc. of IEEE INFOCOM, 2003. 44] W . Peng and X . L u , " O n the reduction of broadcast redundancy in mobile ad hoc networks," In Proc. ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pp. 129-130, 2000. [45] I. Stojmenovic, M . Seddigh, and J . Zunic, "Dominating sets and neigh- bor elimination-based broadcasting algorithms in wireless networks," IEEE Trans, on Parallel and Distributed Systems, vol. 13, pp. 14-25, 2002. 46] J . W u and W . Lou , "Forward-node-set-based broadcast in clustered mo- bile ad hoc networks," Wireless Communications and Mobile Comput- ing, vol. 3, no. 2, pp. 155-173, 2003. [47] M . de Berg, M . van Kreveld, M . Overmars, and 0 . Schwarzkopf, Com- putational Geometry: Algorithms and Applications, 2"*̂  ed. New York: Springer-Verlag, 2000. 48] Y . C a i , K . Hua, and A . Philhps, "Leveraging 1-hop neighborhood knowl- edge for efficient flooding in wireless ad hoc networks," In Proc. IEEE International Performance, Computing, and Communications Confer- ence (IPCCC), pp. 347-354, 2005. 49] J . W u and H . L i , " O n calculating connected dominating set for efficient routing in ad hoc wireless networks," In Proc. International Workshop on Discrete Algorithms and Methods for Mobile Computing and Com- munications (DialM), pp. 7-14, 1999. Chapter 4 Wormhole Attack in Wireless A d Hoc Networks: Analysis and Countermeasure 4.1 Introduction The wormhole attack [50] is one of the most severe security attacks encoun- tered in wireless ad hoc networks. It can significantly disrupt the communi- cations across the network, is hard to detect and can be implemented without having a cryptography key or knowing the network routing protocol. In a wormhole attack, the attacker receives packets at one location in the net- work, "tunnels" them to another location and replays them there. A single malicious node can launch this attack by, for example, broadcasting the route requests at a high power level. The wormhole attack is much more powerful if it is launched by more than one attacker. In this case, attackers can tun - nel the packets to each other by simply encapsulating them or by using an out-of-band link. Once a wormhole is established, malicious nodes can use it for traffic analysis or to make a Denial-of-Service (DoS) attack by dropping certain data or control packets. The wormhole attack can be launched in two different modes. In the hid- den mode, the attackers do not use their identities so they remain hidden from the legitimate nodes. In fact, the attackers act as two simple transceivers that capture messages at one end of the wormhole and replicate them at the other end. In this way, they can create a virtual link between two far-off nodes by, for example, "tunneling" their Hello messages. The existing worm- hole detection schemes [50, 51, 52] typically consider this mode. Clearly, the A version of this chapter has been accepted for publication. M . Khabbazian, H. Mercier and V . K . Bhargava, Severity Analysis and Countermeasures for the Wormhole Attack in Wireless A d Hoc Networks, IEEE Transactions on Wireless Communications, 2008. attackers require no cryptographic keys to launch the wormhole attack in the hidden mode. In the participation mode, it is assumed that the attackers possess valid cryptographic keys that can be used to launch a more powerful attack. In this mode, the attackers make no virtual hnks between the legitimate nodes. Instead, they participate in the routing as legitimate nodes and use the worm- hole to deliver the packets sooner and/or wi th a smaller number of hops. As in the hidden mode, the attackers can drop data packets after being included in the route between the source and the destination. In this chapter, we analyze the effect of the wormhole attack on shortest- path routing protocols. When the nodes are uniformly distributed, we show that strategic placement of a single wormhole can disrupt on average 32% of the communications across the network. However, we show that (n ^ 2) attackers cannot disrupt on average more than (1 - ^) of al l of the com- munications. We also analyze the effect of the wormhole attack in which the malicious nodes target a specific node (such as the sink node in a wire- less sensor network). In this scenario, we show that two attackers can dis- rupt /contro l 30% to 90% of al l communications between the target node and the other nodes in the network. We explain how three malicious nodes can disrupt/control almost al l of the communications independent of target node location in the network. A l l analytical results are further confirmed by simulation. The wormhole attack may have difi'erent effects on different network topologies. We show how to compute the maximum effect of the worm- hole attack on a given network topology. We then evaluate the maximum effect of the wormhole attack on grid network topologies. For these networks, we show that the wormhole attack can disrupt/control about 40% to 50% of a l l communications if the attackers strategically place the wormhole. Final ly , we propose a timing-based countermeasure against the wormhole attack that is an improvement over existing schemes based on t iming analysis. Using the proposed solution, the nodes do not need to have synchronized clocks, and are not required to predict the sending time or to be capable of fast switching between the receive and send modes. Moreover, the nodes do not need to communicate wi th all their neighbors one-to-one. We show that the proposed countermeasure can be used together with one of the recently proposed countermeasures in order to improve the probability of detection. The rest of the chapter is organized as follows. In Section 4.2, we present and categorize related work on the subject. In Section 4.3, we introduce a new analytic model to measure the effect of the wormhole attack and present analytical and simulation results. In Section 4.4, we show how to compute the maximum effect of the wormhole attack on a generic network. We propose a countermeasure based on t iming analysis and compare it wi th the existing timing-based solutions in Section 4.5. A summary of this chapter is presented in Section 4.6. 4.2 Related Work The existing countermeasures against the wormhole attack can be divided into proactive and reactive countermeasures. Proactive countermeasures at- tempt to prevent wormhole formation, typically through specialized hard- ware used to achieve accurate time synchronization or time measurement, or to transmit maximum power in a particular direction. Among proactive countermeasures, timing-based solutions attempt to restrict the maximum distance between two neighbors by computing the packet travel time. For example, in [50], the authors introduced packet leashes as a countermea- sure against the wormhole attack. In their method, the sender adds the transmission time to the packet in order to restrict the packet's maximum transmission distance. In [51], the authors showed how to estimate the dis- tance without having a tight synchronization between the nodes. In this scheme, each node can estimate the distance to another node by sending a challenge bit and receiving its instant response. A similar approach was used in [53] for secure single-hop pairwise time synchronization. In practice, al l of the aforementioned timing-based methods suffer from some of the following shortcomings. • The nodes require tightly synchronized clocks; • each node has to be capable of fast switching between the receive and send modes; • each node needs one-to-one communication with al l its neighbors; • each node requires predicting the sending time and computing signature while having to timestamp the message with its transmission time. In Section 4.5, we show that our proposed timing-based countermeasure does not have any of these shortcomings, thus is more suitable for practical i m - plementation of solutions based on packet travel time measurements. Location information can also be used in packet leashes in order to defend against the wormhole attack [50]. A practical proactive method based on location information is proposed in [54]. In [55], a small fraction of the nodes called guards have access to location information. These nodes monitor local traffic looking for a wormhole. Directional antennas can also be used to mitigate the wormhole attack [52]. In this approach, the transmitter shares its directional information with the receiver. The receiver can prevent the wormhole endpoint from masquerading as a false neighbor by detecting the direction of the arrived signal and comparing it with the directional information provided by the sender and by finding a correctly positioned verifier node. A wormhole may also be avoided by extracting the sending device's radio fingerprint and verifying whether the radio signal originated from a legitimate device [56 . There are also some proactive countermeasures which do not rely on any specialized hardware. For example, recent work [57] explains how to use the local connectivity information to detect wormhole attack. We wi l l show in this chapter that their approach does not work if the malicious nodes selectively forward the Hello messages. A typical drawback of most of the aforementioned proactive schemes (except that proposed in [57]) is that they cannot detect a wormhole running in the participation mode. This is due to the fact that they often attempt to prevent wormholes between two legitimate nodes; however, in the participation mode, the wormhole is formed between two malicious nodes participating in the routing. Note that in this mode, al l the links are valid except the one (the wormhole) between the two attackers. Reactive countermeasures, on the other hand, do not prevent the worm- hole formation. For example, the proposed source routing protocols in [58 and [59] consider the wormhole as a valid l ink and avoid it only if it exhibits some malicious behavior like modifying or dropping packets. This is achieved using some basic mechanisms such as packet authentication and destination acknowledgment. Unlike proactive schemes, the existing reactive counter- measures are not able to avoid the wormhole if it is employed for an invisible (passive) attack such as a traffic analysis attack. Therefore, some other tech- niques such as anonymous communication have to be used to defend against passive attacks. 4.3 Wormhole Attack Analysis The wormhole attack can severely affect routing protocols based on short- est delay and shortest path by delivering packets faster and with a smaller number of hops, respectively. The common belief is that the wormhole at- tack can prevent nodes from discovering other nodes that are more than two hops away when it is used against on-demand routing protocols [50, 60]. We carefully analyze the effect of the wormhole attack on shortest-path routing protocols, w i th the objective of drawing a more precise picture of the average or maximum potential damage of wormhole attack. Throughout this section, we assume that the attackers use the same type of antenna as other nodes in the network and have the advantage of having direct links to each other. We also assume that the network is static. In mobile ad hoc networks, the number of affected communications varies over time. Moreover, a particu- lar communication can be controlled by the attackers at a certain period of time and can become out of their control at other periods. However, a net- work can be seen as a sequence of many different static networks obtained by sampling the network over a given time interval. Clearly, the number of samples increases as the time interval becomes larger. Therefore, as the time interval becomes larger, the average number of affected communications over the interval wi l l approach the average number of affected communications in static networks. In this section, we first show how to approximate the length (number of hops) of the shortest path between two nodes in a homogeneous dense net- work. We then use this approximation to analytically evaluate the average effect of the wormhole attack for two different scenarios. In the first scenario, the main objective of the malicious nodes is to disrupt/control as many com- munications as possible in the network. We show that on average every node is st i l l able to communicate with at least 50% of a l l the other nodes across the network if two malicious nodes launch a wormhole attack. However, the analysis shows that two attackers can disrupt/control about one-third of al l communications if they strategically place the wormhole. In the second sce- nario, two malicious nodes select and attack a target node such as the sink node in a wireless sensor network. The main objective of the attackers in this scenario is to disrupt/control the communications between the target node and a l l other nodes in the network. For this scenario, we show that the attackers can control most of the communications if the target node is around the boundary of the network. 4.3.1 Approximating the Length of the Shortest Path Consider a network consisting of a large number of nodes distributed uni - formly with density S inside a disk of radius R. Suppose each node is equipped with an omni-directional antenna wi th wireless transmission range of T. We assume that there is a link between two nodes if their distance is less than or equal to T. In this case, the network topology can be represented by a unit disk graph. Let us define ds,D (or SD) as the distance between nodes S and D, and Ns,D as the length (#hops) of the shortest path between them. Clearly, we have Ns^o > "-f. (4.1) L e m m a 4.1. In a network with limited diameter and high node density, with high probability we have Ns,D ^ Proof. The number of nodes in a region TZ w i th area A-ji follows a Poisson distribution [61], since they are uniformly and independently distributed. It follows that ^ P(7^ contains k nodes) = e'^^^^^^f'' , (4.2) k\ where 5 is the density of nodes inside the network. If ds,D ^ f , then there are t = [ 2 % ^ J - 1 disks with radius and origins at distances di = '^i + 1 ^ i ^ t, from S on the line going through S and D. This is illustrated in Figure 4.1. Using (4.2), we get P(at least one node in each disk) = ( l - P ( n o node in a disk))* = (l-e"*^''^?)^^)*. Clearly, the distance between two nodes in adjacent disks is at most T. Therefore, there is a path of length t -I-1 = [2^|;^J wi th probability at least (1 _ e-^('^(?)'))*. Consequently, we have NS,D ^ [ 2 % ^ J ^ 2 % ^ wi th high probability when M.(T,2,, , l n ( l 2 % ^ J - l ) e-<5W4) ))f « 1 or 5 » ^, 7 r ( i ) ' where ds,D ^ 2i?. Note that the assumption of uniform distribution is not a necessary condition. In other words, the same result can be obtained if Pq « ^ , where Pq is the probability of having no node in a disk with radius J and with the origin inside the network. • Prom (4.1) and Lemma 4.1, we observe that Ns^d is a function of and can be approximated by Ns,D = P ^ , (4.3) where 1 ^ /? ^ 2. Figure 4.1: F inding a path between 5" and D. 4.3.2 Targeting all of the nodes in the Network As mentioned earher, in this scenario, the mahcious nodes target al l of the nodes in the network in an attempt to disrupt/control as many communi- cations as possible. Suppose that the wormhole attack is launched in the hidden mode by two malicious nodes Mi and M2. Thus, there is a v irtual link between every pair of nodes locating in the transmission ranges of Mi and M2. We assume that the malicious nodes can control the communication between two nodes S and D if and only if the shortest path between them includes a virtual link. In this case, the communication between nodes S and D goes through the mahcious nodes Mi and M2, thus it can be disrupted or controlled by them. The following lemma shows how to model the effect of the wormhole attack using (4.3). L e m m a 4.2. The attackers Mi and M2 can control the communication be- tween the nodes S and D if min {ds,Mi + dD,M2,ds,M2 + dD,Mi) ^ ds,D- Proof. The path through Mi and M2 (or M2 and M i ) looks shorter than the actual shortest path between S and D if and only if min {Ns,M^ + Ndm2 ~ 1- Ns,m2 + Nd,MI - 1) < Ns,d- Using (4.3) we get min ( / 3 ^ + / ? ^ , + / ? ^ ) ^ thus min {ds,Mi + «^D,M2) C?5,M2 + do,Mi) ^ <^5,£)- When the malicious nodes are on the path, they can analyze the traffic or disrupt the communication by, for example, dropping the route reply or data packets. • Let us assume that the malicious nodes Mi and M2 are located at the coordinates (—m,0) and (Tn,0), respectively. As shown in Figure 4.2 , the perpendicular bisector / of the line segment M1M2 partitions the network into two regions 7li and TZ2 containing Mi and M 2 , respectively. Figure 4.2: Partit ioning the network into regions TZi and 7̂ 2- L e m m a 4.3. Let S and D be two nodes both inside TZi or'JZ2- We have min {ds,Mi + C ? D , M 2 , ds,M2 + doMi) > '^s,d- Proof. Wi thout loss of generality, we can assume that both S and D are in TZy. Hence, {ds,M2 > ds,Mi) (<̂ Z),M2 > dD,Mi)- Therefore, using the triangle inequality, we get min {ds,Mi + dD,M2^ ds,M2 + dD,M\) > ds,Mi + dD,Mi ^ ^s^d- • Prom Lemmas 4.2 and 4.3 it follows that two nodes in the same region are able to communicate. The total number of possible communications between m » 1 nodes in a region TZ can be approximated as m m 2 Let m i and m2 be the number of nodes in region TZi and 7?.2, respectively. The attackers cannot disrupt on average more than 50% of al l of the com- munications across the network, because (7) + (7) rn\ + ml Definition 4.1. A region is called unreachable for a node S if it is inside the network and if for any node D in the region min {ds,Mi + dD,M2^ds,M2 + < ^ D , M I ) ^ ds,D- We denote the largest unreachable region for a node S as Us. From L e m m a 4.2, it follows that the wormhole attack can control/disrupt the communications between a node S and any node in Us- The following theorem gives more precise information regarding the severity of a wormhole attack init iated by two malicious nodes M\ and M2. Theorem 4.1. Let S be a randomly selected node in TZi and Aa^ be the area of Us- We have 1 where ^ 2{ds,M2COs{e)-ds,Miy 9{0) = ds,Mr cos{e + 7 ) + ^jR^-dli^^sm{e + 'y), 7 = /.OSM2, O is the origin of the network and the values 61 and 6^1 are the roots of the equations {g{9) — f{6) = 0 ) and {g{—0) — f{0) = 0), respectively. Proof Let D be a node in Us- According to Definition 4.1, min {ds,Mi + ^ D . M Z , ds,M2 + doMi) ^ ds,D- (4.4) Since the node S is in TZi, it follows from Lemma 4.3 that the node D is not in TZi. Therefore, min (ds,Mx + dD,M2^ds,M2 + C ^ D . M J = ds,Mi + C?D,M2- (4.5) Prom (4.4) and (4.5) it follows that ds,Mi ^ ds,D — dD,M2- The equation ds,Mi = ds^o - dD,M2 defines a branch of the hyperbola with foci S and M^. Therefore, as shown in Figure 4.3, Us is a region between the network boundary (a circle of radius R) and the branch of the hyperbola. Let us consider S as the origin and SM2 as the rr-axis of a polar coordinate system. Using the cosine rule for the triangles SM2E and SOF, we can compute f{9) and g{9), respectively. The area Au, can then be computed with rdrd9. m • Consider a polar coordinate system with origin O (the origin of the net- work) and X -ax is OM2. Let (r, a) be the polar coordinates of a node 5*. The expected value of Au^ can be calculated from ^i^us] = :;^Wf ^v,^,./drda. (4.6) r=0 As finding a closed form for (4.6) is difficult (if not impossible), we compute it numerically. Figure 4.4 shows the numerically computed £'[A(/J/(7ri?^). As shown in the figure, £'[A[/J/(7ri?^) is maximized when the attackers M i and M 2 are located at the coordinates (-0.33/?, 0) and (0.33/2,0). For the simulation, the radius of the network is set to R = \ and 500 nodes are ran- domly put inside the network. We run the simulation for the transmission ranges T = 0.2 and T = 0.15. In the simulation, a communication is con- sidered affected by the attack if the shortest path through the wormhole is shorter than the legitimate shortest path between the source and the destina- tion. The simulation is then repeated a few hundred times in order to obtain the average percentage of affected communications across the network. As shown in Figure 4.4, both the simulation and the analytical results indicate that two malicious nodes can disrupt 32% of al l communications across the network when they initiate a wormhole atta<;k. Now, consider the case where (n ^ 2) malicious nodes attack the network by making wormholes between each other. In this case, a malicious node can send packets to any other mahcious nodes using a path of wormholes. Clearly, this generalized wormhole attack can disrupt more communications across the network. The following theorem gives an upper bound on the average percentage of affected communications. Theorem 4.2. Let M i , M 2 , . . . , M„ 6e (n ^ 2) malicious nodes making wormholes between each other. On average, at least ^ of all communications across the network are not affected by the attack. Proof. As shown in F igme 4.5, the network can be partitioned into n regions or Voronoi cells [62] such that each cell contains exactly one malicious node and every point is closer to the mahcious node in its cell than the others. Let S and D be two nodes inside a cell with the malicious node Mg. Using the Voronoi cell definition and the triangle inequality, we have ds,D ^ ds,Mg + doMg < ds^Mi + doMj > where 1 ^ i , j ^ n and i j. Thus, the mahcious nodes cannot disrupt the communication of two nodes inside the same cell. Suppose mj is the number of nodes in the cell d- Using the Cauchy-Schwartz inequality, we get It follows that at least ^ of all of the communications are not affected by the attackers. • Figure 4.5: Partit ioning a network with several attackers into Voronoi Cells. 4.3.3 Targeting a Particular Node in the Network The malicious nodes may launch the wormhole attack to disrupt/control the communication between a target node and the other nodes in the network. For example, in wireless sensor networks, sensor devices typically collect data and send their reading to a sink node. Therefore, many-to-one communica- t ion can be a dominant flow in such networks. Using this fact, the malicious nodes can strategically choose their locations in order to maximize the dam- age to the sink node (the target node in this case). L e m m a 4.4. To maximize the number of disrupted/controlled communica- tions, one of the malicious nodes must be placed in the transmission range of the target node. Proof. Suppose that the malicious nodes Mi and M2 are located at distance di and ^2 > di from the target node. Using Lemma 4.2, the malicious nodes can control the communication between a node A and the target node S if min {dA,Mi + ^2, dA,M2 + di) ^ C^A,5- Since ^2 > rfi, we have C J A . M J +C?2 > d^^Mi+di. Using the triangle inequality, we get dA,Mi + di > d^^s- Therefore, Consequently, di (or equivalently the number of hops between Mi and the target node) has to be minimized in order to maximize the number of con- Now, suppose that Mi is in the transmission range of the target node. The malicious nodes can control the communication between a node A and the target node S i f Na,m2 < Na,s- In this case, the length of the shortest path though M2 and Mi is Na,m2 which is smaller than the length of the actual shortest path, i.e., Na,s- Using (4.3), the attackers can control the communication between A and S if A s shown in Figure 4.6, the perpendicular bisector of the line segment SM2 partitions the network into two regions TZs and TZm containing S and M 2 , respectively. Clearly, Inequahty 4.7 holds for any node A inside the region TZm- Therefore, to maximize the damage, the malicious node M2 has to be close to the target node. However, M2 should maintain a minimum distance dmin from the target node S. It is because for any node A inside TZm we have dA,s—dA,M2 ^ <^S,M2- Therefore, ^ ^ , 5 % ^ A . A / g when ds,M2 is small and thus Na,s = Na,M2 wi th high probability. Note that when Na,s = Na,m2 , the malicious nodes may not take the control over the communication between A and S. For example, M2 and S would receive al l the messages at the same time if they are very close together. Clearly, the wormhole attack would not be effective in this case. L e m m a 4.5. For the fixed location of the target node S and the fixed distance SM2, the area of TZm is maximized when M2 and S are on a diagonal of the network. Proof. The area of circular sector (the region between a chord and a circle) can be computed as min (dA,Mi + c?2, C ? A , M 2 + <̂ i) < <^A,S dA,M2 + di ^ dA,s- trolled communications. • dA,M2 < dA,s- (4.7) (4.8) where a = arccos ( -^) and -R ^ h ^ Ris the distance between the center of circle and the chord of the sector. Note that each chord partitions the circle into two sectors. Equation (4.8) gives the area of the smaller sector when h is negative and the area of the bigger sector when it is positive. A s shown in Figure 4.6, the line containing S and M2 crosses the circle (the network boundary) at points P and Q. Let the chord P'Q' be the per- pendicular bisector of the line segment SM2 and U and V be the midpoints of line segments SM2 and PQ, respectively. The center of circle is on the perpendicular bisector of the line segment PQ. Therefore, the distance be- tween the center of circle and the chord P'Q' is equal to the distance between U and V and can be computed as h = UV = PQ _ rPM2 + PS\ _ /QS + PS\ _ rPM2 + PS QS~PS\ {PM2-PS\ fQS-PS\ d where dmin = SM2 is the distance between S and M2. Using the triangle inequality for the triangles SOQ and SOP we get QS ^R + ÔS and FS^R~ÔS. Therefore, based on (4.9), h is maximized when 5" and M2 are on a diameter of the circle. In this case, we have h = Ô S - ^ . (4.10) • Using (4.8) and (4.10), we can estimate the ratio of the number of communi- cations controlled by the attackers over the total number of communications as / 2a-sin(2a)\ p 2 , , I, 2 )^ 2 a - s i n ( 2 a ) (4.11) where a = arccos( S " ^ ) - To obtain (4.11) we used Approximation (4.3). Without using (4.3) it is possible to show that (4.11) is an upper bound for the ratio of the number of communications that can be controlled on average by two malicious nodes. Suppose TZc is the region composed of TZs and its reflection in respect to Q'P'. Note that the region TZc is symmetric with respect to M2 and S. Therefore, the malicious nodes cannot control on average more than 50% of the communications between S and the nodes inside TZc- Suppose that the malicious nodes can control al l of the communications between S and the nodes outside TZc- Thus, the ratio of the number of communications controlled by the attackers can be bounded by / 2a-sin(2Q;) \ D2 2 X A ( 7 ^ 5 ) AJTZm) - AjTZs) A(7^^,) j ^ (4.12) where A (7^) denotes the area of region 71. A s shown in Figure 4.7, simulation results confirm the analytical results. For the simulation, the radius of the network is set to one and 500 nodes are randomly put inside the network. We run the simulation for the transmission ranges T = 0.2 and T = 0.15. The distance d^in is set to 2T and OS (the distance of the target node from the network center) is varied from 0 to 1 of 0.1 unit steps. As shown in Figure 4.7, both the simulation and the analytical results indicate that two malicious nodes can disrupt most of the communications between the target node and other nodes if the target node is located around the boundary of the network. Using our model, it can be easily shown that three attackers can control most of the communications independently of the target node location. As shown in Figure 4.8, this can be done by putting one of the malicious nodes ( M i in the figure) in the transmission range of the target node and the other malicious nodes on each side of the target node on the diagonal containing it. The shaded segments in Figure 4.8 show the umeachable region for the target node. In other words, the malicious nodes can control the communications between the target node and most of the nodes in the shaded segments, particularly the nodes that are far from the chords AB and A'B'. Figure 4.7: Percentage of affected communications to / f rom the target node. 4.4 Wormhole Attack Analysis for a Generic Network In the previous section, we analyzed the average effect of the wormhole attack where the nodes are distributed uniformly. Clearly, the wormhole attack can have different effects on different network topologies. In this section, we first show how to compute the maximum effect of the wormhole attack on a generic network. We then use the proposed approach to evaluate the effect of the wormhole attack on grid networks. A wireless network can be represented using a unit disk graph G(V, T) with vertex set V efi? and an edge vw e E{G{V, T)) whenever vw ^T. In Figure 4.8: Unreacliable region for the target node under attaclc of three malicious nodes Mi, M^ and M 3 . this model, V corresponds to the location of nodes and T to their transmission range. Given the location of the attackers in the network, we can compute the number of affected communications by considering al l the pairs of nodes and checking whether the shortest path between them contains the malicious nodes. However, without this information, we may need to consider a l l the possible locations of the attackers in order to compute the maximum effect of the wormhole attack. Suppose the effect of the wormhole attack is maximized when the attack- ers are located at positions Pi,P2 e H.^- Let us call a set of points S an inclusive set if there exists P{, P2 e S such that the effect of the wormhole attack w i th attackers located at P{ and P2 is the same as that of the case when they are located at P i and P2. Clearly, it is preferable to find an in - clusive set with small cardinality in order to reduce the size of the search domain. The following lemma shows how to generate an inclusive set of size 0{N^). L e m m a 4.6. Let V = {^1,^2) • • -VN} be the vertex set of a connected graph G, and C = {ci, C 2 , . . . Cjv} be the set of circles Ci centered at Vi with radius T. Suppose S is the set of all the intersections of any two circles in the set C. The set S is an inclusive set of size 0{N'^). Proof. Suppose the effect of the wormhole attack is maximized when the attackers are located at P i and P j . We show that there is a point P[ e S such that an attacker does not lose any of its neighbors if it is moved from Pi to P{. There are three possible cases for the point P i . 1. P i is located on the circumference of at least two circles in C ; 2. P i is located on the circumference of exactly one circle in C ; 3. P i is not located on circumference of any circle in C. For the first case, we set P{ = Pi. Suppose that P i is located on the circum- ference of exactly one circle Ci e C (Case 2). Since graph G is connected. Ci w i l l intersect wi th at least one circle. Therefore, P i can be rotated on the circumference of Cj unt i l it lies, for the first time, on an intersection of Ci and Cj e C denoted by P{. For the th ird case, we can shift P i towards a vertex v eV unt i l it lies on the first circle Cj at point P * . We set P{ = P* if P * is on the circumference of at least two circles. Otherwise, similar to the second case, we rotate P * on the circumference of Cj unt i l it lies, for the first time, on an intersection of d and Cj e C denoted by P[. Note that during the process of transferring P i to P{ for al l three cases, P i does not exit any circle. Therefore, we have ^ueV : uPi^T =^ uP{ ^ T. In other words, an attacker does not lose any of its neighbors (and thus its effect) if it is moved from P i to P / . The same process can be applied to the point P 2 to get P 2 . Note that the effect of attackers at P{ and P 2 cannot be more than that of attackers at P i and P 2 since in the latter case the attackers have maximum effect. Since P{ and P j are on the intersection of at least two circles, it follows that S is an inclusive set. Clearly the size of S is at most (^), so it is of size e ) ( i V 2 ) • Using Lemma (4.6), we can find optimal positions where the mahcious nodes can maximize the damage caused by the wormhole attack. However, finding the inclusive set S introduced in Lemma (4.6) may not be practical, as in practice, we may not have the location information of the nodes or their transmission ranges. Note that having the location of the nodes is important since determining whether an arbitrary graph is a unit disk graph is AfV- complete [63]. Therefore, it may be preferable to compute an approximation of the maximum damage of the wormhole attack when the nodes' location information is not available. One possible solution, in this case, is to use the vertex set V instead of an inclusive set to get a lower bound of the maximum damage. Using this approach, we do not need to have any information about the location of the nodes and their transmission ranges. Moreover, the size of the vertex set is less than the size of S, so the search domain is smaller. Clearly, we can always find u,v eV such that ÛP{^T and vP^ ^ T. Therefore, using V as an inclusive set, wi l l often lead to a good approximation of the maximum damage of the wormhole attack. A s an example, consider a simple grid topology network oi N = m x m nodes. In this topology, the length of the shortest path between two nodes u and V is equal to \ux — Vx\ + \uy — Vy\, where and denote the x- coordinates of the nodes u and v and Uy and Vy denote their y-coordinates. We evaluated the maximum damage of wormhole attack using simulation on a grid topology network of m by m. Simulation results indicate that the maximum damage occurs when the malicious nodes are located on the main diagonal of the grid. Figure 4.9 shows the percentage of maximum number of affected communications. A s shown in the figure, the wormhole attack launched by two malicious nodes can affect around 40% to 50% of al l of the possible communications in a grid topology network of m x m, where 8 m ^ 32. The simulation results indicate that the percentage of maximum number of affected communications decreases as the total number of nodes increases. B 0.4 10 15 20 26 30 Total numlier of row* (columns) In the gird Figure 4.9: Percentage of maximum number of affected communications in a grid topology network. 4.5 Wormhole Attack Countermeasure As mentioned in Section 4.2, the existing wormhole countermeasures can be divided into proactive and reactive countermeasures. Proactive countermea- sures typically use time of flight, geographical position or signal direction information to prevent wormhole formation. These techniques often require specialized hardware and can achieve a high probability of detection. Some proactive countermeasures are able to detect wormholes in certain scenarios without using specialized hardware. For example, using the algorithm pro- posed in [57], each node can detect a wormhole by analyzing its local neighbor information. However, we wi l l show in this section that this method fails if the attackers selectively forward the Hello messages. In contrast to proactive countermeasmres, reactive countermeasures can prevent the wormhole attack launched in either hidden or participation mode. However, they do not pre- vent the formation of wormhole and do not avoid the wormhole if it is used for an invisible (passive) attack such as the traffic analysis attack. In this section, we propose a proactive countermeasure based on timing analysis. T iming analysis techniques are based on the fact that a packet can travel at most at the speed of light. Therefore, a node can estimate its distance to a sender by multiplying Packet Travel Time {PTT) by the light speed (c). The existing methods to compute PTT can be divided into two classes of synchronous and asynchronous methods. The synchronous methods are based on accurate time synchronization. For example, in the method proposed in [50], each sender stamps the packet wi th the time at which it is sent. The receiver can then compute PTT by comparing the time stamp with the time at which it receives the packer. Clearly, this method requires the nodes to have tightly synchronized clocks. Moreover, the sender needs to know the precise sending time which may not be possible in , for example, medium access control protocols based on C S M A [50 . Asynchronous methods do not require time synchronization. These meth- ods typically compute PTT using a few rounds of message exchanges. For example, a node A can compute PTT by comparing the time at which it send a packet to a node B to the time at which it receives an instant response from B. In [51], PTT is computed through a series of fast one-bit exchanges. This method requires fast switching between the receive and send modes. In 54], the authors proposed a similar asynchronous method that does not need fast switching and requires only minor changes in I E E E 802.11-capable hard- wares. In this method, link verification is performed in two phases. In the first phase, the nodes exchange nonces (i.e., randomly generated numbers) v ia a single R T S - C T S - D A T A - A C K exchange. In the second phase, they mu- tually authenticate themselves by signing and transmitting their respective nonces. One of the common drawbacks of the aforementioned asynchronous meth- ods is that they need to verify the vicinity of each neighbor one-by-one. In this section, we propose a new asynchronous method that does not have the drawbacks of the previous methods. Using our proposed method, the nodes do not need to have synchronized clocks, and are not required to predict the sending time or to be capable of fast switching between the receive and send modes. Moreover, the nodes do not need to communicate wi th a l l their neighbors one-to-one. It is only assumed that each node is able to record the time at which a packet is fully sent/received. Using our scheme, each node can validate vicinity of al l its neighbors in two rounds of communication. In the first round, each node sends a signed Hello message containing its id and a nonce, and records the time at which the message is fully sent. It foUows that after the first round, each node has a list of al l its potential neighbors. In the second round, each node signs and sends a follow-up packet. The follow-up packet includes the time at which the node's Hello message was sent (in tlie first round), the list of aU the ids in the received Hello mes- sages together with their corresponding nonces and the times at which they were received. Nonces are used to prevent malicious nodes to masquerade a legitimate node. Note that neither Hello messages nor follow-up packets are timestamped with their transmission time. Therefore, the nodes do not require to compute a signature while having to timestamp the packet wi th its transmission time. Suppose that node A receives 5 ' s Hello message after sending its own. When A receives a follow-up packet from B, it first checks its correspond- ing nonce in the packet and verifies 5 ' s signature. It then accept B as its neighbor if {tA,B - JA) - jtB - tB,A) ^ rp / . 1 X C ^ Tmax, (4.13) where tx is the sending time of x's Hello message recorded by x, t^^y is the receiving time of y's Hello message recorded by x and T^ax is the maximum transmission range. Node A considers S ' s Hello message as a response to its Hello message. The term {tA,B — ^ A ) indicates the time it takes to get the response. However, 5 ' s Hello message is not an immediate response. Therefore, A subtracts ( Ï B — ^ B . / I ) , the delay at node B, from {tA,B — * A ) . Note that A extracts tB,A and te from B ' s follow-up packet. To derive (4.13), it is assumed that node A receives B's Hello message after sending its own. If A sends its Hello message after receiving B's then A considers B as neighbor if itB,A - ts) - (JA - JA^B) 2 ^C^Tmax. (4.14) It is worth mentioning that a node A can estimate the distance between its neighbors B and C using similar equations as (4.13) and (4.14). It is because al l the information used by 5 or C to estimate dB,c is available in 5 ' s and C ' s follow-up packets. After the second round, each node has a hst of al l its 2-hop neighbors. Therefore, it can employ the Maheshwari's algorithm [57] to further check the existence of a wormhole. Maheshwari's algorithm uses local neighborhood information to find a forbidden structure. The algorithm is based on the fact that inside a fixed region it is not possible to pack too many nodes without having edges between them. Using simulation, the authors show that the algorithm can detect wormhole with a 100% detection and 0% false alarm probabilities. However, Proposition 4.3 shows that the algorithm cannot detect a wormhole if the malicious nodes only forward the Hello messages of those node which are at most | away from an end of wormhole. The malicious node may do selection based on the power of received packet. In other words, they can only forward packets with power higher than a specific threshold. Note that selectively forwarding packets can increase the delay of transferring a packet from one end to the other end of the wormhole. Therefore, this attack can be prevented if Maheshwari's algorithm is used together with our proposed scheme. Theorem 4.3. Suppose that the length of wormhole is at least (2 + V 3 ) r and the malicious nodes only forward the Hello messages of the nodes that are at most ^ away from one end of wormhole. In this case, Maheshwari's algorithm is not able to detect the wormhole if it uses 2-hop neighbor infor- mation. 4.6 Summary In this chapter, we investigated the effect of the wormhole attack on shortest- path routing protocols. We showed that two strategically located attackers can disrupt on average 32% of al l communications across the network, when the nodes are distributed uniformly. We also studied the effect of the worm- hole attack launched by n ^ 2 malicious nodes and showed that on average at least ^ of a l l communications are not affected by the attack. We considered the scenario in which the malicious nodes attack a target node in the network. For this scenario, we showed that two malicious nodes can disrupt/control on average 30% to 90% (based on the location of the target node in the net- work) of al l communications between the target node and al l other nodes in the network. We also evaluated the effect of the wormhole attack on grid topology networks. In these networks, we showed that wormhole attack can disrupt /control about 40% to 50% of al l communications if the wormhole is strategically placed on the diagonal of the network. Finally , We proposed a timing-based solutions to defend against the wormhole attack. We showed that, using our proposed solution, nodes need less requirements (compared to the existing timing-based countermeasures) to detect false neighbors. More- over, we showed that the proposed solution can be used to strengthen one of the recently proposed novel countermeasures. Bibliography 50] Y . C. H u , A . Perrig, and D. B . Johnson, "Packet leashes: A defense against wormhole attacks in wireless ad hoc networks," In Proc. of IEEE INFOCOM, 2003. [51] S. Capkun, L . Buttyan, and J . P. Hubaux, " S E C T O R : Secure tracking of node encounters in multi-hop wireless networks," In Proc. of the first ACM workshop on Security of ad hoc and sensor networks, 2003. 52] L . H u and D. Evans, "Using directional antennas to prevent wormhole attacks," In Proc. of Network and Distributed System Security Sympo- sium, 2004. [53] K . Sun, P. Ning , C. Wang, A . L i u , and Y . Zhou, "TinySeRSync: Se- cure and resilient time synchronization in wireless sensor networks," In Proc. of the 13*'' ACM Conference on Computer and Communications Security, 2006. 54] J . Eriksson, S. V . Krishnamurthy, and M . Faloutsos, "Truehnk: A prac- t ical countermeasure to the wormhole attack in wireless networks," In Proc. of IEEE International Conference on Network Protocols, 2006. 55] L . Lazos, R. Poovendran, C. Meadows, P. Syverson, and L . W . Chang, "Preventing wormhole attacks on wireless ad hoc networks: a graph theoretic approach," In Proc. of IEEE WCNC, 2005. [56] K . Rasmussen and S. Capkun, "Implications of radio fingerprinting on the security of sensor networks," In Proc. of IEEE SecureComm, 2007. 57] R. Maheshwari, J . Gao, and S. R. Das, "Detecting wormhole attacks in wireless networks using connectivity information," In Proc. of IEEE INFOCOM, 2007. 58] B . Awerbuch, D . Holmer, C. Ni ta -Rotaru , and H . Rubens, " A n on- demand secure routing protocol resilient to byzantine failures," In Proc. of ACM Workshop on Wireless Security (WiSe), 2002. [59] I. Avramopoulos, H . Kobayashi, R. Wang, and A . Krishnamurthy, "Highly secure and efficient routing," In Proc. of IEEE INFOCOM, 2004. 60] I. K h a l i l , S. Bagchi, and N . B . Shroff, " L I T E W O R P : A lightweight countermeasure for the wormhole attack in multihop," In Proc. of the International Conference on Dependable Systems and Networks, 2005. [61] A . Papouhs, Probability and statistics. Prentice-Hall , Inc., 1990. 62] M . de Berg, M . van Kreveld, M . Overmars, and 0 . Schwarzkopf, Com- putational Geometry: Algorithms and Applications, 2"̂ * ed. New York: Springer-Verlag, 2000. [63] H . Breu and D . Kirkpatr ick , "Un i t disk graph recognition is N P - h a r d , " Computational Geometry, vol. 9, no. 1-2, pp. 3-24, 1998. Chapter 5 Double Point Compression with Applications to Speeding up Random Point Multiplication 5.1 Introduction In cryptographic protocols based on elliptic curve cryptography [64], it is often necessary to transmit or store elliptic curve points [65]. A n elliptic curve point can be represented as P = ix,y), where x is the x-coordinate and y is the y-coordinate. However, it is desirable to represent a point using a compact representation in order to reduce the required bandwidth/memory. One tr iv ia l way to do this is to represent a point by its x-coordinate and an additional bit . The elliptic curve equation is a quadratic equation in y, thus given x we can obtain at most two possible solutions of y. The additional bit can then be used to specify the actual y-coordinate. Solving the quadratic equation requires a square root operation. Therefore, this technique is not practical when the square root operation is computationally expensive. In this case, an elliptic curve point is typically represented by both its x-coordinate and y-coordinate. In the first part of the chapter, we introduce a novel double point compres- sion scheme which allows a compact representation of elliptic curve points without the computational cost associated with ordinary single point com- pression. We also extend double point compression to triple point compres- sion in order to get more savings. Using the proposed double point and triple point compression schemes we can save about 25% and 33% of the band- width/memory, respectively. Moreover, the compression process of the pro- posed schemes requires almost no computational effort, and decompression A version of this chapter has been pubUshed. M . Khabbazian, T . A . Gulliver and V . K . Bhargava, Double Point Compression with Applications to Speeding up Random Point Multiplication, IEEE Transactions on Computers, vol. 56, no. 3, pp. 305-313, 2007. involves no square root operations. The proposed point compression schemes can be tr iv ial ly used to compress multiple points. In this case, Montgomery's trick for simultaneous inversion [66] can be employed to significantly reduce the decompression cost by replacing almost each field inversion with three field multiplications. The second part of the chapter deals with speeding up random point mul - tiplication. Point multiplication, kP, is a fundamental operation which dom- inates the execution time of elliptic curve cryptosystems. Significant research effort has been spent on reducing the time needed to perform this operation. There are different types of point multiplication algorithms including fixed point multiplication algorithms and random point multiplication algorithms. F ixed Point Mult ip l icat ion ( F P M ) algorithms are used when a fixed base point is multiplied several times. In this case, a lookup table can be gener- ated once and used every time a multiplication of the base point is required. Random Point Mult ipl icat ion ( R P M ) algorithms, on the other hand, are de- signed for the case where the base point is multiplied only once. To speed up the operation, these algorithms typically use low average Hamming weight integer representations such as K ; - N A F (see [67]) and the representation pro- posed in [68]. In this chapter, we extend R P M algorithms to the case where the base point is multiplied only once and we are allowed to have some limited extra information regarding the base point. We refer to the new algorithms as Part ia l ly Random Point Mult ip l i cat ion ( P R P M ) algorithms. We introduce the first P R P M algorithm which uses MoUer's algorithm [69] in its evalua- tion stage. We speed up the precomputation stage of the algorithm using Montgomery's trick for simultaneous inversion. We then compare the perfor- mance of the proposed P R P M algorithm with a standard R P M algorithm for different integer representations and show that a significant speed up can be obtained at the cost of slightly higher required bandwidth. We also show that a substantial speed improvement can be obtained when multiple processors are available. Note that this technique can be used to speed up point mul t i - plication in any devices, particularly those with constrained computational power or servers overloaded with elliptic curve encryption or key agreement requests. In this case, the proposed point compression techniques can be employed to reduce the required bandwidth when single point compression is not practical. The remainder of the chapter is organized as follows. In Section 5.2, we briefiy summarize elliptic curve operations. In Section 5.3, we propose a dou- ble point compression algoritl im and extend it to triple point compression. In Section 5.4, we review some of the best fixed and random point mult i - plication algorithms and explain how to extend random point multiplication algorithms. We introduce a partially random point multiplication algorithm in Section 5.5 and show how to accelerate its precomputation stage. We also analyze the performance of the proposed algorithm and show that a sub- stantial performance improvement in speed can be obtained when multiple processors are available. Finally , we present a summary in Section 5.6. 5.2 Elliptic Curves: Definition and Operations A n elliptic curve E over the field F is a smooth curve in the so called "long WeirestraB form" E : + aixy + asy = + a2X^ + a^x + ae, (5.1) where o i , . . . , ag e F . Let CharÇF) denote the characteristic of the field F . Equation (5.1) can be simplified to E-.y^ = x^ + ax + b, (5.2) and E : y^ + xy = x^ + ax^ + 6, (5.3) when Char{F) 2, 3 and Char{F) = 2, respectively Let E{F) be the set of points P = {x,y) e F ^ that satisfy the elhptic curve equation (along with a "point at infinity" denoted O). It is well known that E{F) together with the point addition operation given in Table 5.1 form an abelian group. When the two operands are equal, i.e. P i = P j , the op- eration is called point doubling. As shown in Table 5.2, point inversion in this group can be computed easily. Thus, point subtraction has virtual ly the same cost as point addition. Note that in Tables 5.1 and 5.2, the points P i = ( 2 ; i , y i ) , P 2 = ( x 2 , 2 / 2 ) and P 3 = (0:3,2/3) are represented by affine coor- dinates. Alternative coordinates such as projective coordinates or Jacobian coordinates can be used to avoid field inversion when field inversion is much more expensive than field multiplication. Point multiplication is defined as repeated addition kP = P + P + ... + P, k times where P is an eUiptic curve point, A; G [1, AT - 1] is an integer, and N is the order of point P. Char{F) = 2 Pi ^ ±P2 X2+X1 X3 = + X + xi + X2 + a yz = {xi + X3)X + yi + X3 Pl = P2 xz = X'^ + X + a y3 = {Xi + X3)X + yi+X3 Char{F) ^ 2 , 3 Pi ^ ±P2 X2-XI X3 = X"^ - Xi - X2 = {xi - X3)X - yi Pl=P2 , 3x(+a X3 = X^ — 2xi ys = {xi - X3)X - yi Table 5.1: E l l ip t i c curve point addition, P3 = Pi + P2. Char{F) = 2 -Pi = (a;i,a;i - l -y i ) Char(F) ^2,3 -Pi = {xi, -yi) Table 5.2: Elhpt ic curve point inversion. 5.3 Point Compression Using single point compression, an elliptic curve point P = {x,y) can be represented by its x-coordinate and an additional bit. This is because given x, the elliptic curve equation becomes quadratic in y. The quadratic equation has at most two solutions, so one bit is sufficient to specify y (the additional bit is not required when Char{F) = 2 and P has odd order [70]). For example, for the case of Fp , we have y'^ = x^ + ax + b = x{x^ + a) + h. Therefore, given x and an additional bit, y can be obtained at the cost of 1M+1S+ I S R , where M , S and SR denote the cost of a field multiplication, a field squaring and a square root operation, respectively. The main drawback of the single point compression scheme is that it is not practical when square root operation is expensive. For example, to obtain a square root of a modulo a prime p ^ 3 mod 4, we need to compute a V mod p, which requires Q{\ogp) field multiplications/squaring. In this case, the elhptic curve points are typically represented by both their x-coordinate and ^-coordinate to avoid the overhead of computing square root operation. In this work, we present two novel point compression schemes that do not require any square root operation. 5.3.1 Double Point Compression In some cases, such as the elliptic curve E l G a m a l encryption [71] and the proposed technique in Section 5.4, we are required to transmit/store multiple points. In these cases, we can use double point compression as given in Proposition 5.1 below to reduce the required bandwidth/memory by about 25%. Note that decompression does not require a square root operation. Therefore, the proposed double point compression algorithm can be used when single point compression is not practical. Theorem 5.1. The elliptic curve points Pi = {xi,yi) and P2 = (x2,y2) can be represented by at most three field elements and an additional bit. Proof. Suppose Char{F) 7^ 2,3 and yi + y2 ^ 0. The points P i = {xi,yi) and P2 = (2:2,2/2) can be represented by {xi,X2,yi + 2/2)- Given Xi, X2 and Vi + y2 = A, we can obtain yi and y2 as 2/1 = ^ + {8A)-\xi - X2) {3{xi + X2)^ + {xi - X2f + 4 a ) , (5.4) and y2 = A-yi. (5.5) This is because, using (5.2), we have - + {8A)-\xi - X2) (3(xi + x^f + (rci - X2f + 4 a ) = - + ( 8 ^ ) - ^ X 4 ({x\ -h axi + h)- {xl + ax2 + b)) = I + ( 8 ^ ) - ^ X 4{yl - vl) 2/1 + 2/2 , 2/1 - 2/2 Therefore, computing both yi and 2/2 costs 2M + 2S + I, where / denotes the cost of a field inversion. In other words, decompressing each point costs M + 5 + 0 . 5 / . When 2/1 + 2/2 = 0, we can represent the points simply by {xi, X2,2/1) as t/2 = —2/1 • Clearly, decompression requires almost no computational effort in this case. A n additional bit can be used to distinguish between the two cases 2/1 + 2/2 7^ 0 and 2/1 + 2/2 = 0. Now, suppose that Char{F) = 2 and X1+X2 0. The points Pi = {xi, 2/1) and P2 = (3 :2 , 2 / 2 ) can be represented by {xi,X2,yi + 2 /2)- Given xi, X2 and 2/1 + 2/2 = A, we can obtain yi and 1/2 as 2/1 = ((a + a;2)(a;i + X2) + xj) + A{A + X2){xi + X 2 ) - \ and 2/2 = >1 - 2/1 (or 2/2 = ^ + 2/1 since Char{F) = 2). This is because, using (5.3), we have ((a + X2){xi + X2) + xj) + y l (A + X2)(xi + ^ 2 ) " ^ = {xl +xl + ax\ + a 2 ; ^ ) ( 2 ; i + xz)"^ + (2/? + 2/2 + 2/1^^2 + 2/2a;2)(2 ; i + 3 : 2 ) ' ^ = ((2/1 + + axj + b) + ( 2 / 2 + 0:2 + « 2 : 2 + 2/23̂ 2 + &) + 2/12^2) ( 2 ; i + X2)~^ = {yixi + 2/ia:2)(a;i + X2)~^ = 2/1- Therefore, computing both 2/1 and 2/2 costs 3M + 3 + 1, and decompressing each point costs 1 .5M + 0.55 + 0.5/. When X i + X 2 = 0 we can represent the points simply by ( x i , 2 /1) . This is due to the fact that xi+ X2 = 0, hence X l = X 2 as Char{F) = 2. Consequently, we have P2 = +Pi. A n additional bit is sufficient to distinguish between the two cases P2 = Pi and P2 = —Pi- For the case P2 = —Pi, we have 2/2 = 2 / i + ^ i (see Table 5.2), so decompression requires almost no effort. • 5.3.2 A n Extension to Triple Point Compression In this section, we extend double point compression to the case where three points are required to be transmitted/stored. We restrict ourselves to prime fields and show how to represent three points in a compact representation and save 3 3 % of bandwidth/memory. A similar approach can be used to compress three points on an elliptic curve defined over a binary field. Theorem 5.2. Suppose Char{F) ^ 2 , 3 . The elliptic curve points Pi = {xi,yi), P2 = {x2,y2) and P3 = {xz,yz) can he represented by at most four field elements and two additional hits. Proof. Let yi+y2 + y3 = A and + y l - yf - y l = B. Suppose yf ^ yj, Vz, ; e { 1 , 2 , 3 } , z ^ j and A 7^ 0. Therefore, we have 5 7̂  0 because B = A^+ yl-yl-yl^ 2(2 /3 + y i ) ( z / 3 + 2/2). In this case, the elliptic curve points P i , P2 and P3 can be represented as ( x i , a;2, X3,2/1 + Î/2 + 2/3 = A). Given Xi, X2 and X 3 , we can obtain 2/3 as + 4A^2/| - 42/1̂ 2/i = — 4 À B — ' ^^-^^ because B' + AA'vl - Ayfyl {B - 2 ^ 2 / 3 ) ^ + AABy^ - Ay\yl 4AB AAB , {A' + yl -y\- y\ - "^Ay^f - 4y\yl = y^ + 4ÂB ^ {2yiy2y-Ay!yl^ 4AB Note that yf can be obtained from Xi using ( 5 . 2 ) at a cost of M + 5". Having 2/3, we get 2/1 +2/2 = A-ya. Clearly, yi + ^ 0 as y\ ¥= y^. Therefore, we can obtain yi and ?/2 using (5.4) and (5.5), respectively. As the second case, assume yf # y'^, e { l ,2 ,3} ,z ¥= j and A = Q. Clearly, yi+y2 0, thus the points can be represented as {xi,X2, x^, 2 / 1 + 2 / 2 ) - We can use (5.4) and (5.5) to obtain yi and 2/2» respectively. Then 2/3 is ys = - ( y i + 2 / 2 ) . Now suppose that yi = 2/| and 2/| ^ vl for different integers i, j, k G {1,2,3}. Without loss of generality, we assume that yf = 2/2^ and 2/2 ^ 2/3- In this case, we represent the points as {xi,X2, X 3 , 2 / 2 + 2 / 3 ) - Clearly, 2 / 2 + 2 / 3 ^ 0 as 2/2 ^ 2/3- Thus, we can obtain 2/2 and 2/3 using (5.4) and (5.5), respectively. A n additional bit can be used to distinguish between the two cases 2/1 — 2/2 and 2/1 = - 2 / 2 - Final ly , suppose that 2 2 2 y i = 2/2 = 2/3- In this case, the points can simply be represented as ( x i , X 2 , X 3 , 2 / 1 ) . Two additional bits would then be sufficient to differentiate the cases 2/2 = yi, 2/2 = -yi and 2/3 = 2/1) 2/3 = - 2 / 1 - • Table 5.3 summarizes al l possible cases with the corresponding point rep- resentation and decompression cost. The conditions given in the second col- umn can be verified using (5.2) when we have X i , X 2 and X 3 . A lgor i thm 5.1 provides pseudo code for triple point decompression. Note that in Lines 8 and 9 of the algorithm, Montgomery's trick for simultaneous inversion is used to reduce the required number of field inversions from two to one. Final ly , it is worth mentioning that triple point compression requires almost no effort as the conditions given in Table 5.3 can easily be verified just by comparing the 2/-coordinates of the points. Algorithm 5.1 Triple Point Decompression Input: A 4-tuple {xi,X2, X3,T) and additional bits 61,62 e {0,1} Output : 2/1, 2/2 and 2/3 1: Compute for z = 1, 2, 3 and determine the condition 2: switch (condition) 3: case condition # 1 : 4: if {hi == 1) then 5: c^B' + ATVs - ^yfyl 6: D<- 2 ( (T + By - T 2 - B^) = 4TB 7: E^TD-C 8: D-^ ^ E{DE)-^ 9: E-^ <- D{DE)-^ 10: 2/3 ^ CD~^ 11: 2 / 2 - è ( ( y i - y ? ) i ^ ^ - ' + ^ - 2 / 3 ) 12: 2/1 <- T - 2/2 - 2/3 13: end if 14: if (hi == 0) then 15: yi^l{{y!-yl)T-'+T) 16: 2/2 * - T - 1/1 17: 2/3 < (2/1 + 2/2) 18: end if 19: end case {#!}: 20: case condition #2: 21: 2 / . - è ( ( 2 / . ^ - 2 / | ) r - l + T ) 22: Vj^T - 2/fc 23: 2/i ^ (26i - 1)% 24: end case {#2}: 25: case condition #3: 26: 2/2 ^ (26i - 1)2/1 27: 2/3 ^ (262 - 1)2/1 28: end case {#3}: # Condit ion Addi t ional Bi ts Point Representation Decompression Cost per Point 1 Vi ^ yf, where h = l ( a ; i , X 2 , a ; 3 , y i + 2/2 + 2 /3) ^ / + 4 M + 2S J. bi=0 {Xi,X2,X3,yi + 2 / 2 ) ^I + IM + S 2 yf = y] a n d ^ ^ yl bi = l {xi,X2,xs,yj +yk) ll + lM + S where 1 ^ i,j,k ^ 3 bi = 0 61 = 1,62 = 1 3 yf = 2/1 = 2/3 61 = 1,62 = 0 {Xi,X2,X3,yi) M + S 61 = 0 ,62 = 1 61 = 0,62 = 0 Table 5.3: Triple Point Compression. 5.3.3 Compressing Multiple Points The proposed point compression schemes can be used to compress multiple points. For example, when we have m, — 2u points, we can divide them into u pairs and compress each pair using the double point compression scheme. We can also use triple point compression to get more bandwidth/memory savings. Suppose that we need to transmit/store m ^ 2 points. Clearly, any integer m ^ 2 can be uniquely written in the form m, = 3v + 2u, where v ^ 0 and 0 ^ u ^2. Therefore, we can divide the points into v 3-tuples and u 2-tuples and compress them using the triple point and double point compression schemes, respectively. Note that decompressing each tuple requires one field inversion. Therefore, v + u simultaneous field inversions are required to obtain al l the y- coordinates. Montgomery's trick for simultaneous inversion can be employed to do this using one field inversion and 3{v + u — 1) field multiplications. This can significantly speed up the decompression process as a field inversion costs more than three field multiplications in most useful fields. 5.4 Point Multiplication In this section, we briefly present some of the best known fixed and random point multiplication algorithms. We then show how to extend random point multiplication algorithms to the case where the base point is variable but some l imited extra information is available. 5.4.1 Fixed point multiplication (FPM) Fixed point multiplication algorithms are designed for the case where a fixed point is multiplied by different multipliers a number of times. In this case, the F P M algorithms generate a lookup table once and use it every time a mult i - phcation of the point is required. L i m and Lee's algorithm [72] and Moller 's algorithm [69] are two of the best fixed point multiplication algorithms. In the L i m and Lee algorithm, the multiplier k is divided into hv subblocks of b bits l-l h-l / v - l \ u=Q i=0 \J=0 / where The points / 6-1 e„ 6 {0,1}, a = bv,b= [—], kij = cia+jb+t'^*. "-^ t=o h-1 h-1 ^UM = 2 6^2'"^'''^ foi^ O^j <v, where / = ^ ^^2' t=0 i=0 are then precomputed and stored in a lookup table, and used to compute kP as follows h-1 6-1 /v-l \ kP = Y,2' Y,^\-hM , w h e r e , = 2 ê a+,-6+t2\ t=0 \j=Q J i=0 MoUer's algorithm represents the multiplier k in w - N A F form (see [67]) and divides it into n subblocks of length s = [^]. It stores the points d{2^^P) for 0 ^ j < n and for al l odd integers 1 < d < 2'^~^ in a lookup table, and uses them to compute kP where h e {+1, + 3 , . . . , ±{2""-^ - 1)} u {0}. 5.4.2 Random Point Multiplication (RPM) Random point multiplication algorithms are designed for the case where the base point is multiplied only once. In this case, generating a lookup table is not practical since it is computationally expensive. There are many a l - gorithms to accelerate the computation of random point multiplication by reducing the required number of point additions [65, 73]. These algorithms usually consist of two stages, typically a precomputation stage and an evalu- ation stage. Algor i thm 5.2 is an example of such algorithms. The precompu- tation stage of this algorithm consists of two steps. In Step 1, the multipher k is receded to a ^-representation A; = 2 ki2\ Q^i<l where ki e 5 u { 0 } , I ^ [log2A/'] + 1 and 5 is a set of nonzero integers including 1. In Step 2, point multiphcations dP for the integers de B,d > 1 are computed and stored. In the evaluation stage, the information obtained from these two steps is used to compute kP. Note that Algor i thm 5.2 can be considered as a sliding window algorithm. In sliding window algorithms, the recoding process may be done in the evaluation stage. This happens when the recoding and evaluating processes scan the multiplier digits in the same direction. In this case, both the recoding and evaluating processes can be carried out simultaneously. Algori thm 5.2 Random Point Mult ip l icat ion ( R P M ) Input: A n integer k and a point P e E{F) Output : kP Precomputation Stage: 1: Compute the ^-representation of the multiplier k = Xlo<i<! ^^2% h e B u {0} 2: Compute and store dP for al l integers d e B, d > 1 Evaluation Stage: 3: R^O 4: for i from I — 1 down to 0 do 5: R^2R 6: if {ki > 0) then 7: R^R + kiP 8: else if {ki < 0) then 9: R^R- {-ki)P 10: end if 11: end for 12: return R The integer representation of the multiplier plays an important role in the performance of the R P M algorithm. Some useful integer representa- tions are binary, N A F , and w - N A F for which B = {!}, B = {+!}, and B = {±1, + 3 , . . . , ±(2"^"^ - 1)}, respectively. If a binary representation is used in Algor i thm 5.2, Steps 1 and 2 of the precomputation stage are not required. However, the evaluation stage would need (| — 1) point additions on average. Using the N A F representation, only Step 1 of the precompu- tation stage is required. In this case, the average number of point addi- tions required in the evaluation stage is reduced to (| - 1). This is because the average Hamming weight (the number of nonzero digits in the repre- sentation) of N A F is |. In fact, N A F has the minimal average Hamming weight among al l ^-representations with B = {+!}. The N A F representa- t ion can be generalized to w - N A F . The l y - N A F representation has the min - imal average Hamming weight of i^;^) among al l ^-representations wi th B = {+1, + 3 , . . . , +(2'^-i - 1)} [67]. When f y - N A F is used in Algor i thm 5.2, it is a signed shding window algorithm. In this case, the evaluation stage would require on average ( : j ^ — 1) point additions. However, Step 2 of the precomputation stage requires (2 '"-2 _ 1) point additions and one point doubling. In al l these cases, the evaluation stage requires about {I —I) point doublings. Note that / = [logg N] for the binary representation and I = [logj A ]̂ -I- 1 for the N A F and t y - N A F representations. 5.4.3 Extending R P M Algorithms We extend R P M algorithms to the case where we need to multiply a base point P only once but we can have some limited extra information regarding P. For example, in variants of the Diffie-Hellman key agreement protocol, an entity A receives P ' s public key PB and certificate, and is required to compute kPB- In this case, B can provide A with some l imited extra information by including it in its certificate. A tr iv ia l way to do this is to add a lookup table to the certificate. The entity A can use the lookup table together with a fixed point multiplication algorithm in order to compute kPB faster. This approach may not be practical when the table is large. A simple solution to this problem is to make a small lookup table and embed it in the certificate. However, a better solution is to use a relatively large lookup table and add only a few selected points from it to the certificate. W h e n properly selected, the points allow A to generate the entire lookup table relatively fast, and use it to speed up point multiplication. For instance, assume that we can add at most three points in a certifi- cate. In addition, suppose that Moller's algorithm is used as the fixed point multipl ication algorithm. We can add the points 3P, (2̂ =1 P ) and 3(2f^lp) to the certificate in order to set w = 3 for k's l y - N A F representation and avoid using a precomputation stage. In this case, we have the entire lookup table and we can reduce the required number of point doublings by about 1/2. However, the number of point doublings can be reduced by about 1/4 when we only add the points (2 f i lp ) , (22xmp) and {2^''^-^^P). To use the same l y - N A F representation {w = 3) as in the previous case, A must compute the points 3P,3 (2 f5 lp ) ,3(22 '^ f3 lp) and 3{2^''^-*^P) in the precomputation stage using 4 point additions and 4 point doublings. This is a small price to pay for a significant reduction in the required number of point doublings. In the next section, we use this approach by adding the set of points J n - i = { 2 f ^ l " ' P , . . . , 2 f ^ l ^ M p } to the certificate. This redundant information can be stored as an extension of the certificate since X.509 version 3 [74] supports extensions. Note that including this information into the certificate does not significantly increase the certificate size for small values of n. For example, a typical size for an X .509 certificate is about IK bytes [75]. For a 192-bit elhptic curve (as an example), the public key P requires [̂ |̂̂ 1 = 48 bytes. However, using a single point compression scheme, the point P could be represented using one 192-bit value and an additional bit. It then requires [^^f^] = 25 bytes. Therefore, adding an extra point to the certificate would increase its original size by less than 5% and 2.5% when the points are represented in an uncompressed and a compressed format, respectively. 5.5 Partially Random Point Multiplication (PRPM) A s shown in Algor i thm 5.3, MoUer's algorithm can be used to compute ran- dom point multiphcation kP using the redundant information J„_ i . We refer to A lgor i thm 5.3 as Partial ly Random Point Mult iphcat ion ( P R P M ) algo- r i thm since it performs a precomputation stage every time it is executed. P R P M is an extension of R P M to the case where some hmited extra infor- mation is available. Therefore, P R P M is expected to be faster than R P M at the cost of extra bandwidth. In this section, we speed up the P R P M a l - gorithm using Montgomery's trick for simultaneous inversion and show that it is significantly faster than the R P M algorithm. We also show how to compute random point multiplication using multiple processors. Note that the proposed point compression schemes can be used to reduce the required bandwidth when single point compression is computationally expensive. Algorithm 5.3 Part ia l ly Random Point Mult ip l icat ion ( P R P M ) Input: A n integer k, the base point P and the set r „ _ i Output: kP Precomputation Stage: 1: Compute the S-representation of the multiplier k = Yjo<i<i ^i"^^ ̂  ^ B u {0} 2: Compute and store d[2^nl^^P) for al l integers d e B, d > 1 and 0 ^ j < n Evaluation Stage: 4: R<-0 5: for i from (s — 1) down to 0 do 6: R^2R 7: for j from (n - 1) down to 0 do 8: if {ksj+i > 0) then 9; R^R + ksj+i{2'JP) 10: else if {kgj+i < 0) then 11: Ji^R-{-ksj+i){2^^P) 12: end if 13: end for 14: end for 15: return R 5.5.1 Speeding up P R P M In the precomputation stage of the P R P M algorithm, we must compute d{2'^P) for d G S , d > 1 and 0 ^ J < n. When u ; - N A F is employed, this computation can be accomphshed in 2^'^ steps by computing the point Q = 2Pij in the first step and the points P j j = Pi-i,j + Q in the i-th step for 0 ^ j < n, where Pij = 2*^P and 2 i ^ 2^""^. In the precomputation stage, it is preferable to represent the points Pij using affine coordinates in order to reduce the amount of memory required to store them and to speed up the evaluation stage of the algorithm using mixed coordinates systems [76]. Using affine coordinates, we need n simultaneous field inversions in each step. Montgomery's trick for simultaneous inversion enables us to do this using one field inversion and 3(n — 1) field multiphcations [66]. Thus, for large n, one field inversion is replaced by approximately three field mul - tiplications, which is a significant cost saving as a field inversion costs more than three field multiplications in most useful fields. Using this approach, we sti l l need 2"̂ ~^ field inversions. The number of field inversions can be further reduced to {w — 1) in a second approach by computing the points 2Pj in the first step, the points ( 2 ' - i + l)Pj, (2^-1 + 3)Pj,..., (2^ - 1)P,-, i2')Pj in the i-th step, 2 ^ i < w — 1, and the points (2—2 + i )p,^ (2"'-2 + 3 ) P j , . . . , (2^-^ - 1)P; in the last step, where Pj = 2^^P and 0 ^ j < n. In order to analyze the effects of using these approaches in more detail, let us restrict ourselves to elliptic curves defined over prime fields. If we use affine coordinates, the cost of the precomputation stage of Algor i thm 5.3 would be n 2 ^ - 2 / + n2'"-^M + n (2^-2 + 1)5. Using Montgomery's trick for simultaneous inversion in the first approach, we can reduce the computation cost to 2 " ' - 2 / + (5n - 3 ) 2 ^ - 2 + n(2 '"-2 + 1)5, thus saving the cost of 2 " ' - 2 ( n - l ) ( J - 3 M ) . The second approach has a computational cost of {w - 1)1 + {bn{T-^ + w-3)-Zw + 3)M + « (2^ -^ ^2w- 5)5. This can result in more savings for large values of I/M. 5.5.2 Performance Analysis of the P R P M Algorithm In this section, we compare the performance of the P R P M and R P M algo- rithms. To do this, we consider the binary, N A F and w-NAF integer repre- sentations. A binary representation requires no recoding, thus it can be used in devices with very l imited resources. The N A F representation can speed up point multiplication at the cost of recoding the integer, so it may be used in restricted devices in order to accelerate point multiplication. Finally, w-NAF {w > 2) can result in more speed up at the cost of recoding and storing some multiples of the base point. Therefore, w - N A F can be employed when some storage is available. In the P R P M algorithm, the S-representation of the multiplier k is d i - vided into n subblocks of length s = \^]. In the evaluation stage of this algorithm, the point multiplication kP is computed as / \ kP = 0^i<s Therefore, the required number of point doublings at this stage is reduced to ([^] — 1) while the required number of point additions remains the same as that wi th the R P M algorithm. Let A be the cost of a point addition and D the cost of a point doubling. If a binary representation is used, the cost of the P R P M and R P M algorithms are approximately {^A + ID) and {^A -\- ^£>), respectively. Therefore, we have - l ' - « = c o s t o i A g m " « = 2 Similarly, when the N A F representation is used we have {A + ID \-\-t s n i n Figure 5.1 compares the performance of the P R P M and R P M algorithms for the cases when binary and N A F representations are used, respectively. As shown in this figure, the higher the values of t and n , the better the performance improvement achieved by replacing the R P M algorithm wi th the P R P M algorithm. The value of t depends on the finite field and coordinate system employed. For example, if the binary finite field and affine coordinates are used, we would have t = 1 (see Table 5.1). Figure 5.1: Performance comparison of Algorithms 5.2 and 5.3 when binary (left) and N A F (right) representations are used. Now, consider the case where l y - N A F {w > 2) is used by both the R P M and P R P M algorithms. In this case, comparing the performance of these two algorithms is more complex than the previous case since different coor- dinate systems may be used in the precomputation and the evaluation stages. Therefore, for a precise performance comparison of Algorithms 5.2 and 5.3, we restrict ourselves to elliptic curves defined over prime fields, particularly those recommended by the National Institute of Standards and Technology (NIST) . In prime fields, the cost of a field squaring (S) can be approximated by 0 . 8 M as the ratio S/M is almost independent of the implementation. In addition, / can be approximated to be between 9M and 3 0 M for the case of F p , p > 100 [76]. Considering these assumptions, the optimum mixed coordinate systems for the R P M algorithm is to use affine coordinates in the precomputation stage, modified Jacobian coordinates (denoted by J"^), and Jacobian coordinates (denoted by J) in the evaluation stage [76]. The same mixed coordinate systems are used for the P R P M algorithm. Tables 5.4 to 5.7 show the average cost of the R P M and P R P M algo- rithms for the N I S T recommended elliptic curves. To get precise results and avoid complex equations, the average cost of the algorithms was obtained by simulation. For the P R P M algorithm, we restrict ourselves to 2 ^ n ^ i, as these values are more likely to be used in practice. In Table 5.4, the pa- rameter w was selected to minimize the cost of the R P M algorithm. For the P R P M algorithm, w was selected such that the required storage is less than or equal to that of the R P M algorithm. Therefore, the P R P M algorithm may result in more speed up when more storage is available. The fifth column of Tables 5.5 to 5.7 indicates the percentage increase in certificate size when the proposed point compression schemes are used. w # stored points Cost P-192 5 8 4 / + 1789M P.224 5 6 8 16 4 / + 2 0 8 4 M 5 / + 2 0 6 6 M P_256 5 6 8 16 47 + 2 3 7 8 M 5 / + 2 3 5 1 M P.384 6 16 5 / + 3492M P_521 6 7 16 32 5 / + 4 7 1 4 M 67 + 4 6 9 5 M Table 5.4: Cost of the R P M algorithm. w # Stored Points Cost Certificate Increase Performance Improvement P_192 4 8 37 + 1180M 2.5% 50% P-224 4 5 8 16 3 / + 1371M 4 / + 1338M 2.8% 51% 52% P_256 4 5 8 16 3 / + 1562M 41 + 1516M 3.2% 51% 53% P_384 5 16 47 + 2 2 3 0 M 4.6% 55% P_521 5 6 16 32 47 + 2 9 9 4 M 57 + 2 9 4 9 M 6% 56% 57% Table 5.5: Cost of the P R P M algorithm for n = 2. w # Stored Points Cost Certificate Increase Performance Improvement P_192 3 6 27 + 1038M 5.0% 73 - 74% P_224 4 12 3 7 + 1128M 5.6% 81 - 83% P_256 4 12 37 + 1280M 6.4% 82 - 84% P_384 4 12 37 + 1888M 9.2% 84 - 85% P_521 5 24 47 + 2 4 2 1 M 12% 91 - 93% Tab: e 5.6: Cost of the P R P M algorithm for n = 3. w # Stored Points Cost Certificate Increase Performance Improvement P_192 3 8 27 + 9 3 1 M 10% 93% P_224 3 4 8 16 27 + 1081M 37 + 1024M 11.2% 93% 99 - 101% P_256 3 4 8 16 27 + 1230M 3 7 + 1155M 12.8% 94% 101 - 103% P_384 4 16 37 + 1682M 18.4% 105 - 107% P.521 4 5 16 32 37 + 2 2 4 4 M 47 + 2163M 24% 108 - 110% 1 1 4 - 1 1 6 % Table 5.7: Cost of the P R P M algorithm for n = 4. 5.5.3 Parallel Processing of the P R P M Algorithm Using the redundant information J n - i , random point multiplication can be computed much faster wi th multiple processors. For example, assume that n processors are available and we have J n - i - Then kP can be computed as follows A - l \ n-1 / /s-1 \ \ kp = V=o / j=o \ \i=o / n-1 j=0 J where Rj = (YHZQ ksj+i2^){2^^P)- The j ' - th processor can then compute using Algor i thm 5.2. Hence, each processor requires s point doublings and in the worst case {{^ - 1) + (2^ "̂̂  - 1)) point additions when the w - N A F representation is used (note that l y - N A F has at most ^ nonzero digits). Then [log2n\ point additions are required to compute the final result. Therefore the total cost of parallel computation of kP is ((^ — 1) + (2^~^ — 1) + [log2 n\)A-f- sD. Consequently, using the redundant information and parallel processing, random point multiplication can be computed about n times faster than Algor i thm 5.2 when n « I because ( ( ^ - 1) + ( 2 - 2 - \))A + ID A + ID (it - 1) + (2" ' - ' - 1) + [log2 n])A + sD i ( l A + ID) (5.7) n. Note that for the algorithm used in parallel processing, the optimal w is generally smaller than that of Algor i thm 5.2. However, we used the same w in (5.7) for computational convenience. In fact, using the optimal w for parallel processing results in a value closer to n than in (5.7). Consider the general case where we have m processors (m < n) and we know J n - i - Random point multiplication can then be computed in the following (similar) way kP = n-\ \ m—1 / V ^ . 2 ^ 2 ks'j+i^ (2^'^P) V=o / j=0 \ m-1 j=0 where s' = \^] x \̂ ] and Rj = ks'j+i2'){2''^P). Note that in this case, each processor uses Algor i thm 5.3 instead of Algor i thm 5.2 to compute Rj. 5.6 Summary In this chapter, we proposed a novel double point compression technique and extended it to triple point compression. The compression process of the pro- posed schemes requires almost no computational effort, and decompression involves no square root operations. Therefore, they can be used to compress multiple points when single point compression is computationally expensive. We introduced a new approach to compute random point multiplication in which redundant information is added to the certificate and used to speed up the multiplication. Using this approach, we showed that a significant speed up can be obtained at the cost of slightly higher bandwidth. We also showed that the required bandwidth can be reduced using the proposed point compression schemes. Note that a similar approach can be used to speed up double point multiphcation [77] and exponentiation in hyperelliptic curve cryptography [78]. Bibliography 64] N . Kobl i tz , "E l l ip t i c curve cryptosystems," Math. Comp., vol. 48, pp. 203-209, 1987. [65] I. Blake, G . Seroussy, and N . Smart, Elliptic Curves in Cryptography. Cambridge: Cambridge University Press, 1999. 66] H . Cohen, A Course in Computational Number Theory, Graduate Texts in Math. 138. Springer-Verlag, 1993, th ird Corrected Pr int ing , 1996. 67] J . A . M u i r and D. R. Stinson, "Minimal i ty and other properties of the with-io nonadjacent form," Preprint, 2004, Available from http:/ /www.cacr.math.uwaterloo.ca/tech_reports.html. 68] M . Khabbazian, T . A . Gulliver, and V . K . Bhargava, " A new mini - mal average weight representation for left-to-right point multiplication methods," IEEE Trans. Computers, vol. 54, pp. 1454-1459, 2005. [69] B . MoUer, "Improved techniques for fast exponentiation," Springer- Verlag Lecture Notes in Computer Science, vol. 2587, pp. 298-312, 2003. 70] G . Seroussi, "Compact representation of ehiptic curve points over F 2 n , " Hewlett-Packard Laboratories Technical Report No. HPL-98-94R1,1998. 71] A . Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography. C R C Press, 1997. 72] C. H . L i m and P. J . Lee, "More flexible exponentiation with precompu- tation," Springer-Verlag Lecture Notes in Computer Science, vol. 839, pp. 95-107, 1994. 73] D . Gordon, " A survey of fast exponentiation methods," J. Algorithms, vol. 27, pp. 129-146, 1998. [74] I T U - T , ITU-T Recommendation X.509 version 3 (1997), Information Technology - Open Systems Interconnection - The Directory Authenti - cation Pramewordk, I S O / I E C 9594-8, 1997. 75] R. Zuccherato, "El l ip t i c curve cryptography support in entrust," Tech. Rep., M a y 9, 2000. [76] H . Cohen, A . M i y a j i , and T . Ono, "Efficient elhptic curve exponentiation using mixed coordinates," Springer-Verlag Lecture Notes in Computer Science, vol. 1514, pp. 51-65, 1998. 77] M . Khabbazian, T . A . Gulliver, and V . K . Bhargava, " A new technique for improving the speed of double point multiplication," IEEE Pacific Rim Conf. on Commun., Computers and Signal Processing, pp. 653-656, 2005. 78] N . Kob l i t z , "Hyperelliptic cryptosystems," Journal of Cryptology, vol. 1, pp. 139-150, 1989. Chapter 6 Summary and Conclusion This work consists of four major breakthroughs in the area of wireless ad hoc networks. The first two, presented in Chapters 2 and 3, deal with broad- casting, a fundamental operation in wireless ad hoc networks. In Chapter 2, we present two efficient broadcast algorithms based on 1-hop neighbor infor- mation. The first algorithm offers great improvements over one of the best neighbor-designating broadcast algorithms based on 1-hop neighbor infor- mation [79]. In their paper [79], L i u et al. proposed a neighbor-designating broadcast algorithm that can achieve local optimality by selecting the m i n - imum number of forwarding nodes in the lowest computational time com- plexity O ( n l o g n ) , where n is the number of neighbors. We show that this optimality only holds for a subclass of neighbor-designating algorithms. In fact, we prove that our first broadcast algorithm can reduce the time com- plexity of computing forwarding nodes to 0{n). The second improvement of our first broadcast algorithm is on reducing the maximum number of selected nodes. In algorithm of L i u et al, n nodes are selected to forward the message in the worst case, whereas in our proposed algorithm, the number of forward- ing nodes in the worst case is 11. This nice feature provides the capability of bounding packets overhead. Our second broadcast algorithm, presented in Chapter 2, was proposed with the objective of significantly reducing the number of transmissions. We show that our second proposed broadcast a l - gorithm is very successful in achieving this goal for the case where nodes are distributed randomly. However, we show that the algorithm cannot provide a constant approximation ratio to the optimal solution (minimum number of required transmissions) in the worst case. This directed us to our next work, presented in Chapter 3, in which we investigated whether localized broadcast algorithms are able to provide both full delivery and a good approximation ratio to the optimal solution. In Chapter 3, we first show that many of the existing neighbor-designating broadcast algorithms based on 1-hop neighbor information are not able to provide both full dehvery and a good bound on the optimal solution. We also show that this is true for many self-pruning broadcast algorithms based on 1-hop neighbor information as well. These results are in favor of a common belief that localized broadcast algorithms for ad hoc networks are not able to achieve full delivery and guarantee a bounded number of transmissions in the network. One of the breakthrough results, presented in Chapter 3, is showing for the first time this belief is unfounded by designing an efficient broadcast algorithm that satisfies both aforementioned properties. In fact, we prove that an extension of our second algorithm proposed in Chapter 2 can achieve both full delivery and a constant approximation ratio to the optimum solution. In addition, we prove that the message complexity of the extended algorithm is 0{N), where N is the total number of nodes in the network. This is also a very interesting result because the lower message complexity bound of finding C D S , a closely related problem, is proven to be fl(NlogN). Chapter 3 also includes other interesting contributions such as: • Proposing a nearly optimal algorithm to verify the responsibility con- dition • Removing nodes' IDs from the broadcast messages in order to reduce bandwidth overhead • Representing location information using only a constant number of bits • Replacing the list of neighbors of the broadcasting node (piggybacked in the packet) wi th a significantly smaller subset of it w i th the objective of further reduction in bandwidth overhead • Relaxing several system model assumptions or replacing them wi th practical ones: - Distr ibuting nodded in 3-D instead of 2-D - Broadcasting under uncertain position information - Relaxing the Homogeneous Network Assumption The other two major breakthrough of this work, presented in Chapters 4 and 5, deal with security issues in wireless ad hoc networks. In Chapter 4, we first analyze the effect of wormhole attack, one of the most severe attacks in ad hoc networks. We first draw a precise picture of the effect of the wormhole attack in shortest path routing protocols. We then show, in contrast to the common belief, the wormhole attack launched by two malicious nodes can- not disrupt/control the majority of communications, on average. However, we show that the attackers can disrupt/control about one-third of a l l the communications if the wormhole is placed strategically in the network. We also analyze a scenario in which several attackers make wormholes among each other and a case where two malicious nodes attack a target node in the network. We show how to evaluate the maximum effect of the wormhole attack on a given network topology. Then, we compute the maximum effect of the wormhole attack on grid topology networks and show that the at- tackers can disrupt/control around 40% to 50% of all communications when the wormhole is strategically placed in the network. To defend against the wormhole attack, we propose a timing-based countermeasure. The existing timing-based solutions typically suffer from some of the following shortcom- ings: • The nodes require tightly synchronized clocks • Each node has to be capable of fast switching between the receive and send modes • Each node needs one-to-one communication with al l its neighbors • Each node requires predicting the sending time We show that our proposed timing-based countermeasure does not have any of these shortcomings, thus is more suitable for practical implementation of solutions based on packet travel time measurements. A s the continuation of our work on security of ad hoc networks, we studied elliptic curve cryptography, which is one the primary public-key candidates to be used in ad hoc networks. We propose two point compression schemes, in Chapter 5, that can be used to reduce memory/bandwidth required to store/transmit elliptic curve points. The compression using our schemes can be done with almost no effort. In contrast to single point compression scheme, patented by Certicom Corporation, decompression of our schemes does not require any square root operation. Therefore, our schemes can be used, rather than single point compression scheme, when square root operation is computationally expensive. A l l the results presented in this work can be used to improve the effi- ciency of the wireless ad hoc network operations or to make the network more secure. A s future work, it would be interesting to show whether local- ized broadcast algorithms can achieve both full delivery and a good bound on the optimal solution without using location information. Also, it is worth analyzing the effect of the wormhole attack in routing protocols not based on shortest path. In Chapter 5, we showed that the wormhole attack counter- measure presented in [80] is not able to detect the wormhole if the attackers selectively forward the packets. We claimed that this problem can be m i t i - gated when our proposed timing-based solution is used. It is of interest to improve the proposed countermeasure in [80] to resolve this issue without us- ing any specialized hardware such as accurate clocks (note that timing-based solutions require accurate clocks). Bibliography [79] H . L i u , P. Wan, X . J i a , X . L i u , and F . Yao, "EfRcient flooding scheme based on 1-hop information in mobile ad hoc networks," In Proc. of IEEE INFOCOM, 2006. 80] R. Maheshwari, J . Gao, and S. R. Das, "Detecting wormhole attacks i n wireless networks using connectivity information," In Proc. of IEEE INFOCOM, 2007. Appendix A List of Publications Journal papers (accepted/published) • M . Khabbazian, M d . Jahangir Hossain, and V . K . Bhargava, "Exact Method for the Error Probabil ity Calculation of Three-Dimensional Signal Constellations," accepted for publication IEEE Transactions on Communications, 2008. • H . Mercier, M . Khabbazian and V . K . Bhargava, " O n the Number of Subsequences when Deleting Symbols from a String," accepted for publication in IEEE Transactions on Information Theory, 2008. • M . Khabbazian and V . K . Bhargava, "Locahzed Broadcasting with Guaranteed Delivery and Bounded Transmission Redundancy," accepted for publication in IEEE Transactions on Computers, 2008. • M . Khabbazian, H . Mercier and V . K . Bhargava, "Severity Analysis and Countermeasures for the Wormhole Attack in Wireless A d Hoc Networks," accepted for publication in IEEE Transactions on Wireless Communications, 2008. • M . Khabbazian and V . K . Bhargava, "Highly Efficient Broadcasting in Mobile A d Hoc Networks," accepted for publication in IEEE Trans- actions on Mobile Computing, 2007. • M . Khabbazian, T . A . Gulliver and V . K . Bhargava, "Double Point Compression with Applications to Speeding up Random Point M u l - t ipl ication," IEEE Transactions on Computers, vol. 56, no. 3, pp. 305-313, M a r . 2007. • M . Khabbazian, T . A . Gulliver and V . K . Bhargava, " A New M i n i m a l Average Weight Representation for Left-to-Right Point Mult ip l i cat ion Methods," IEEE Trans. Computers, vol. 54, No. 11, pp. 1454-1459, Nov. 2005. Journal papers (submitted) • K . K . Leung, C. W . Sung, M . Khabbazian and M . A . Safari, "Opt imal Phase Control in M I M O Systems with Quantized Feedback," submitted to IEEE Transactions on Information Theory, Mar . 2008. Selected conference papers • P. Kaligineedi, M . Khabbazian, and V . K . Bhargava, "Secure Coop- erative Sensing Techniques for Cognitive Radio Systems," IEEE Inter- national Conference on Communications (ICC), M a y 2008. • M . Khabbazian and V . K . Bhargava, "Reducing Broadcast Redun- dancy in Wireless A d Hoc Networks," IEEE Global Communications Conference, Nov. 2007. • M . Khabbazian, H . Mercier and V . K . Bhargava, "Wormhole A t - tack in Wireless A d Hoc Networks: Analysis and Countermeasures," in Proc. IEEE Global Communications Conference, Nov. 2006. • M . Khabbazian, K - K . Leung and M . A . Safari, " O n the Opt imal Phase Control in M I M O Systems with Phase Quantization," in Proc. IEEE International Communications Conference, vol. 9, pp. 4272- 4277, Jun . 2006. • M . M . Rashid, E . Hossain, M . Khabbazian, and V . K . Bhargava, " O n Access-Based Self-Organized Clustering in A d Hoc Mobile Wire - less Networks," in Proc. IEEE Conference on Communication System Software and Middleware (COMSWARE), Jan . 2006.

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0066825/manifest

Comment

Related Items