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.

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 V i c t o r i a , 2004 A THESIS S U B M I T T E D IN P A R T I A L F U L F I L M E N T O F THE REQUIREMENTSFOR T H E D E G R E E OF Doctor of Philosophy in The Faculty of Graduate Studies (Electrical and Computer  Engineering)  The University O f B r i t i s h C o l u m b i a (Vancouver) August, 2008 © M a j i d K h a b b a z i a n 2008  Abstract Wireless ad hoc networks have been emerged to support applications, i n 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 limited transmission range. Therefore, each node can directly communicate w i t h only those w i t h i n its transmission range and requires other nodes to act as routers i n order to communicate w i t h out-of-range destinations. One of the fundamental operations i n ad hoc networks is broadcasting, where a node sends a message to a l l other nodes i n the network. T h i s can be achieved through flooding, in which every node transmits the first copy of the received message. However, flooding can impose a large number of redundant transmissions, which can result i n significant waste of constrained resources such as bandwidth and battery power. One of the contributions of this work is to propose efficient 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 existing timing-based solutions against the wormhole attack. Finally, i n the last chapter, we propose novel point compression techniques which can be used i n E l l i p 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 ) w i t h substantially smaller key sizes. Smaller keys can result i n smaller system parameters, b a n d w i d t h savings, faster implementations and lower power consumption. These advantages make E C C interesting for ad hoc networks w i t h restricted devices.  Table of Contents Abstract  ii  Table of Contents  iii  List of Tables  iv  List of Figures Acknowledgements  v vi  Dedication  vii  Statement of C o - A u t h o r s h i p  viii  1  Introduction and Background  1  1.1 1.2  1 2 2 2 3 4 5  1.3 1.4  Introduction and M o t i v a t i o n Wireless A d Hoc Networks 1.2.1 Modeling Wireless A d Hoc Networks 1.2.2 Broadcasting and R o u t i n g 1.2.3 Wormhole A t t a c k E l l i p t i c Curve Cryptography Thesis C o n t r i b u t i o n  Bibliography 2  Efficient Broadcasting i n Wireless A d H o c Networks . . . . 2.1 Introduction 2.2 System M o d e l 2.3 A n Efficient Neighbor-Designating Broadcast A l g o r i t h m . . . 2.3.1 A l g o r i t h m Structure 2.3.2 Forwarding-Node Selection A l g o r i t h m  7 9 9 11 12 12 13  2.3.3 2.3.4  2.4  2.5  2.6  Reducing the Number of Forwarding Nodes M a x i m i z i n g the M i n i m u m Node Weight of B-coverage Set 2.3.5 Similarity W i t h A Topology C o n t r o l A l g o r i t h m . . . . A H i g h l y Efficient Self-Pruning broadcast algorithm 2.4.1 A l g o r i t h m Structure 2.4.2 A Responsibility-Based Scheme 2.4.3 A Property of the Proposed R B S Simulation 2.5.1 Average Number of Nodes Selected by the Proposed 2.5.2 Probability of Broadcast using the Proposed R B S . . . 2.5.3 Performance of Proposed Neighbor-Designating Summary  22 22 24 27 27 28 32 37 37 38 42 48  Bibliography  49  3  52 52 53 55 56 57 57 60 61 63  Localized Broadcasting with B o u n d e d 3.1 Introduction 3.1.1 Related Work 3.1.2 O u r Contribution 3.2 System M o d e l 3.3 Broadcast Algorithms Based on 1-hop Neighbor Information . 3.3.1 Neighbor-Designating A l g o r i t h m s 3.3.2 Self-Pruning Algorithms 3.4 A n Efficient Self-Pruning Broadcast A l g o r i t h m 3.4.1 Analysis of the Proposed Broadcast A l g o r i t h m . . . . 3.4.2 Efficient Algorithms for C o m p u t i n g the Responsibility Condition 3.4.3 Reducing B a n d w i d t h Requirements 3.5 Relaxing Some of the System-Model Assumptions 3.5.1 Broadcasting Under Uncertain Position Information . 3.5.2 Relaxing the Homogeneous Network A s s u m p t i o n . . . 3.5.3 Broadcasting i n Three-Dimensions 3.6 Simulation 3.6.1 Reducing B a n d w i d t h Overhead 3.6.2 Performance of the Proposed Broadcast A l g o r i t h m . . 3.7 Summary  67 69 72 73 80 81 82 82 82 88  89  Bibliography 4  W o r m h o l e A t t a c k i n Wireless A d H o c Networks 4.1 Introduction 4.2 Related Work 4.3 Wormhole Attack Analysis 4.3.1 A p p r o x i m a t i n g the L e n g t h of the Shortest P a t h . . . . 4.3.2 Targeting a l l of the nodes i n the Network 4.3.3 Targeting a Particular Node i n the Network 4.4 Wormhole Attack Analysis for a Generic Network 4.5 Wormhole A t t a c k Countermeasure 4.6 Summary  Bibliography 5  Double Point Compression 5.1 Introduction 5.2 EUiptic Curves: Definition and Operations 5.3 Point Compression 5.3.1 Double Point Compression 5.3.2 A n Extension to Triple Point Compression 5.3.3 Compressing M u l t i p l e Points 5.4 Point M u l t i p h c a t i o n 5.4.1 F i x e d point multiphcation ( F P M ) 5.4.2 R a n d o m Point M u l t i p h c a t i o n ( R P M ) 5.4.3 E x t e n d i n g R P M Algorithms 5.5 P a r t i a l l y R a n d o m Point M u l t i p h c a t i o n ( P R P M ) 5.5.1 Speeding up P R P M 5.5.2 Performance Analysis of the P R P M A l g o r i t h m 5.5.3 Parallel Processing of the P R P M A l g o r i t h m 5.6 Summary  91 91 93 95 96 97 103 107 Ill 114 115  117 117 119 120 121 123 127 127 127 128 130 131 132 . . . .134 138 139  Bibliography  140  6  142  S u m m a r y and Conclusion  Bibliography  146  Appendices A  List of Publications  147  List of Tables 2.1  Simulation parameters  44  2.2  A l g o r i t h m s used i n the simulation  45  3.1  Simulation parameters  84  5.1  E l h p t i c curve point addition, P3 = Pi + P2  120  5.2 5.3 5.4 5.5 5.6 5.7  E l l i p t i c curve point inversion Triple Point Compression Cost of the R P M algorithm Cost of the P R P M algorithm for n = 2 Cost of the P R P M algorithm f o r n = 3 Cost of the P R P M algorithm for n = 4  120 126 136 137 137 137  List of Figures 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 2.15 2.16 2.17 2.18 2.19 2.20  3.1 3.2 3.3 3.4  A bulged slice around A Left bulged slice of B and right bulged slice of C around A. . Upper bound on the distance between nodes inside a bulged slice Illustration of Lemmas 2.2 and 2.3 T h e counterexample for ct = ^ A counterexample for a = | A n example of an R B S decision A n instance of using the proposed broadcast algorithm F i n d i n g a lower bound for A{I{VA,R, VB,R, T>QQB)) Average number of nodes selected by the proposed slice-based algorithm Probabihty of broadcast for R = 300m P r o b a b i l i t y of broadcast for R = 400m Probabihty of broadcast for R = 500m Probabihty of broadcast for R = 600m Broadcasting nodes i n a 1000 x lOOOm^ square area w i t h 400 nodes R a t i o of broadcasting nodes vs. t o t a l number of nodes R a t i o of broadcasting nodes vs. transmission range R a t i o of broadcasting nodes vs. t o t a l number of nodes Average delivery ratio vs. probability of message-reception failure Average delivery ratio vs. probability of message-reception failure A n example of a node on the network boundary T w o worst-case examples for Theorem 3.1 A worst-case example for Theorem 3.2 A n example of self-pruning based on the responsibility condition.  15 15 16 17 26 26 30 31 35 38 39 40 40 41 41 45 46 46 47 47 58 59 61 63  3.5  Three co-centered disks;  6  m-  66  3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13  Partitioning the network into square cells T h e ratio ^ ^ ^ ^ ^ x 100 against the total number of neighbors. Broadcasting nodes i n a 10^ x lO^m^ square area w i t h 400 nodes. R a t i o of broadcasting nodes vs. transmission range R a t i o of broadcasting nodes vs. t o t a l number of nodes Average delay vs. t o t a l number nodes R a t i o of broadcasting nodes of the proposed algorithm R a t i o of broadcasting nodes of the proposed algorithm i n a network  78 83 85 85 86 86 87  DQ  R  and A^g. e  DQBR  -  DQ  87  4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9  F i n d i n g a p a t h between 5 and 97 Partitioning the network into regions 72-1 and 7^2 98 C o m p u t i n g the area of Us using polar coordinates 101 Percentage of affected communications across the network. . . 102 Partitioning a network w i t h several attackers into Voronoi Cells. 103 C o m p u t i n g the area of TZM 105 Percentage of affected communications t o / f r o m the target node. 107 Unreachable region for the target node under attack 108 Percentage of m a x i m u m number of affected communications . . . I l l  5.1  Performance comparison of A l g o r i t h m s 5.2 and 5.3  135  Acknowledgements First and foremost, I would like to acknowledge my thesis supervisor, P r o fessor V i j a y Bhargava, for his guidance and support. M y respectful gratitude goes to my committee: Professor Ian Blake, Professor L u t z L a m p e , V i c t o r Leung, Professor B r i a n 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 I T S lab. I would like to thank a l l of them for their friendship, help w i t h 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 K h a b b a z i a n is the p r i m a r y author of the papers presented i n this work. For a l l these papers, M r . K h a b b a z i a n 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 V i j a y Bhargava (and Professor A a r o n Gulliver for the last chapter). M r . K h a b b a z i a n was assisted i n preparing the papers presented i n 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 i n this work have been received credit or presented i n 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 communications between different devices (simply called nodes) without relying on any centralized infrastructure. For example, i n battlefields or i n emergency/rescue operations, it is often impractical to have an infrastructure and to rely on centralized and organized connectivity. M a n y 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 limited bandwidth wireless links. E a c h node is equipped w i t h a transceiver w i t h limited transmission range and thus, has to rely on other nodes i n order to communicate w i t h destinations outside its transmission range. To establish a communication, the sender first needs to discover a route to the destination node. It then requires all 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 i n ad hoc networks have typically limited resources such as battery lifetime, bandwidth and computational power. Therefore, it is crucial to design efficient methods for ad hoc networks i n order to save these scarce resources. A l s o , wireless ad hoc networks are vulnerable to several attacks. In real environments, a malicious node can easily j o i n 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 i v i a l due to the network specific characteristics such as open environment, dy-  namic topology, lack of centralized infrastructure and limited bandwidth, battery lifetime and computational power. The a i m and motivation of this work is to construct novel methods i n an attempt to improve the security and efficiency of ad hoc networks.  1.2 1.2.1  Wireless A d Hoc Networks Modeling Wireless A d Hoc Networks  A wireless ad hoc network can be modeled as a directed graph i n 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 w i t h i n the transmission range of t?i's corresponding node. In general, the wireless devices may have different transmission ranges. Moreover, two nodes w i t h i n 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 t h a n 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 i n ad hoc networks. In broadcasting, a single node sends a message to a l l other nodes i n the network. The simplest way of broadcasting is v i a flooding. In flooding, each node transmits the received message to a l l its neighbors (the nodes w i t h i n 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 i n transmissions. However, this is achieved at the cost of one transmission per each single node i n the network. In practice, not all the nodes are required to transmit the message i n order to deliver it to a l l the nodes i n 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. R o u t i n g algorithms are responsible for providing end-to-end communications i n ad hoc networks. There are numerous routing protocols proposed for ad hoc networks [3]. These protocols can be divided into two main categories: Proactive (Table-Driven) and Reactive (On-Demand) routing protocols. Proactive routing protocols maintain a constant network view by saving routes to a l l possible destinations i n 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 i n route discovery. However, they can cause a substantial overhead when the mobility rate or the number of nodes i n 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 O n - D e m a n d Distance Vector R o u t i n g ( A O D V ) [4] and D y n a m i c Source R o u t i n g ( D S R ) [5] are two well-known examples of on-demand routing protocols. B o t h 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 valid route to the destination. In this phase, the source node broadcasts a Route Request ( R R E Q ) packet. W h e n the destination node receives the R R E Q packet, it replies to the source node w i t h a Route Reply ( R R E P ) packet. Packets i n A O D V only contain the address of the destination node whereas i n D S R they also include the address of a l l the intermediate nodes.  1.2.3  Wormhole Attack  A s mentioned earlier, ad hoc networks are vulnerable to many different attacks. T h e wormhole attack is one of the most severe attacks that can form a serious threat against ad hoc networks. T h e 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 t u a l " link between them. T h e link can be formed using an i n - b a n d (tunneling) or out-of-band communications and can attract many packets since it can transfer packets between far apart locations w i t h short delays a n d / o r small number of hops. T h i s can be considered as a useful service from the malicious nodes if they do not take advantage of the v i r t u a l link. However, i n practice, the malicious nodes can employ this link to analyze 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 countered w i t h cryptography alone. Moreover, as we w i l l analytically show i n Chapter 4, using this attack, the malicious nodes can control/disrupt many communications i n the network. T h e existing solutions against wormhole attack often t r y to bound the distance a packet can travel by using location or t i m i n g information. For example, i n 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] i n 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  E l l i p t 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 ) w i t h substantially smaller key sizes. Smaller keys can result i n smaller system parameters, b a n d w i d t h savings, faster implementations and lower power consumption. These advantages make elliptic curve cryptography appropriate for ad hoc networks w i t h 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 i n 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 . T h e 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 e x t r a 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 w i l l be two possible solutions; thus the extra bit is needed to distinguish the correct solution. T h i s 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 w i t h the single point compression. The double point and triple point compression schemes can be employed to save about 25% and 3 3 % of bandwidth/memory, respectively.  1.4  Thesis Contribution  In this section, we explain the organization of this work along w i t h our contributions i n designing efficient and secure algorithms. T h e m a i n objective of this work is to develop efficient algorithms and secure schemes for wireless ad hoc networks. A s mentioned earlier, broadcasting is a fundamental primitive i n ad hoc networks. In broadcasting, many nodes may get involved i n transmitting a message. Consequently, it can significantly affect the network performance. T h e simplest way of performing a broadcast is v i a flooding. In flooding, each node transmit the message once. T h i s can cause a huge amount of redundant transmission particularly i n dense networks. Unfortunately, it is not possible, i n general, to remove all redundant transmissions as the problem of m i n i m i z i n g the total number of required transmissions is N P - H a r d when the network is modeled using a unit disk graph. M a n y broadcast algorithm have been proposed i n the literature to reduce the number of redundant transmissions. A m o n g the existing methods, localized broadcast algorithms are more attractive as they can cope w i t h the network topology changes. In Chapters 2 and 3, we propose two efficient localized broadcast algorithms. T h e first proposed algorithm, presented i n Chapter 2, is an improvement over L i u ' s algorithm [10] which is one of the best broadcast algorithms i n its category. In the same chapter, we propose another broadcast algorithm w i t h the objective of reducing the total number of transmissions. We demonstrate that the second proposed algorithm is very successful i n 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 t o t a l number of transmissions i n 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 a n d prove that it can achieve both full delivery and a constant approximation ratio to the m i n i m u m 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 w i t h more practical ones. Chapters 4 and 5 deal w i t h the security of ad hoc networks. In Chapter 4, we analyze the effect of the wormhole attack i n shortest-path routing protocols w i t h the objective of drawing a more precise picture of the attack's possible damage. We show that two malicious nodes can control/disrupt a large percentage of the communications i n the network if they place the wormhole strategically. We also consider and analyze the case where more t h a n two malicious nodes are involved i n the wormhole attack. We then propose a timing-based countermeasure and show that it does not have the shortcomings 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 w i t h its transmission time. In Chapter 5, we introduce two compression schemes that can be used to reduce the memory and bandwidth requirements i n storing and transmitting the elliptic curve points. In practice, single point compression scheme may be employed to reduce the m e m o r y / b a n d w i d t h requirement. However, single point compression, patented by Certicom Corporation, requires a square root operation which is a computationally expensive operations i n some finite 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 t h a n 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. T h i s approach can be used to speed up elliptic curve cryptography i n any devices, particularly those w i t h constrained computational power or servers overloaded w i t h elliptic curve encryption or key agreement requests. Finally, we conclude this work i n Chapter 6.  Bibliography 1] Y . C. H u , A . Perrig, and D . B . Johnson, " R u s h i n g attacks and defense i n 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 i n wireless ad hoc networks," In Proc. of IEEE INFOCOM, 2003. 3] D . A g r a w a l and Q. Zeng, Introduction B r o o k s / C o l e Publishing, 2002.  to Wireless and Mobile  Systems.  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 . M a l t z , " D y n a m i c source routing i n ad hoc wireless networks," i n Mobile Computing, Imielinski and K o r t h , Eds. Kluwer Academic Pubhshers, 1996. 6] S. C a p k u n , L . B u t t y a n , and J . P. Hubaux, " S E C T O R : Secure tracking of node encounters i n 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, " U s i n g directional antennas to prevent wormhole attacks," In Proc. of Network and Distributed System Security Symposium, 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 . K o b l i t z , " E l h p t i c curve cryptosystems," 203-209, 1987.  Math.  Comp., vol. 48, pp.  [10] H . L i u , P. W a n , X . J i a , X . L i u , and F . Yao, "Efficient flooding scheme based on 1-hop information i n 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, i n which one node sends a message to a l l other nodes i n the network. Broadcasting is widely used as a basic mechanism i n many ad hoc network protocols. For example, ad hoc on-demand routing protocols, such as A O D V [11] and D S R [12], typically use broadcasting i n 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 a l l its neighbors in a collision-free network. Therefore, the broadcast redundancy significantly increases as the average number of neighbors increases. H i g h broadcast redundancy can result i n high power and b a n d w i d t h consumption i n the network. Moreover, it increases packet collisions, which can lead to additional transmissions. T h i s can cause severe network congestion or significant performance 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 i n the network. A set of nodes is called a D o m i n a t i n g Set (DS) if any node i n the network either belongs to the set or is a 1-hop neighbor of a node i n the set. T h e set of broadcasting nodes forms a Connected D o m i n a t i n g Set ( C D S ) . Therefore, the m i n i m u m number of required broadcasts is not less than the size of the m i n i m u m C D S . Unfortunately, finding the m i n i m u m 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 m i n i m u m C D S w i t h 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 i n ad hoc networks. However, this approach is not efficient i n networks w i t h frequent topology changes, as maintaining a C D S is often costly [18 . T h e m a i n objective of efficient broadcast algorithms is to reduce the n u m ber of transmissions while keeping the bandwidth and computational overhead 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 a n d / o r eflPectively reduce the number of transmissions. M o r e 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 network situations. In the second category, broadcast algorithms require to have 2-hop or more neighbor information. T h e broadcast algorithms i n this category can reduce the number of transmissions i n the network and guarantee 100% delivery [21, 22, 23]. However, they may induce high overhead i n 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. T h e first proposed algorithm is a neighbor-designating (or sender-based) algorithm. In neighbor-designating algorithms, the broadcasting nodes select a subset of their neighbors to forward the message. We compare our proposed broadcast algorithm to one of the best neighbordesignating broadcast algorithms that use 1-hop information [18]. In [18], L i u et al. proposed a broadcast algorithm that reduces the number of transmissions and achieves local optimality by selecting the m i n i m u m number of forwarding nodes w i t h m i n i m u m 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 w i t h time complexity 0 ( n ) . Moreover, L i u ' s algor i t h m selects n forwarding nodes i n the worst case, while our proposed a l gorithm selects 11 nodes i n the worst case. Based on our simulation results, our neighbor-designating algorithm results i n fewer transmissions t h a n does L i u ' s algorithm. A l l these nice properties are achieved at the cost of slightly increase i n end-to-end delay. Therefore, our first proposed algorithm is preferred to L i u ' 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 algor i t h m i n this chapter. In self-pruning algorithms, the receiver decides whether or not to broadcast the message. O u r proposed self-pruning algorithm is a novel broadcast algorithm that can significantly reduce the number of transmissions i n 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 algor i t h m is less t h a n one of the best-known approximations for the m i n i m u m number of required broadcasts. T h e 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 i n 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 w i t h that of one of the best existing broadcast algorithms and an approximated lower b o u n d of o p t i m a l solution. Finally, we provide a summary i n Section 2.6.  2.2  System Model  O u r system model is very similar to that used by L i u et al. [18]. We assume that a l l nodes are located i n 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. T w o nodes are considered neighbors if they are i n transmission range of each other. We suppose that each node knows its location v i a a localization technique such as G l o b a l Positioning System ( G P S ) or the lightweight techniques summarized i n [24]. E a c h 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 M e d i u m 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 i n 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 until the channel becomes idle. W h e n the channel is idle, it starts decrementing the defer timer at the end of each time unit. T h e message is broadcast when the timer expires.  2.3 2.3.1  A n Efficient Neighbor-Designating Broadcast Algorithm 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. E a c h message can be identified by its source id and a sequence number incremented for each message at the source node. A l g o r i t h m 2.1 is a general neighbordesignating broadcast algorithm and indicates the structure of our proposed neighbor-designating broadcast algorithm. U p o n expiration of the timer, the algorithm requests the M A C layer to schedule a broadcast. T h e message scheduled i n the M A C layer is buffered and then broadcast w i t h a probability p. T h i s adds another delay (i.e., the M A C layer delay) i n broadcasting the message. T h e M A C layer delay i n 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. T h i s chance is not negligible when the delay i n the M A C layer is comparable to the average value of the timer set i n the broadcast algorithm. A s stated i n [25], one solution to this problem is a cross-layer design i n which the network layer is given the ability to modify or remove packets that are present i n the M A C layer queue. T h i s 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 i n the M A C layer queue. T h e neighbor-designating broadcast algorithms can be divided into two subclasses. In the first subclass, each node decides whether or not to broadcast solely based on the first received message and drops the rest of the same  messages that it receives later. Liu's algorithm falls i n this subclass. In L i u ' s algorithm, each node selects the smallest subset of its 1-hop neighbors w i t h the m a x i m u m coverage area, where the coverage area of a set of nodes is the union of their transmission coverage. Clearly, if the selected neighbors 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(nlogn). In the second subclass of neighbor-designating broadcast algorithms, each node can decide whether or not to broadcast after each message reception. However, if a node broadcasts a message, it w i l l drop the rest of the same messages that it receives i n future. Therefore, each message is broadcast at most once by a node using the broadcast algorithms i n b o t h subclasses. O u r first proposed broadcast algorithm falls i n this subclass of neighbordesignating broadcast algorithms. We show that the proposed algorithm can reduce b o t h the computational time complexity of selecting the forwarding nodes and the m a x i m u m number of selected nodes i n the worst case. A l g o r i t h m 2.1 shows the basic structure of our proposed neighbor-designating broadcast algorithm. A s shown i n A l g o r i t h m 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 i u ' s algorithm. However, i n L i u ' s algorithm, each node may only schedule a broadcast when it receives a message for the first time. In contrast, i n A l g o r i t h m 2.1, a broadcast 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 m a i n design issue i n A l g o r i t h m 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 w i t h 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  A l g o r i t h m 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: W h e n defer timer expires 8: Select a subset of neighbors to forward the message 9: A t t a c h the list of forwarding node to the message 10: Schedule a broadcast  in any bulged slice AMN  we have /.MAN  = |.  Definition 2.2 ( R i g h t / L e f t B u l g e d 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 A l g o r i t h m ) . 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 trivial slice-based selection algorithm would be one that selects a l l of the neighbors as the B-coverage set. Clearly, this algorithm w i l l result i n flooding if it is used as the forwarding-node selection scheme i n A l g o r i t h m 2.1. In this section, we first show that A l g o r i t h m 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 i n the worst case and has computational complexity 0 ( n ) , where n is the number of neighbors.  L e m m a 2.1. For any two points Pi and P2 inside a bulged slice, we have P^2^RProof. A s shown i n 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- T h i s is easy to show if b o t h 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 w i 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 . A s shown i n 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 and BP ^R.  or AQN  if AP ^ R  Proof. It is easy to show that for any triangle AABC, AC, where M is a point on the line segment BC. triangle APAB (shown i n Figure 2.4) we have PQ^AP^R  or  AM ^ AB or AM ^ Consequently, i n the  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 a n d 2.3.  L e m m a 2.3. For any point P ^ A inside the bulged slice AQM we have 'BP <BÂ.  or AQN,  Proof. Using triangle inequality we get 'BP ^'BQ + 'QP  + R =  BA.  T h e equality holds only when BP = BQ + QP and QP = R, or simply when P = A.  •  T h e o r e m 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 A l g o r i t h m 2.1, each node broadcasts the message at most once. Therefore, broadcasting will eventually terminate. B y contradiction, suppose 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 p a t h between Ns and Nr. Clearly, we can find two neighbor nodes NQ, NB along the p a t h 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 NAConsequently, {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 L e m m a 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. W i t h o u t loss of generality, assume that B' is inside the bulged shce A'PiP2. Since NA' has at least one neighbor (i.e., NB') i n this shce, there must be a selected node N^ i n the shce that has forwarded the message. Using L e m m a 2.1, we get B'D ^ R; hence, nodes No a n d NB' are neighbors. Therefore, (No, N B ' , Nc) e A . However, this contradicts (2.1) because using L e m m a 2.3 we have DC  <  A'C.  • A l g o r i t h m 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 i n an array of length n , where n is the number of neighbors. T h e algorithm selects the first node A^^j 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))  :  (2.2) ^  /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)).  T h e algorithm terminates by selecting the last node Ns^ if Ns^ CBA{SI)  or Ns, is inside £ 5 ^ ( 5 ^ ) or Sm+i = Sy.  (2.3) is inside  A l g o r i t h m 2.2 A slice-based selection algorithm Input: ListA[l... n]: List of a l l neighbors of A''^ O u t p u t : 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 ^ l e n g t h ( L i s t A ) ; J + + do if ListA[j] is i n CBA{Si) then if /-Aij^l^AiSi), CBA{ListA[j])) > angjmax chk true indjmax <— j angjmax end if else  *— /-A{J^I^A{Si),  if /-A{CBA{Si),TZBA{ListA[3])) ind-min <— j  CBA{ListA{3\))  < angjmin  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 i n if # 1 then end if  then  then  CBA{SI)  L e m m a 2.4. Suppose the proposed algorithm selects m nodes { , For any 1 ^ i < m — 2, we have  A^^^,Ns^}.  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). T h u s , using (2.2) we have Z.A{CBA{Si),CBA{Si+2))  ^  ^AiCBAiSi),CBA{Si+i))  which is a contradiction. T h e o r e m 2.2. most 11 nodes.  •  The proposed slice-based selection  algorithm  will select at  Proof. B y contradiction, assume that the algorithm selects more than 11 nodes. Therefore, 5 i i is not i n CBA{SI).  Using L e m m a 2.4, we get  5  = 2(^A(/:^A(52,-I),/:fiA(52i+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 w i l l terminate after selecting ^ n . • AA{CBA{S,),CBA{Sn))  T h e 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 t h a n 6. T h e o r e m 2.3. Time complexity of the proposed slice-based selection rithm is 0{n), where n is the number of neighbors.  algo-  Proof T h e algorithm selects the first node i n 0 ( 1 ) . To select each of the other nodes, the algorithm performs 0{n) operations by checking all the neighbors i n the array. Therefore, the complexity of the a l g o r i t h m 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 attaches a list of its selected forwarding nodes to the message before broadcasting i t . T h i s procedure will increase the b a n d w i d t h and power required to broadcast the message. A s shown earher, our proposed shce-based selection algorithm reduces the number of selected forwarding nodes to 11 i n 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 all 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 CAA l g o r i t h m 2.2 can be simply extended to achieve this i n 0(n). Note that the extended algorithm can start w i t h a node from CA and select any node i n CA as soon as it appears in the left bulged shce of the previously selected node. Finally, the extended algorithm removes a l l of the nodes i n 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. T h e 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 m i n i m u m node weight is m a x i m u m or its m a x i m u m node weight is m i n i m u m among that of all B-coverage sets. For example, assume that the weight of each node represents its battery lifetime i n a wireless network. It may be desirable to select the nodes w i t h a higher battery lifetime to forward the message in order to keep the nodes w i t h a lower battery hfetime alive. A l g o r i t h m 2.3 shows how to find a B-coverage set such that its m i n i m u m node weight is m a x i m u m among that of all B-coverage sets. A similar approach can be used to find a B-coverage set such that its m a x i m u m node weight is minimum.  A l g o r i t h m 2.3 M a x i m i z i n g the m i n i m u m node weight Input: ListA[l • • .n]: List of a l l neighbors of A^^ O u t p u t : A B-coverage set of NA w i t h highest m i n i m u m 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 SList[l 6: end if 7: while H>T+ldo 8: St <— AlgorithmJ2.2(SList[l.. .m]) {Pass m nodes w i t h the highest weights to A l g o r i t h m 2.2 as the input} if St is a B-coverage set for NA then 9 H 10 11 12 13  else T  m  14 15 16 17  end if end while r e t u r n ( A l g o r i t h m J 2 . 2 ( 5 L i s i [ l . . . H]))  A l g o r i t h m 2.3 first sorts the nodes by their weights i n decreasing order. T h e n , i n each step it passes m nodes w i t h the highest weights to A l g o r i t h m 2.2 as input and gets a set of (at most 11) nodes as output, where 1 ^ m ^ n is an integer initially set to \^]. If the output set is a B-coverage set, A l g o r i t h m 2.3 sets H to m and decreases m to f ^ ^ ] , where T and H are variables initially 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. A l g o r i t h m 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]). C o r o l l a r y 2.1. Algorithm  2.3 will select at most 11 nodes.  Proof. T h e proof is clear, as A l g o r i t h m 2.3 returns an output of A l g o r i t h m 2.2 (Line 17). • T h e o r e m 2.4.  Time complexity of Algorithm  2.3 is 0 ( n l o g n ) .  Proof. A l g o r i t h m 2.3 requires O ( n l o g n ) operations to sort the fist of neighbors ListA[l.. .n]. The computational complexity of A l g o r i t h m 2.2 is 0 ( n ) . Therefore, A l g o r i t h m 2.3 performs 0 ( n ) operations i n each iteration of the while loop. T h e while loop terminates after O ( l o g n ) iterations because it uses a binary search approach to find the m i n i m u m value of H. Consequently, the order of A l g o r i t h m 2.3 is 0 ( n l o g n -I- l o g n x n). • T h e o r e m 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 m i n i m u m weight of nodes i n Stmin is greater than or equal to that of other B-coverage sets. Let Nx s Stjnin be the node w i t h the m i n i m u m weight i n Stmin- Assume Ny\ has K neighbors w i t h 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 A l g o r i t h m 2.3 finds the m i n i m u m 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 m i n i m u m weight of nodes of the B-coverage set selected by A l g o r i t h m 2.3 is greater than or equal to the weight of Nx•  2.3.5  Similarity W i t h A Topology Control Algorithm  In [26] and [27], the authors proposed a cone-based topology control algor i t h m , 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 w i t h the m i n i m u m power Pa, such that i n every nonempty cone of degree a around NA, there is some node that NA can reach w i t h power P^. A cone is non-empty, if there is at least a node i n the cone that NA can reach using its m a x i m u m 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 i n the proposed forwardingnode selection algorithm. Therefore, the algorithm will 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 w i 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 b o t h 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 until there is a node i n each non-empty cone around NA- However, i n the forwarding-node selection algorithm, a node A^^ selects some nodes (the forwarding nodes) until there is a selected node i n 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 i n the network. A s mentioned earlier, 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  A l g o r i t h m 2.4 shows a general approach used i n several self-pruning broadcast algorithms [23, 28]. O u r proposed self-pruning broadcast algorithm employs this approach. Clearly, the m a i n design issue of A l g o r i t h m 2.4 is to determine whether or not to broadcast a received message. A t r i v i a l algor i t h m is to refrain broadcasting if and only if a l l the neighbors have received the message during the defer period. A l t h o u g h this algorithm is simple to implement, it has limited effect i n reducing the number of redundant broadcasts. 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 received the message by ^o- However, this broadcast is redundant if a l l such neighbors receive the message from other nodes after time to. T h i s scenario typically occurs when to is small compared to the m a x i m u m defer time. In the next section, we introduce a responsibility-based scheme ( R B S ) that can significantly reduce the redundant broadcasts. A l g o r i t h m 2.4 A general self-pruning algorithm 1: E x t r a c t the required information from the received message M 2: if M has been received before then 3: drop the message 4: else set a defer timer 6: end if 7: W h e n defer timer expires 8: decide whether or not to schedule a broadcast 5:  2.4.2  A Responsibility-Based Scheme  A l g o r i t h m 2.5 shows the proposed Responsibility-Based Scheme ( R B S ) . T h e m a i n idea of A l g o r i t h m 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^iSuppose NA stores ids of a l l its neighbors that have broadcast the message during the defer period. W h e n executed by a node A ^ i , A l g o r i t h m 2.5 first uses this information to determine which neighbors have not received the message (Lines 1-9 of A l g o r i t h m 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. T h e output of R B S determines whether or not the broadcast is redundant.  A l g o r i t h m 2.5 A responsibility-based scheme ( R B S ) Input: List A'. List of a l l neighbors of A ' ^ , and Lists'neighbors O u t p u t : true or false Liste •<— List A  List of broadcasting  for i = l\i ^ length(l/zsic); i++ do for J = 1; j ^ l e n g t h ( L i s t B ) ; do if dist(l/zsic[î], ListB\jy) ^ R then removeElement(Lzstc[î], Liste) break end if end for e n d 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]) check <— / a / s e break end if end for if check then return (false) end if e n d for r e t u r n (true)  ^ dist(Lisic[«], A^^) then  E x a m p l e 2.1. As shown in Figure 2.7, NA NA has received a message from Np. Note its neighbors. Therefore, it can easily find the message but NB and Nc have not. As required to broadcast because BE <RÂ  and  has five neighbors. Suppose that that NA has the position of all that NE and ND have received shown in Figure 2.7, NA is not  'CD  <CJ.  Figure 2.7: A n example of a n R B S decision.  E x a m p l e 2.2. Figure 2.8 shows an example of using the proposed selfpruning 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 required 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 transmission, 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. T h e o r e m 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 A l g o r i t h m 2.4, each node broadcasts a message at most once. Therefore, broadcasting will eventually terminate. B y contradiction, suppose 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. T h e network is connected, thus there is a p a t h between Ns and NT- Clearly, we can find two neighbor nodes NB and A^^ along the p a t h from A ^ to Ng such that NB has not received the message, while NA has. Consequently, {NA, NB) e A , thus A # 0 . A s 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. Therefore^ there must be a node Nc> such that Nc has received the message and C'B' < A'B' ^ R. T h i s result contradicts to (2.4), since {Nc, NB') 6 A . • T h e o r e m 2.7. Time complexity of the proposed RBS is 0{v?), the number of neighbors.  where n is  Proof. A l g o r i t h m 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- T h e 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 i t . Therefore, the complexity of the algorithm is 0{lm + kn).  •  2.4.3  A Property of the Proposed R B S  In the simulation section (Section 2.5), we show that the proposed R B S can significantly reduce the number of transmissions i n the network. In p a r t i c u lar, our simulation shows that using R B S , the average number of broadcasts is less t h a n one of the best-known approximations for the m i n i m u m number of required broadcasts. To justify this, we prove a property of the proposed RBS. 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 i n the area. Moreover, we have {ÔT)''e~^'^ Pr6(number of nodes i n 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. T h i s result is further confirmed by simulation i n Section 2.5.  E x a m p l e 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. S u p 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,)  (2.5)  = Prh{UÙPrh{C,n2)...Prh{Cn,).  L e m m a 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  • • •, C7^J ^ Pr6(C7^JPr6(C7e,) • • • PrbiCn,)-  PrbiCnrXn,,  Proof. T h e proof is by induction on the number of regions. T h e lemma is true if the number of regions is one (i.e., k = I). Suppose that the inequality holds for A; = d regions. W e have Pfb{Cni,Cn2',  • • • ) (njCiZd+i) = PfKCni-TZd+iXni-nd+t,-  • •, Cna-TZd+i),  (2.6) where is the complement of CTI^ and Ri — Rj is the collection of a l 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,, + Prb{Cn,JPrb{Cn,XiZ2,  • • •,  CnXn,,,)  • • •,  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 i n Figure 2.9, the disk 2^B,(R_ÂB) 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.  inside I{T>A,R,  DB,R).  Therefore, we have and  /LQBC ^ ^ and hence ACBD  ^  AQBD  ^  -  Therefore,  A(/(P  •  Figure 2.9: F i n d i n g a lower bound for  T h e o r e m 2.8. NB- We have  A{I(VA,R,'DB,R,'DQQ^)).  Suppose d ^ R is the distance between two nodes NA and Prb{Brd)  ^ 1 - e-^'"'  ,  where Prb{Brd) is the probability that NB broadcasts the message after receiving 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 * : VTVQ  6A :  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 L e m m a 2.6 we get inside I{VA,R,VB,R,VQ^QB))  Prb{3Np  =  Thus 00 = 1 - Prh{C)  Prb{Brd)  = 1 - 2  P^K\^\ = k)Prb{Ç.*\{\k\ = k)).  fe=0  where |A| is the cardinality of the set A . Therefore, using (2.9) and L e m m a 2.5 we get ^ 1 - 2  Prb{Brd)  (1 - e - ^ " ^ ) * ^ = 1 -  e"^^^"'^,  fc=0  where 7 is the area of the hatched crescent i n Figure 2.9 (collection of a l l points Q,QA> R a n d QB ^ R)  7  =  A(VB,R)  -  A{X{VA,R,VB,R))  = R^-n - 2 a r c c o s ( ^ ) ) + d ^ i î ^ _ (^)2.  • C o r o l l a r y 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) have  has a global m i n i m u m at a; = 0. Therefore, we l-e-""  for any real number a;. A s a result, we get  • It is also possible that node NB receives the message from more t h a n one neighbor i n 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 w i t h i n a constant factor of the optimal solution (minimum C D S ) , if it is provided w i t h p a r t i a l information about 2-hop neighbors.  2.5 2.5.1  Simulation Average Number of Nodes Selected by the Proposed Sliced-Based Algorithm  In Section 2.3, we proved that the proposed forwarding-node selection algor i t h m selects 11 nodes i n the worst case. In practice, the number of selected nodes is typically less t h a n 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 w i t h 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. A s shown i n Figure 2.10, the average number of selected nodes is less t h a n 6 and approaches 5 when n increases. Note that the proposed sliced-based selection algorithm does not necessarily select a B-coverage w i t h a m i n i m u m number of nodes. However, there is a sliced-based selection algorithm that can find  a B-coverage w i t h a m i n i m u m number of nodes i n O ( n l o g n ) and can consequently 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 t h a n that for the source node because of the optimization technique introduced i n Section 2.3.  1.5 i!  1 20  1 40  1 1 1 60 so 100 Number of neighbors  1 120  1 140  160  Figure 2.10: Average number of nodes selected by the proposed algorithm.  2.5.2  shce-based  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 message {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''^ w i t h distance 0 < d ^ R from each other. We uniformly placed nodes w i t h 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 i n 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. T h i s 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^. A s shown i n Figure 2.15, only 9 nodes (represented by stars) among 400 nodes broadcast the message.  Figure 2.11: Probability of broadcast for R = 300m.  Figure 2.12: Probability of broadcast for R = 400m.  Figure 2.13: Probability of broadcast for R — 500m.  Figure 2.14: Probability of broadcast for R = 600m.  600  800  1000  Figure 2.15: Broadcasting nodes i n a 1000 x lOOOm^ square area with 400 nodes.  2.5.3  Performance of Proposed Neighbor-Designating and Self-Pruning Algorithms  T h e m a i n objective of efficient broadcast algorithms is to reduce the number of transmissions. Therefore, we considered the ratio of broadcasting nodes over the t o t a l 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 r u n , we uniformly distributed N nodes i n 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. O n l y one broadcasting occurred i n each simulation r u n by a randomly selected node. Table 2.1 summarizes some of the parameters used i n ns-2. A s shown i n the table, the t o t a l number of nodes, N, varies w i t h i n 25 — 1000 and the transmission range varies w i t h i n 50 - 300 m. A s a result, the simulation covers very sparse and very dense networks as well as the networks w i t h 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. T h e performance of our proposed algorithm is compared w i t h the performance of L i u ' 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 A p . , where 1 ^ z ^ 6. If NA receives a new broadcast from another node, say N B , it first determines the p a r t i t i o n of A ^ , say Bp., i n which it is located. A s the basic forwarding rule, the node NA forwards the message if there exist at least one partition Api^ such that no other host can be found i n Bp. r\Ap^. Using the basic and advanced forwarding rules proposed i n [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 t h a n that of previous notable broadcast algorithms [31, 32]. A s proved earlier, our proposed neighbordesignating algorithm has lower computational complexity and selects fewer forwarding nodes t h a n Liu's algorithm. T h e simulation results, shown i n Figures 2.16 and 2.17, indicate two interesting facts. First, our proposed neighbor-designating algorithm does not require more broadcasts t h a n L i u ' s proposed broadcast algorithm. Secondly, the number of transmissions using  R B S is significantly lower t h a n the number associated w i t h the other implemented algorithms. In fact, as shown i n Figures 2.16 and 2.17, this number is even less t h a n one of the best-known approximations (ratio 8 approximation) for the m i n i m u m number of required broadcasts [16]. Note that in R B S , the probability that two close nodes broadcast the same message is very low. A s a result, the number of broadcasting nodes is statistically bounded i n a finite region (e.g., the transmission range of a node). However, using the slice-based and L i u ' s algorithm, the chance that two close nodes broadcast the same message is not negligible. For example, using L i u ' s a l gorithm, a node NA selects the smallest subset of its 1-hop neighbors w i t h the m a x i m u m coverage area, where the coverage area of a set of nodes is the union of their transmission coverage. A s expected, most of the nodes around the transmission boundary of A^^ will be selected by A^^ since they often have contributions i n the m a x i m u m 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. B o t h center and variance of the Gaussian distribution were randomly selected for each run. T h e variance was selected from the range 200-400 to avoid very dense population of nodes around the center of the distribution. A s shown i n Figure 2.18, the number of broadcasting nodes decreases for a l l the broadcast algorithms when a Gaussian distribution is used to distribute the nodes i n the region. T h e simulation results indicate that the R B S algorithm still performs significantly better t h a n other broadcast algorithms considered i n this work. In the second scenario, we used uniform distribution to distribute the nodes and evaluated the impact of message-reception failure on the performance of broadcast algorithms. We considered two networks of 100 and 400 nodes. T h e probability of message-reception failure was assumed to be equal a n d independent for each node i n the network. For b o t h networks, the m a x i m u m 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 i n these figures, the Edge Forwarding algorithm is the most robust broadcast algorithm against message-reception failure. T h i s 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. T h e  simulation results indicate that the slice-based algorithm is the least robust broadcast algorithm against message-reception failure. T h i s 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. Finally, we simulated the broadcast algorithms i n a mobile wireless settings. The nodes were initially distributed using a uniform distribution. In the simulation, we used random walk mobility model and set the m a x i m u m velocity to l O m / s . We fixed the transmission range to 250m and varied the total number of nodes w i t h i n 25 — 1000. The simulation results indicate that all the broadcast algorithms considered i n this chapter can achieve a high delivery ratio (above 9 5 % on average) for N ^ 50, where N is the total number of nodes i n the network. T h i s 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 i n 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 M o d e l Packet Size Bandwidth Size of Square A r e a 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  B r i e f Description  Edge Forwarding Liu's A l g . Ratio-8 Approx. Slice-Based A l g . RBS Alg.  Nodes divide their transmission range into six equal sectors Each node selects the smallest subset of its neighbors w i t h m a x i m u m 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  Reference [31] [10] [16] Section 2.3 Section 2.4  Table 2.2: Algorithms used i n the simulation  Total number of nodes  Figure 2.16: R a t i o 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 TrammlMlon range (meter)  2S0  300  Figure 2.17: R a t i o of broadcasting nodes vs. transmission range (uniform distribution).  -  200  400 600 Total number of nodes  RBS Algorithm R«tio-a Approximation Sllce-B«Md Algorithm Uu'» Algorithm Edg» Forwarding  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. failure (A^ = 100).  probability of message-reception  Probability of message-reception failure  Figure 2.20: Average delivery ratio vs. failure (A^ = 400).  probability of message-reception  2.6  Summary  In the first part of this chapter, we proposed a forwarding-node selection algorithm that selects at most 11 nodes i n 0 ( n ) , where n is the number of neighbors. T h i s limited number of nodes is an improvement over L i u ' s a l gorithm, which selects n nodes i n the worst case and has time complexity O ( n l o g n ) . Moreover, we showed that our proposed forwarding-node selection algorithm results i n fewer broadcasts i n 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 i n 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 ( C D S ) "onthe-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 , " D y n a m i c source routing i n ad hoc wireless networks," i n Mobile Computing, Imielinski and K o r t h , Eds. K l u w e r Academic Publishers, 1996. 13] S. N i , Y . Tseng, Y . Chen, and J . Sheu, "The broadcast storm problem i n a mobile ad hoc network," In Proc. ACM International Conference on Mobile Computing and Networking (MOBICOM), pp. 151-162, 1999. 14] M . C a r e y and D . Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness. New Y o r k , N Y , U S A : W . H . Freeman & Co., 1990. 15] B . C l a r k , C. Colbourn, and D . Johnson, " U n i t disk graphs," Mathematics, vol. 86, pp. 165-177, 1990.  Discrete  [16] P. W a n , K . A l z o u b i , and O. Frieder, "Distributed construction of connected dominating set i n 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 m i n i m u m C D S i n unit disk graphs," ACM Trans. Sensor Networks (TOSN), vol. 2, no. 3, pp. 444-453, 2006. 18] H . L i u , P. W a n , X . J i a , X . L i u , and F . Y a o , "Efficient flooding scheme based on 1-hop information i n mobile ad hoc networks," In Proc. of IEEE INFOCOM, 2006. [19] Y . Tseng, S. N i , and E . Shih, "Adaptive approaches to relieving broadcast storms i n 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 flooding i n wireless mobile ad hoc networks," In Proc. IEEE Wireless Communications and Networking Conference (WCNC), pp. 1124-1130, 2003. [21] W . L o u and J . W u , "Double-covered broadcast ( D C B ) : a simple rehable broadcast algorithm i n manets," In Proc. of IEEE INFOCOM, pp. 20842095, 2004. 22] J . W u and F . D a i , "Broadcasting i n ad hoc networks based on selfpruning," In Proc. of IEEE INFOCOM, 2003. 23] W . Peng and X . L u , " O n the reduction of broadcast redundancy i n 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, "Rangefree localization schemes i n large scale sensor networks," In Proc. ACM International Conference on Mobile Computing and Networking (MOBICOM), pp. 81-95, 2003. 25] A . Keshavarz-Haddad, V . Ribeiro, and R. Riedi, " D R B and D G C B : efficient and robust dynamic broadcast for ad hoc and sensor networks," In Proc. of IEEE Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), June 2007. 26] R. Wattenhofer, L . L i , P. B a h l , and Y . W a n g , "Distributed topology cont r o l for power efficient operation i n multihop wireless ad hoc networks," In Proc. of IEEE INFOCOM, pp. 1388-1397, 2001. 27] L . L i , J . Halpern, P. B a h l , Y . W a n g , 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 i n 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. C h a n g and R. Lee, " O n the average length of delaunay triangulations," BIT Numerical Mathematics, vol. 24, pp. 269-273, 1984. [31] Y . C a i , K . H u a , and A . Philhps, "Leveraging 1-hop neighborhood k n o w l edge for efficient flooding i n wireless ad hoc networks," In Proc. IEEE International Performance, Computing, and Communications Conference (IPCCC), pp. 347-354, 2005. 32] J . W u and H . L i , " O n calculating connected dominating set for efficient routing i n ad hoc wireless networks," In Proc. International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (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 i n Chapter 2) for the case where each node is provided w i t h partial information about its 2-hop neighbors. After a brief introduction, we explain the related work i n more details and specify the contribution of this work. A s discussed i n Chapter 2, broadcasting is a fundamental communication primitive, which has many applications, including route discovery i n 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 all redundant transmissions. T h i s is because the problem of finding the m i n i m u m Connected Dominating Set ( C D S ) i n a unit disk graph can be reduced to the problem of eliminating a l 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 i n 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 i n 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 m i n i m u m C D S and of designing an o p t i m u m 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 i a message exchanges. It is desirable to reduce this bandwidth overhead to improve the practicahty of the broadcast algorithm for ad hoc networks w i t h 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 i v i a l if it consists of a l 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-trivial C D S . In fact, we show that an extension of our proposed nont r i v i a 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 w i t h i n a constant factor of the optimum solution (i.e., m i n i m u m C D S ) . C o m p u t a t i o n a l overhead also plays an important role i n designing efficient broadcast algorithms. F l o o d i n g is an ideal broadcast algorithm i n terms of computational overhead, since each node requires almost no computation (it simply broadcasts the first copy of the received message). T h e existing broadcast algorithms typically require some computation for selecting forwarding nodes or for self-pruning. In this chapter, we show how to efficiently implement 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 algorithms. 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. A s mentioned earlier, finding the M i n i m u m 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 w i t h constant approximation ratio to the M C D S [35, 36]. T h e m a i n drawback of this solution is that maintaining a C D S is often costly i n networks w i t h frequent topology changes [37].  T h e 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 i n the network increases. T h e localized broadcast algorithms typically use A; ^ 0 rounds of information 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 i n the packets. O u r proposed algorithm is based on one round of information exchange but uses partial 2-hop neighbor information obtained by extracting the information piggybacked i n 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 i n 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 i n unreliable communication 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 i n [40 . M o s t 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 (receiverbased). In neighbor-designating algorithms [37, 41], the forwarding status of each node is determined by other nodes. In other words, each broadcasting node selects a subset of its A;-hop neighbors to forward the message. T h e m a i n design challenge for neighbor-designating algorithms is to choose a small subset of nodes to forward the message. For example, i n [37], the a u thors proposed a broadcast algorithm based on 1-hop neighbor information that selects the smallest subset of its 1-hop neighbors w i t h the m a x i m u m 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 m i n i m u m number of 1-hop neighbors that cover a l l 2-hop neighbors. T h i s procedure is known as the m i n i m u m forwarding set problem. There are heuristic algorithms i n the literature that give a constant approximation ratio to the m i n i m u m forwarding set problem [42]. However, as shown i n [41], even an optimal solution to this problem may not result i n a small-sized C D S i n the network. In [41], the authors extended the m i n i m u m forwarding set problem to the case where the complete 2-hop topology inform a t i o n is available. Note that two rounds of information exchange provide partial topology information for the 2-hop neighbor set. To get complete 2hop topology information, each node must either get the position information of the 2-hop neighbors or perform three rounds of information exchange [41]. T h e authors show that their proposed algorithm can provide a probabilistic 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 m a i n design challenge w i t h regard to self-pruning algorithms is to find an effective selfpruning condition. Different self-pruning conditions have been proposed i n 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 algorithms do not provide a constant approximation ratio to the optimal solution (MCDS).  3.1.2  Our Contribution  In the first part of the chapter, we consider two general structures commonly used i n neighbor-designating and self-pruning algorithms based on 1-hop neighbor information. We show that using these structures, we are not able to guarantee b o t h full delivery and a good bound on the number of forwarding nodes i n the network. A n open question is whether localized broadcast algorithms can provide b o t h full delivery and constant approximation to the optimal solution ( M C D S ) . A s 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 constant approximation ratio to the optimal solution [43, 46]. One contribution of this chapter is to show that localized broadcast algorithms are i n fact able  to guarantee a reasonable bound on the number of forwarding nodes. In particular, we prove that our proposed self-pruning algorithm can provide full delivery as well as guaranteeing a constant approximation ratio to the o p t i m a l solution ( M C D S ) if the nodes are allowed to piggyback information w i t h the broadcast packet. We design efficient algorithms w i t h nearly o p t i m u m computational complexity to compute the proposed self-pruning condition. It is proved i n [35] that every distributed algorithm for constructing a nont r i v i a 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 algorithms. 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 message 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 b a n d w i d t h requirements by reducing the amount of piggybacked information i n each broadcast packet. We relax several system-model assumptions, or replace them w i t h 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 w i t h one of the best broadcast algorithms based on 1-hop information. T h e simulation results show that the proposed broadcast algorithm performs better t h a n 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 i n Chapter 2. We discuss how to relax some of these assumptions i n Section 3.5. We consider a wireless network as a collection of N nodes represented bypoints located at their positions i n a 2-D plane. E a c h node is equipped w i t h an omni-directional antenna that has radio transmission range of R. T w o distinct nodes are called neighbors if they are i n transmission range of each other (i.e., the Euclidean distance between them is less t h a n or equal to R). We assume that each node is able to obtain its position using an existing positioning technique, such as the G l o b a l Positioning System ( G P S ) . E a c h  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. T o prove that a broadcast algorithm guarantees full delivery, we assume that nodes are static during the broadcast and that the M e d i u m Access C o n t r o l ( M A C ) layer is ideal, i.e., there are no transmission errors such as collision a n d 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 i n neighbordesignating 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 b o t h full delivery and a good bound on the number of forwarding nodes i n the network.  3.3.1  Neighbor-Designating Algorithms  A l g o r i t h m 3.1 shows a general structure of neighbor-designating broadcast algorithms based on 1-hop neighbor information. A s shown i n A l g o r i t h m 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 represent a node A ^ ^ w i t h a point A located at its position and use PQ to denote the E u c l i d e a n distance between two points P and Q. Suppose A l g o r i t h m 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 i n 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 i n order to guarantee full delivery. For example, suppose NA is a node on the boundary of the network. A s shown i n 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. T h i s 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. T h i s implies that most of the nodes around the boundary of the network (including a l l the nodes on the convex hull [47 of the network) w i l l broadcast the message if A l g o r i t h m 3.1 is used as the basic structure i n 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 A l g o r i t h m 3.1 as its basic structure.  Convex Hull  Figure 3.1: A n example of a node on the network boundary.  T h e o r e m 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. A s shown i n Figure 3.2, suppose that a l l the nodes are located on a line segment AB of length R or on a circle CQ R w i t h a radius ^, where R is the radio transmission range. For every node NA, we can find a point  A l g o r i t h m 3.1 A general structure of neighbor-designating algorithms 1: E x t r a c t 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: 6:  7: 8: 9: 10: 11:  set a defer timer end if W h e n defer timer expires Based on 1-hop neighbor information: Select a subset of neighbors to forward the message A t t a c h the list of forwarding nodes to the message 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 w i l l broadcast the message. However, one broadcast is enough to transmit a message to a l l the nodes i n the network for each scenario. Consequently, the ratio of broadcasting nodes over the m i n i m u m number of required broadcasts is N. •  R  B  Scenario 1  t  Scenario 2  Figure 3.2: T w o worst-case examples for Theorem 3.1.  3.3.2  Self-Pruning Algorithms  A l g o r i t h m 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. W h e n 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 b o t h full delivery and a good bound on the number of forwarding nodes. Note that i n A l g o r i t h m 3.2, no information is piggybacked w i t h the broadcast packet. A n extension of A l g o r i t h m 3.2 is to allow nodes to piggyback some information i n the broadcast packet. Clearly, this extension of A l g o r i t h m 3.2 is stronger t h a n b o t h A l g o r i t h m 3.1 and A l g o r i t h m 3.2. In the next section, we show that a broadcast algorithm based on 1-hop neighbor information can guarantee b o t h 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 A l g o r i t h m 3.2. T h e o r e m 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 a l l the nodes are on two circles C Q E and CQ m centered at O w i t h radii f and  respectively.  A s shown i n 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. and  Note that A'^.  do not share any neighbor. Since they have only 1-hop neighbor  information and there is no information piggybacked i n the broadcast packet, N^i (or A^B.) cannot be sure whether its corresponding node has received the message.  Therefore, i n 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 m i n i m u m number of required broadcasts is e{N).  •  Figure 3.3: A worst-case example for Tlieorem 3.2.  A l g o r i t h m 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 i n 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 neighborknowledge-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 ) . A s its basic structure, the proposed broadcast algorithm ( A l g o r i t h m 3.3) uses a simple extension of A l g o r i t h m 3.2 i n which each node is allowed to piggyback some information w i t h i n the broadcast packet. In A l g o r i t h m 3.3, each node adds a list of its 1-hop neighbor ids and positions into the broadcast packet. U p o n receiving a packet, this information is extracted and used to determine the node's status (forwarding/non-forwarding) based on the following selfpruning condition. Definition 3.1 (Responsibility C o n d i t i o n ) . Node NA is pruned (has nonforwarding 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 NAA l g o r i t h m 3.3 T h e proposed broadcast algorithm 1: E x t r a c t the required information from the received packet 2: A d d the broadcasting node and its 1-hop neighbor information (except 3: 4: 5: 6: 7:  8: 9: 10: 11: 12: 13:  the node's own information) to the list Listfff if the message has been received before then drop the message else set a defer timer end if W h e n defer timer expires if the responsibility condition is satisfied then Remove the previous information attached to the message A t t a c h the list of 1-hop neighbors to the message Broadcast the packet end if  Suppose NA computes a list of nodes that have received the message {List^^) by collecting the information piggybacked i n the broadcast packets. To check the responsibility condition, A^^ can first determine which neighbors have not received the message. T h e 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 responsibihty condition. E x a m p l e 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 A l g o r i t h m 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 connected and the M A C layer is ideal, i.e., there is no communication error. A s mentioned earlier i n Section 3.2, even flooding cannot guarantee full delivery without these assumptions. T h e o r e m 3.3. Algorithm will receive the message.  3.3 guarantees that all the nodes in the network  Proof. U s i n g A l g o r i t h m 3.3, each node broadcasts the message at most once. Therefore, broadcasting will eventually terminate. B y contradiction, suppose there is at least one node that has not received the message after the  broadcast termination. Let us consider the set A = {{Nx,  and Ny are neighbors, Nx has received the message and  NY)\NX  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. T h e network is connected, thus there is a p a t h between Ns and NT- Clearly, we can find two neighbor nodes NB and A^^ along the p a t h from NT to Ns such that NB has not received the message, while NA has. Consequently, {NA,NB) e A , thus A 7^ 0 . A s a result, e A s.t. V ( i V x , Ny) e A : WB'  3{NA',NB')  (3.1)  ^ XY.  Clearly, NA' has not broadcast since NB' has not received the message. Therefore, there must be a node Nc such that Nc has received the message and C^' < ^ R. T h i s 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 a disk DQ E with a radius j is bounded by a constant. Proof  A s shown i n Figure 3.5, consider three disks  centered at O w i t h radii j , ^  R, DQ  SR  and  DQBR,  and ~ , respectively. Let us define  = {P\P e Ui and P i  ni-n2  DQ  nodes inside  U^},  where TZi and 7^-2 are two regions and P is a point. Suppose k is the m i n i m u m number such that for every set of k points Pi e DQ 5R — DQ SH, 1 ^ Z ^ A;, ' 4  ' 4  we have  3Pi,Pj: Note that the area Dn ^ ' 4  i^j  and  PiPj  ^ - .  - Dr, m can be covered w i t h a constant number of ^ ' 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 w i l l contain more t h a n one point. For two points Pi and P j inside a disk w i t h 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 t h a n '  4  or equal to k. B y contradiction, suppose that there are more t h a n A; broadcasting 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 corresponding neighbor NB, such that A^^. ^ List^^ node Nc e List^^^, where Listff^  and AiBi ^ CBi for every  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 V I ^ 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 w i t h i n the  broadcast packet. Therefore, NB, e List^'f; , thus NB-  NB.- It follows that  NBX - - - A^Bfc are A; different points inside DQ BR — DQ SR . Therefore ' 4  3NB„NB,--  i<j  and  B^Bj^^-  T h i s is a contradiction, because Ajg. 6 List^^ AjBj  > R =>  AjBj  ' 4  (3.3)  and based on (3.2) and (3.3) >  BiBj.  Thus, according to the responsibility condition, NA^ is not responsible for NBy T h e o r e m 3.4. Algorithm 3.3 gives a constant approximation optimal solution (MCDS).  • ratio to the  Proof. Clearly, a disk w i t h radius R can be covered w i t h a constant number of disks w i t h radius f . Therefore, based on L e m m a 3.1, the number of broadcasting nodes inside a disk w i t h radius R is bounded by a constant Cmin- Let \MCDS\ be the number of nodes i n the M C D S . E a c h broadcasting node is inside the transmission range of at least one node i n t h M C D S . O n the other hand, the number of broadcasting nodes inside the transmission range of each node i n the M C D S is bounded by Cmin- Therefore, the total number of broadcasting nodes is not more t h a n Cmin x \MCDS\. •  Figure 3.5: Three co-centered disks; A ^ ^ . e DQ R and A ^ B . e DQ SR - DQ SR.  T h e foUowing theorem shows that the message complexity of the proposed 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 will show that the message size can be reduced to a constant number of bits by removing the node id from the message and using a constant number of bits to represent each node's position. T h e o r e m 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 i n the proposed broadcast a l gorithm. F i r s t , each node broadcasts its id and position i n a short Hello message. Second, each broadcasting node piggybacks the list of its 1-hop neighbor ids and positions into the broadcast packet. We will 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 w i t h its position. A s 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 i n at most Cmin + 1 messages, including the Hello message. Consequently, the total number of messages is not more t h a n (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 P r o b l e m ( 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 i n V to at least one point i n Q. One approach to solving C P P is to find the closest point i n V to every point i n Q. T h e t r i v i a l algorithm for finding the closest point i n P to a query point Q 6 Q is to compute the distance from Q to ah the points i n "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 i n d i n g the closest point i n P to a query point Q e Q is a well-known problem called the Nearest Neighbor Search ( N N S ) 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 i n fc-dimensional space. A fcrf-tree for the set of 2-D points V can be constructed i n O ( m l o g m ) . Moreover, the computational complexity of a query is O ( l o g m ) [47]. Therefore, using A;d-tree, the C P P can be solved i n 0 ( m l o g m + n l o g m ) . Similarly, we can use the Voronoi diagram to solve C P P . T h e Voronoi diagram is a partitioning of a plane w i t h n generating points into convex polygons called Voronoi cells, such that each cell contains exactly one generating point and every node i n 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 i n 0{n log n) and that each cell has 0{n) edges i n 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 i n P to a query point Q if and only if Q is i n the Voronoi cell of PQ. We can check whether a query point Q is in the Voronoi cell of PQ i n O ( l o g m ) , since the Voronoi cell of Po is a convex polygon w i t h at most 0 ( m ) edges. Therefore, the C P P can be solved i n 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 i n 0 ( m l o g / i ) , where h is the number of edges of the cell. T h e  average number of vertices of a Voronoi cell is less t h a n 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 i n 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 i n the set Q. O n the other hand, every algorithm to solve the C P P has to consider a l l the points i n V if PQ is the closest point i n P to a node i n Q. Thus, f2(m) is also a lower bound for such algorithms. Considering b o t h 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 i n 0 ( ( n + m ) l o g m ) , i n the worst case. These algorithms are nearly optimal i n terms of computational complexity, because log m is a small factor i n practice. Moreover, by constructing the Voronoi ceU of PQ, we showed that the C P P can be solved i n 0{n + m) i n the average case. T h e o r e m 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 A l g o r i t h m 3.3, a node A^^ stores the broadcasting neighbors' information and their 1-hop neighbors' information (except Ayi's i n formation) i n List^^. T h e node NA can compute List^°^^^'^, the list of its neighbors that have not received the message, i n 0 ( / x n), where 1 ^ / n is the number of broadcasting neighbors and n is the t o t a l 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 i n List^^. Suppose Q =  {Qi,Q2,...,Qk}  is the set of points located at the position of the nodes i n List%°^^^'^. A s mentioned earlier, by constructing the Voronoi cell of P Q , we can compute the C P P i n 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 VP  6  P :  QPQ^  QP.  A s shown i n the proof of Theorem 3.4, I (the number of broadcasting neighbors of NA) is bounded by a constant. Moreover, we have k ^ n, m ^ I x Ac and n ^ A ^ , where A Q is the m a x i m u m node degree of the network. Therefore, the complexity of computing the responsibility condition is 0{l X n) + 0{{m+k)  logm)  = O(AGlogAG).  Note that the C P P can be solved i n 0{k + m) i n 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 A l g o r i t h m 3.3, each forwarding node piggybacks the list of its 1-hop neighbors i n 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 corresponding 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 a l l its neighbors and NB i List^^ is a neighbor of NA- T h e node NB is required i n 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 i n computing the responsibility condition of Nc, we can find a node i n List^^^ that leads to the same result.  •  L e m m a 3.2 shows that forwarding nodes can save b a n d w i d t h by piggybacking the list of their representative neighbors instead of the list of a l l their neighbors. Clearly, finding the m i n i m u m representative neighbor set is equivalent to computing the m i n i m u m 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 m i n i m u m representative set of V is unique and can be computed i n 0{\V\ log\V\). L e m m a 3.3. Suppose V is a set of points inside the circle Co R and the minimum  representative PeSmin  set ofV. «  We have  JVBCell{P):  Synin is  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. fore, for every point Q outside the circle we have 3P' e V :  P'Q ^  PQ,  There-  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 i n the m i n i m u m 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 i n every representative set of V including its m i n i m u m representative set. • T h e o r e m 3.7. Suppose V is a set of points inside a circle CO,R- The minimum representative set ofV is unique and can he computed m 0(|P| log Proof. Based on L e m m a 3.3, a point P is i n the m i n i m u m representative set of V if and only if 3V 6 Cell{P) : ÔV > R. There is a single Voronoi diagram associated w i t h each set of generating points. Therefore, the m i n i m u m representative set is unique. F r o m L e m m a 3.3, it also follows that the m i n i m u m representative set of P is a subset of every representative set of V. To compute the m i n i m u m 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- T h e Voronoi diagram of V can be computed i n 0(|P| log [Pj). Moreover, the average number of vertices of a cell is less t h a n six [47]. In other words, the t o t a l number of vertex-checking operations is less t h a n 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 m i n i m u m representative set of V. T h i s situation occurs, for example, when all the  points i n V are located i n a line segment or on a circle. However, it can be shown that h m M ^ i l i l ) ^ 0, IPHoo \V\ where E{\Smin\) is the expected cardinality of the m i n i m u m representative set of V. In order to avoid complex analytical analysis, we used simulation to analyze E{\Smin\)- T h e simulation results are presented i n Section 3.6. Suppose that the forwarding nodes can piggyback a list of their representative neighbors instead of the list of a l l their neighbors. In this case. Theorem 3.8 shows that a node can simply avoid broadcasting if it is not i n the list of the nodes piggybacked i n at least one received packet. T h e o r e m 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 all 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 i n the representative neighbor set of N B , there exists a node No ^ NA such that ND is i n the representative neighbors set of NB and DC  ^  AC.  Note that DC AC, because based on L e m m a 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  T h e assumptions made i n Section 3.2 are often used i n the existing broadcast algorithms i n order to model the network. Some of these assumptions are  not practical. For example, a node may obtain its position using the G l o b a l Positioning System ( G P S ) . However, the position is not accurate due to several sources of error including positioning error and the limited 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 w i t h more practical ones i n order to improve the practicality of our proposed broadcast algorithm. We show that a l l of the extensions of the proposed algorithm can provide b o t h full delivery and a constant approximation ratio to the optimal solution under the new assumptions.  3.5.1  Broadcasting Under Uncertain Position Information  A s 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 w i t h the fact that a finite number of bits is used to represent the position information. Typically, each node i n 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 b a n d w i d t h and power overhead, it is desirable to use as few bits as possible to represent the position information added i n the Hello messages or the broadcast packets. In this section, we show that a constant number of bits suffices to maintain the m a i n properties of the proposed algorithm. Let 5 be an upper bound on the m a x i m u m position error and S S an upper bound for m a x i m u m error i n computing the distance between two points. Suppose that £ is known by a l l the nodes i n the network. We have A B - £ ^  T{ÂB)  ^JB  + £,  (3.4)  where T{AB) is the approximated distance between the points A and B. A l g o r i t h m 3.4 shows how to compute the responsibility condition under u n 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., a l l of the broadcasting nodes together w i t h their 1-hop neighbors. A l g o r i t h m 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)  T h e output of A l g o r i t h m 3.4 determines whether the responsibility condition is satisfied. A l g o r i t h m 3.4 C o m p u t i n g the responsibihty condition under uncertain position information Input: List%''^, Listy^'^'^, Listfif and the max error c O u t p u t : 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: r e t u r n true 12: end if 13: end for 14: r e t u r n false  T h e o r e m 3.9. Algorithm 3.3 guarantees full delivery under uncertain position information if it uses Algorithm 3.4 to compute the responsibility condition. Proof. T h e proof is similar to that of Theorem 3.3. T h e broadcasting w i 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. T h e network is connected, thus there is a path between Ns and NTClearly, we can find two neighbor nodes NB and A^^ along the p a t h 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'.  T h i s result contradicts (3.6), since {Nc,  NB') S A .  •  T h e o r e m 3.10. Using Algorithm 3.4 to compute the responsibility condition, the proposed broadcast algorithm (Algorithm 3.3) guarantees a constant approximation ratio to the optimum solution under uncertain position information 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 w i t h a radius j is bounded by a constant. Using the same approach used i n the proof of Theorem 3.4, it then follows that the t o t a l number of broadcasting nodes is bounded by a constant factor of that of the o p t i m u m solution. Let DQ |, DQ m and DQ SR be three disks centered at O w i t h radii ~, ^ and respectively. Suppose k is the m i n i m u m number, such that for every set of k points Pj e DQ^R — DQ3E, 1 ^ i ^ A;, we have 3Pi, Pj :  i^  j  and  ^  ^ AP.  Note that j is bounded by a constant, so the area covered w i t h a constant number of disks w i t h radius  DQ5R  —  DQÎR  can be  If the number of  points inside D Q  - D Q m is greater t h a n the number of covering disks, at  ' 4  ' 4  least one covering disk will contain more t h a n one point. For two points Pi and P2 inside a disk w i t h 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 t h a n or equal to k. B y contradiction, suppose that there are more t h a n 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^^^ : where List^^  r{AiBi)  r{BiC)  + S,  is the list of nodes that have received the message based on  A ' ^ . ' s collected information. Suppose 1 are neighbors, because AiAj  < j ^ k.  Nodes A T ^ . and NAJ  ^ ^. Recall that A ^ ^ . piggybacks the hst of a l l  its neighbors w i t h i n 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 i n the list of nodes piggybacked by NAÇ, i n the broadcast packet. T h u s n^i^k:  Nee  List^^.  It follows that VI  N B . ^ D Q ^ -  A;:  O n the other hand, A ^ B . is a neighbor of A ^ i ^ , thus NB^ e D Q 5R .  Conse-  quently, A;:  VI  NB^  e  DQ5E  -  DQm-  Thus, R AiBi > - .  yi^i^k:  (3.7)  There are A; different nodes NB^ • • • NB,, inside D Q SR - D Q ZR. Therefore, ' 4  3A^B.,A^B.  :  i<j  and  BiBj ^ XR.  +  B^j  + 2£.  F r o m ( 3 . 4 ) we have TiB^Bj)  ' 4  (3.8)  Thus, using (3.8) we get r{BiBj)  + S^-  O n the other hand, we have AjBj  R  + S.  (3.9)  > ^. Hence,  r{AjBj)  - £ > ^ - 2 £ .  (3.10)  Since £ ^ f , we have R  ^  R  ^^  Thus, based on (3.9) and (3.10) we get V{BiBj)  +e  < V{AjBj)  - S  T h i s result is a contradiction, because based on (3.5), A^^^. is not responsible iox  NBJ.  •  E x a m p l e 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 i n Theorem 3.10, A l g o r i t h m 3.3 can guarantee a constant approximation ratio to M C D S if the m a x i m u m error is bounded by a factor of the transmission range. A s a result, employing the same approach used in the proof of Theorem 3.5, we can show that the message complexity of A l g o r i t h m 3.3 under uncertain position information is still 0{N), where N is the t o t a l number of nodes i n 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 i n an L x L square area. Clearly, each node requires an infinite number of bits i n general to precisely represent its position. However, allowing errors i n position information, node position can be represented by a limited number of bits, provided that the size of square area is finite. For example, assume that we allow the m a x i m u m position error of aR. A s shown i n F i g m e 3.6, the L x L square area can be partitioned into r L ] X f y ^ l grid cells of size y/2aR x ^/2aR. Let V2aR the tuple (/, J ) denote the coordinate of the cell i n the grid. For instance, (1,1) indicates the bottom left cell of the gird. Suppose each node uses the coordinate of the cell i n 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 m a x i m u m 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 —  •  Position error (2.1)  (2.2) M a x i m u m position  (1,1)  on  (1.2)  Figure 3.6: Partitioning the network into square cells.  L e m m a 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 i n which NA is located and that the side of each grid cell is \/2aR. Node NA can transmit the tuple (z  moda^J+2),i  m o d a ^ J + 2))  a  to node NB- Suppose {i,j) cells such that  and  a  are the coordinates of two different  i = i'  mod([^J+2),  j^f  mod([^J+2).  and  Let Pi and P^ be two points inside the cells is easy to show that ^ ( L ^ J + 1) X {V2aR)  ^ 2  and  =>  P^2>  respectively. It  2R.  It follows that a circle w i t h radius R cannot intersect b o t h cells. Therefore, NB can uniquely identify the cell using the tuple {i  m o d a ^ J + 2),j  a  m o d ( [ ^ J + 2)).  a  Consequently, NA is required to transmit only  \  a  J  a  bits, which is constant if ^ is bounded by a constant. Node NB can approximate the position of NA by taking the position of the center of the cell. • A s mentioned earlier, the message complexity of A l g o r i t h m 3.3 is 0{N) under uncertain position information if the m a x i m u m position error is bounded. Moreover, using L e m m a 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. A l t h o u g h 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 i n transmission range of N^.. Let G be an undirected graph obtained by removing u n i 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 i n G (i.e., they are i n 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 i n the Hello message. Moreover, assume that the forwarding nodes include the lower bounds of their neighbors' transmission ranges i n the broadcast packets. T h e 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 i n the proof of Theorem 3.3, we can show that A l g o r i t h m 3.3 guarantees full delivery i n a heterogeneous network if it employs the new responsibility condition. Suppose Rmin is a lower bound for the transmission ranges of all the nodes i n the network and Rmax is an upper bound. T h e following theorem shows that the proposed broadcast algorithm can still guarantee a good bound on the number of forwarding nodes i n a heterogeneous network if is bounded by a constant.  T h e o r e m 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^,  O w i t h radii  D^ZR^  and  ^^f^ and  DQ  be three disks centered at  R^^J^^^  + Rmax, respectively. Suppose k is the  m i n i m u m number such that for every set of k points Pi e D „ R ^ ^ ^ , ^ D^ 3R^i„,  1 ^ z ^ fc, we have  3Pi, Pj-. Note that  -  i^  j  and  PiPj  ^  Pmin  is bounded by a constant, so the area D^  R „ J „ 4  , „ 'T.-^max  —D^^  SR.  4 mm can be covered w i t h a constant number of disks w i t h radius If the number of points inside D„ R^J^ , ^ - D „ 3 f l ^ ^ „ is greater t h a n the number ^ ,  of covering disks, at least one covering disk w i l l contain more t h a n one point. For two points P i and P2 inside a disk w i t h 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 i n the proof of L e m m a 3.1, we can show that the number of broadcasting nodes inside D Q R^J^ is less t h a n '  4  or equal to k. Since is bounded by a constant, a disk w i t h radius Rmax can be covered w i t h a constant number of disks w i t h radii Rmin- It follows that the t o t a l number of broadcasting nodes is bounded by a constant factor of that of the o p t i m u m solution (refer to the proof of Theorem 3.4).  •  3.5.3  Broadcasting in Three-Dimensions  We assumed i n Section 3.2 that the nodes are placed i n a 2-D plane. In general, the nodes can be located i n 3-D space, as the network area may not be perfectly flat. In this case we assume that the nodes are provided w i t h their position i n 3-D. Interestingly, a l l the properties of the proposed broadcast algorithm are preserved i n 3-D. A s s u m i n g AB as the Euclidean distance of two points i n 3-D, we can use the proof of Theorem 3.3 to show that A l g o r i t h m 3.3 guarantees full dehvery i n 3-D space. Note that the transmission range of a node i n 3-D is a sphere. Replacing circles by spheres i n the proofs of L e m m a 3.1 and Theorem 3.4, we can similarly argue that A l g o r i t h m 3.3  guarantees a constant approximation ratio to tlie optimal solution i n 3-D. Finally, using a technique similar to that used for 2-D, we can show that, i n 3-D, the proposed algorithm not only preserves its m a i n properties under u n certain position information (provided that the m a x i m u m error is bounded) but also can benefit from the proposed bandwidth-overhead reduction technique introduced i n Section 3.4.3.  3.6  Simulation  3.6.1  Reducing Bandwidth Overhead  A s shown i n 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 m i n i m u m representative set. For a given number of neighbors 1 ^ n < 500, we randomly put n points inside a unit circle and computed the m i n i m u m 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 i n Figure 3.7, the ratio •^d'^™"-!) decreases as the number of neighbors increases. For instance, the m i n i m u m number of representative nodes is on average less t h a n 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 t o t a l 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 r u n , we uniformly distributed N nodes i n a 1000 X 1000 square area. A randomly generated topology was discarded if it leaded to a disconnected network. O n l y one broadcast was initiated i n each simulation r u n by a randomly selected node. Table 3.1 summarizes some of the parameters used i n 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 i n a square area of  Figure 3.7: The ratio  ^il^^^^l)  x  100 against the total number of neighbors.  1000 X lOOOm^. A s shown i n this figmre, only 10 nodes (represented by stars) among 400 nodes broadcast the message. Figures 3.9 and 3.10 show the r a tio of the number of broadcasting nodes over the total number of nodes. To get the results shown i n 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 w i t h that of the broadcast algorithm proposed i n [37]. In [37], L i u et al. showed that the number of broadcasting nodes using their proposed flooding algorithm is significantly lower t h a n that of previous notable broadcast algorithms [48, 49 . We also considered the ratio-8 approximation of M C D S [35] as a benchmark. A s shown i n 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. T h i s property can further justify why the proposed broadcast algorithm can significantly reduce the number of transmissions i n the network. A n o t h e r metric evaluated using simulation was the algorithm delay, which we define as the time between the first and the last transmission i n a single  message broadcast. Figure 3.11 shows the average delay of our proposed algorithm and compares it w i t h that of L i u ' s broadcast algorithm. A s shown in this figure, the average delay of our broadcast algorithm is 80% to 50% of that of L i u ' 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 i n position information. We set the transmission range to R = 250 meters and fixed the m a x i m u m 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 w i t h i n 25 — 1000. A s shown i n Figure 3.12, the performance of the broadcast algorithm slightly degrades as the m a x i m u m position error increases. Finally, we evaluated the performance of the proposed algorithm for the case where nodes can have different transmission 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 m i n i m u m transmission range. The value of Rmin varied w i t h i n 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 i n 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 M o d e l Packet Size Bandwidth Size of Square A r e a 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 i n a 10^ x lO^m^ square area witli 400 nodes.  Figure 3.9: R a t i o of broadcasting nodes vs. transmission range.  1r 4  I  Proposed Algorithm  Figure 3.10: R a t i o of broadcasting nodes vs. total number of nodes.  Figure 3.12: R a t i o of broadcasting nodes of the proposed algorithm w i t h uncertain position information.  .R^«=150 meters =175 meters -R^=225 meters  400 600 Total number of nodes  1000  Figure 3.13: R a t i o of broadcasting nodes of the proposed algorithm i n a network w i t h nodes having different transmission ranges.  3.7  Summary  We considered two general structures typically used i n broadcast algorithms based on 1-hop neighbor information. We showed that a broadcast algorithm cannot guarantee b o t h 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 b o t h full delivery and a constant approximation ratio to the o p t i m a l solution. T h e 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 b a n d w i d t h overhead. We then relaxed several system-model assumptions, or replaced them w i t h 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 Y o r k , N Y , U S A : W . H . Freeman & C o . , 1990. 34] B . C l a r k , C. C o l b o u r n , and D . Johnson, " U n i t disk graphs," Mathematics, vol. 86, pp. 165-177, 1990.  Discrete  [35] P. W a n , K . A l z o u b i , and O. Prieder, " D i s t r i b u t e d construction of connected dominating set i n 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 m i n i m u m C D S i n unit disk graphs," ACM Trans. Sensor Networks (TOSN), vol. 2, no. 3, pp. 444-453, 2006. 37] H . L i u , P. W a n , X . J i a , X . L i u , and F . Yao, "EfRcient flooding scheme based on 1-hop information i n mobile ad hoc networks," In Proc. of IEEE INFOCOM, 2006. [38] Y . Tseng, S. N i , and E . Shih, " A d a p t i v e approaches to relieving broadcast storms i n 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 flooding i n wireless mobile ad hoc networks," In Proc. IEEE Wireless Communications and Networking Conference (WCNC), pp. 1124-1130, 2003. 40] P. Kyasanur, R . Choudhury, and I. G u p t a , "Smart gossip: A n adaptive 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 . L o u , and F . D a i , "Extended multipoint relays to determine connected dominating sets i n manets," IEEE Trans, on Computers, vol. 55, no. 3, pp. 334-347, 2006. 42] G . Calinescu, I. M a n d o i u , P . - J . W a n , and A . Zelikovsky, "Selecting forwarding neighbors i n wireless ad hoc networks," Mobile Networks and Applications, vol. 9, no. 2, pp. 101-111, 2004. [43] J . W u and F . D a i , "Broadcasting i n ad hoc networks based on selfpruning," In Proc. of IEEE INFOCOM, 2003. 44] W . Peng and X . L u , " O n the reduction of broadcast redundancy i n 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, " D o m i n a t i n g sets and neighbor elimination-based broadcasting algorithms i n wireless networks," IEEE Trans, on Parallel and Distributed Systems, vol. 13, pp. 14-25, 2002. 46] J . W u and W . L o u , "Forward-node-set-based broadcast i n clustered mobile ad hoc networks," Wireless Communications and Mobile Computing, vol. 3, no. 2, pp. 155-173, 2003. [47] M . de Berg, M . van Kreveld, M . Overmars, and 0 . Schwarzkopf, Computational Geometry: Algorithms and Applications, 2"*^ ed. New Y o r k : Springer-Verlag, 2000. 48] Y . C a i , K . H u a , and A . Philhps, "Leveraging 1-hop neighborhood knowledge for efficient flooding i n wireless ad hoc networks," In Proc. IEEE International Performance, Computing, and Communications Conference (IPCCC), pp. 347-354, 2005. 49] J . W u and H . L i , " O n calculating connected dominating set for efficient routing i n ad hoc wireless networks," In Proc. International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (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 encountered i n wireless ad hoc networks. It can significantly disrupt the communications 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 i n the network, "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. T h e wormhole attack is much more powerful if it is launched by more t h a n one attacker. In this case, attackers can t u n 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 d a t a or control packets. T h e wormhole attack can be launched i n two different modes. In the hidden 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. T h e existing wormhole 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 i n 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 i n the routing as legitimate nodes and use the wormhole to deliver the packets sooner a n d / o r w i t h a smaller number of hops. A s 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 shortestpath routing protocols. W h e n 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 t h a n (1 - ^) of a l l of the communications. We also analyze the effect of the wormhole attack i n which the malicious nodes target a specific node (such as the sink node i n a wireless sensor network). In this scenario, we show that two attackers can disr u p t / c o n t r o l 30% to 90% of a l l communications between the target node and the other nodes i n the network. We explain how three malicious nodes can d i s r u p t / c o n t r o l almost a l l of the communications independent of target node location i n the network. A l l analytical results are further confirmed by simulation. T h e wormhole attack may have difi'erent effects on different network topologies. We show how to compute the m a x i m u m effect of the wormhole attack on a given network topology. We then evaluate the m a x i m u m effect of the wormhole attack on grid network topologies. For these networks, we show that the wormhole attack can d i s r u p t / c o n t r o l about 4 0 % to 50% of all communications if the attackers strategically place the wormhole. Finally, we propose a timing-based countermeasure against the wormhole attack that is an improvement over existing schemes based on t i m i n g 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 w i t h all their neighbors one-to-one. We show that the proposed countermeasure can be used together w i t h one of the recently proposed countermeasures i n order to improve the probability of detection. T h e 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 m a x i m u m effect of the wormhole attack on a generic network. We propose a countermeasure based on timing analysis and compare it w i t h the existing timing-based solutions i n Section 4.5. A summary of this chapter is presented in Section 4.6.  4.2  Related Work  T h e existing countermeasures against the wormhole attack can be divided into proactive and reactive countermeasures. Proactive countermeasures attempt to prevent wormhole formation, typically through specialized hardware used to achieve accurate time synchronization or time measurement, or to transmit m a x i m u m power i n a particular direction. A m o n g proactive countermeasures, timing-based solutions attempt to restrict the m a x i m u m distance between two neighbors by computing the packet travel time. For example, i n [50], the authors introduced packet leashes as a countermeasure against the wormhole attack. In their method, the sender adds the transmission time to the packet in order to restrict the packet's m a x i m u m transmission distance. In [51], the authors showed how to estimate the distance 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, a l l of the aforementioned timing-based methods suffer from some of the following shortcomings. • T h e 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 w i t h a l l its neighbors; • each node requires predicting the sending time and computing signature while having to timestamp the message w i t h 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.  L o c a t i o n information can also be used i n packet leashes i n order to defend against the wormhole attack [50]. A practical proactive method based on location information is proposed i n [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 w i t h the receiver. T h e receiver can prevent the wormhole endpoint from masquerading as a false neighbor by detecting the direction of the arrived signal and comparing it w i t h 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 will 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 i n [57]) is that they cannot detect a wormhole running i n the participation mode. T h i s is due to the fact that they often attempt to prevent wormholes between two legitimate nodes; however, i n the participation mode, the wormhole is formed between two malicious nodes participating i n the routing. Note that i n this mode, a l l the links are valid except the one (the wormhole) between the two attackers. Reactive countermeasures, on the other hand, do not prevent the wormhole formation. For example, the proposed source routing protocols i n [58 and [59] consider the wormhole as a valid link and avoid it only if it exhibits some malicious behavior like modifying or dropping packets. T h i s is achieved using some basic mechanisms such as packet authentication and destination acknowledgment. Unlike proactive schemes, the existing reactive countermeasures 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 techniques such as anonymous communication have to be used to defend against passive attacks.  4.3  Wormhole Attack Analysis  T h e wormhole attack can severely affect routing protocols based on shortest delay and shortest p a t h by delivering packets faster and w i t h a smaller number of hops, respectively. T h e common belief is that the wormhole attack can prevent nodes from discovering other nodes that are more t h a n 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 t h the objective of drawing a more precise picture of the average or m a x i m u m 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 p a r t i c u 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 network 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 w i l l approach the average number of affected communications i n static networks. In this section, we first show how to approximate the length (number of hops) of the shortest p a t h between two nodes i n a homogeneous dense network. We then use this approximation to analytically evaluate the average effect of the wormhole attack for two different scenarios. In the first scenario, the m a i n objective of the malicious nodes is to d i s r u p t / c o n t r o l as many communications as possible i n the network. We show that on average every node is still able to communicate w i t h 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 d i s r u p t / c o n t r o l about one-third of a l l communications if they strategically place the wormhole. In the second scenario, two malicious nodes select and attack a target node such as the sink node i n a wireless sensor network. T h e m a i n objective of the attackers i n this scenario is to d i s r u p t / c o n t r o l the communications between the target node a n d a l l other nodes i n 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 u n i formly w i t h density S inside a disk of radius R. Suppose each node is equipped w i t h an omni-directional antenna w i t h wireless transmission range of T. We assume that there is a link between two nodes if their distance is less t h a n 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 p a t h between them. Clearly, we have Ns^o >  (4.1)  "-f.  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. T h e number of nodes i n a region TZ w i t h 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 w i t h radius  and origins at distances di = '^i +  1 ^ i ^ t, from S on the line going through S and D. T h i s is illustrated i n Figure 4.1. Using (4.2), we get P(at least one node i n each disk) = ( l - P ( n o node i n a disk))* = (l-e"*^''^?)^^)*. Clearly, the distance between two nodes i n adjacent disks is at most  T.  Therefore, there is a p a t h of length t -I-1 = [2^|;^J w i t h probability at least (1 _ e-^('^(?)'))*. Consequently, we have NS,D ^ [ 2 % ^ J ^ 2 % ^ w i t h high probability when M.(T,2,,  e-<5W4) ))f « 1  or  ,  5 »  ln(l2%^J-l)  7r(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 w i t h radius J and w i t h the origin inside the network. • Prom (4.1) and L e m m a 4.1, we observe that Ns^d is a function of can be approximated by Ns,D = P ^ ,  and (4.3)  where 1 ^ /? ^ 2.  Figure 4.1: F i n d i n g a p a t h between 5" and D.  4.3.2  Targeting all of the nodes in the Network  A s mentioned earher, i n this scenario, the mahcious nodes target a l l of the nodes i n the network i n an attempt to d i s r u p t / c o n t r o l as many communications as possible. Suppose that the wormhole attack is launched i n the hidden mode by two malicious nodes Mi and M 2 . Thus, there is a virtual link between every pair of nodes locating i n 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 p a t h 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 tween the nodes S and D if m i n {ds,Mi +  dD,M2,ds,M2  be-  + dD,Mi) ^ ds,D-  Proof. T h e path through Mi a n d M 2 (or M2 a n d M i ) looks shorter than the actual shortest path between S a n d D if a n d only if m i n {Ns,M^ +  Ndm2  ~  1- Ns,m2  + Nd,MI  - 1) < Ns,d-  Using (4.3) we get min ( / 3 ^ + / ? ^ ,  + / ? ^ )  ^  thus m i n {ds,Mi +  «^D,M2) C?5,M2  + do,Mi)  ^ <^5,£)-  W h e n the malicious nodes are on the p a t h , they can analyze the traffic or disrupt the communication by, for example, dropping the route reply or d a t a packets. • Let us assume that the malicious nodes Mi a n d M2 are located at the coordinates (—m,0) and (Tn,0), respectively. A s shown i n Figure 4.2 , the perpendicular bisector / of the line segment M1M2 partitions the network into two regions 7li a n d TZ2 containing Mi a n d M 2 , respectively.  Figure 4.2: Partitioning the network into regions TZi a n d 7^2-  L e m m a 4.3. Let S and D be two nodes both inside TZi or'JZ2- We have m i n {ds,Mi  +  + doMi)  C ? D , M 2 , ds,M2  > '^s,d-  Proof. W i t h o u t loss of generality, we can assume that b o t h S and D are i n TZy. Hence, {ds,M2  (<^Z),M2 > dD,Mi)-  > ds,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 i n the same region are able to communicate. T h e t o t a l number of possible communications between m » 1 nodes i n a region TZ can be approximated as  m  m  2  Let m i and m2 be the number of nodes i n region TZi and 7?.2, respectively. T h e attackers cannot disrupt on average more t h a n 50% of a l l of the communications 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 m i n {ds,Mi +  dD,M2^ds,M2  +  <^D,MI) ^  ds,D-  We denote the largest unreachable region for a node S as Us. F r o m 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 i n Us- T h e following theorem gives more precise information regarding the severity of a wormhole attack initiated by two malicious nodes M\ and M 2 .  T h e o r e m 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 i n Us- According to Definition 4.1, m i n {ds,Mi +  ^ D . M Z , ds,M2  + doMi)  ^ ds,D-  (4.4)  Since the node S is i n TZi, it follows from L e m m a 4.3 that the node D is not in TZi. Therefore, m i n (ds,Mx +  dD,M2^ds,M2  C^D.MJ  +  =  ds,Mi  +  C?D,M2-  (4.5)  P r o m (4.4) and (4.5) it follows that ds,Mi ^ ds,D  —  dD,M2-  T h e equation ds,Mi = ds^o - dD,M2 defines a branch of the hyperbola w i t h foci S a n d M^. Therefore, as shown i n 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. T h e area Au, can then be computed with rdrd9. m  •  Consider a polar coordinate system w i t h origin O (the origin of the network) and X - a x i s OM2. Let (r, a) be the polar coordinates of a node 5*. T h e expected value of Au^ can be calculated from  ^i^us]  =  :;^Wf  ^v,^,./drda.  (4.6)  r=0  A s 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?^). A s shown i n 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 r a n domly put inside the network. We r u n the simulation for the transmission ranges T = 0.2 and T = 0.15. In the simulation, a communication is considered affected by the attack if the shortest path through the wormhole is shorter t h a n the legitimate shortest p a t h between the source and the destination. T h e simulation is then repeated a few hundred times i n order to obtain the average percentage of affected communications across the network. A s shown i n Figure 4.4, both the simulation and the analytical results indicate that two malicious nodes can disrupt 32% of a l 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 m a k i n g wormholes between each other. In this case, a malicious node  can send packets to any other mahcious nodes using a p a t h of wormholes. Clearly, this generalized wormhole attack can disrupt more communications across the network. T h e following theorem gives an upper bound on the average percentage of affected communications. T h e o r e m 4.2.  Let M i , M 2 , . . . , M „ 6e (n ^ 2) malicious  wormholes between each other. On average, at least ^ of all  nodes making communications  across the network are not affected by the attack. Proof. A s shown i n F i g m e 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 i n its cell t h a n 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 i n 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: P a r t i t i o n i n g a network w i t h several attackers into Voronoi Cells.  4.3.3  Targeting a Particular Node in the Network  The malicious nodes may launch the wormhole attack to d i s r u p t / c o n t r o l the communication between a target node and the other nodes i n 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 communication can be a dominant flow i n such networks. Using this fact, the malicious nodes can strategically choose their locations i n order to maximize the d a m age to the sink node (the target node i n this case). L e m m a 4.4. To maximize the number of disrupted/controlled communications, 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 L e m m a 4.2, the malicious nodes can control the communication between a node A and the target node S if m i n {dA,Mi + ^2, dA,M2 + di)  ^ C^A,5-  Since ^2 > rfi, we have C J A . M J +C?2 > d^^Mi+di. we get dA,Mi + di > d^^s- Therefore, m i n (dA,Mi + c?2, C ? A , M 2 + <^i) <  Using the triangle inequality,  dA,M2  <^A,S  +  di  ^  dA,s-  Consequently, di (or equivalently the number of hops between Mi and the target node) has to be minimized i n order to maximize the number of controlled communications.  •  Now, suppose that Mi is i n the transmission range of the target node. T h e malicious nodes can control the communication between a node A and the target node S if Na,m2 < Na,s- In this case, the length of the shortest path though M 2 and Mi is Na,m2 which is smaller t h a n 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 dA,M2  <  dA,s-  (4.7)  A s shown i n 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 M 2 has to be close to the target node. However, M 2 should maintain a m i n i m u m distance dmin from the target node S. It is because for any node A inside TZm we have dA,s—dA,M2 ^ < ^ S , M 2 - Therefore, ^ ^ , 5 % ^ A . A / g when ds,M2 is small and thus Na,s = Na,M2 w i t h 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 a l l the messages at the same time if they are very close together. Clearly, the wormhole attack would not be effective i n 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. T h e area of circular sector (the region between a chord and a circle) can be computed as (4.8)  where a = a r c c o s ( - ^ ) and -R ^ h ^ of circle and the chord of the sector. circle into two sectors. E q u a t i o n (4.8) when h is negative and the area of the  Ris the distance between the center Note that each chord partitions the gives the area of the smaller sector bigger sector when it is positive.  A s shown i n Figure 4.6, the line containing S and M 2 crosses the circle (the network boundary) at points P and Q. Let the chord P'Q' be the perpendicular 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 between 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 QS~PS\  + PS\  _  /QS + PS\  {PM2-PS\  _ rPM2  fQS-PS\  +  PS d  where dmin = SM2 is the distance between S and M 2 . 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 (4.10)  h = Ô S - ^ .  • Using (4.8) and (4.10), we can estimate the ratio of the number of communications controlled by the attackers over the t o t a l number of communications as / 2a-sin(2a)\  I,  2  )^  p2  ,  ,  2a-sin(2a)  (4.11)  where a = arccos( S"^)T o obtain (4.11) we used A p p r o x i m a t i o n (4.3). W i t h o u t 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 i n respect to Q'P'. Note that the region TZc is symmetric w i t h respect to M2 and S. Therefore, the malicious nodes cannot control on average more t h a n 50% of the communications between S and the nodes inside TZc- Suppose that the malicious nodes can control a l 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 2  X  A(7^5)  AJTZm)  - AjTZs)  A(7^^,)  / 2a-sin(2Q;) \ D2 j ^ (4.12)  where A (7^) denotes the area of region 71. A s shown i n 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 r u n the simulation for the transmission ranges T = 0.2 and T = 0.15. T h e distance d^in is set to 2T a n d OS (the distance of the target node from the network center) is varied from 0 to 1 of 0.1 unit steps. A s shown i n Figure 4.7, b o t h 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. A s shown i n Figure 4.8, this can be done by p u t t i n g one of the malicious nodes ( M i i n the figure) i n the transmission range of the target node and the other malicious nodes on each side of the target node on the diagonal containing it. T h e shaded segments i n 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 i n the shaded segments, particularly the nodes that are far from the chords AB and A'B'.  Figure 4.7: Percentage of affected communications t o / f r o m 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 m a x i m u m 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^ a n d M 3 . this model, V corresponds to the location of nodes and T to their transmission range. G i v e n the location of the attackers i n the network, we can compute the number of affected communications by considering a l 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 i n order to compute the m a x i m u m effect of the wormhole attack. Suppose the effect of the wormhole attack is maximized when the attackers 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 t h attackers located at P{ a n d P2 is the same as that of the case when they are located at P i a n d P2. Clearly, it is preferable to find a n i n clusive set w i t h small cardinality i n order to reduce the size of the search domain. T h e 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 a n d P j . W e 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 i n C ; 2. P i is located on the circumference of exactly one circle i n C ; 3. P i is not located on circumference of any circle i n C. For the first case, we set P{ = Pi. Suppose that P i is located on the circumference of exactly one circle Ci e C (Case 2). Since graph G is connected. Ci w i l l intersect w i t h at least one circle. Therefore, P i can be rotated on the circumference of Cj until it lies, for the first time, on an intersection of Ci and Cj e C denoted by P{. For the t h i r d case, we can shift P i towards a vertex v eV until 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 until 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 a l 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 / . T h e 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 t h a n that of attackers at P i and P 2 since i n the latter case the attackers have m a x i m u m 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)(iV2) • U s i n g L e m m a (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 i n L e m m a (4.6) may not be practical, as i n 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 AfVcomplete [63]. Therefore, it may be preferable to compute an approximation of the m a x i m u m damage of the wormhole attack when the nodes' location information is not available. One possible solution, i n this case, is to use the  vertex set V instead of an inclusive set to get a lower bound of the m a x i m u m 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 t h a n 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, w i l l often lead to a good approximation of the m a x i m u m 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 p a t h between two nodes u and V is equal to \ux — Vx\ + \uy — Vy\, where and denote the xcoordinates of the nodes u and v and Uy and Vy denote their y-coordinates. We evaluated the m a x i m u m damage of wormhole attack using simulation on a grid topology network of m by m. Simulation results indicate that the m a x i m u m damage occurs when the malicious nodes are located on the m a i n diagonal of the grid. Figure 4.9 shows the percentage of m a x i m u m number of affected communications. A s shown i n the figure, the wormhole attack launched by two malicious nodes can affect around 40% to 50% of all of the possible communications i n a grid topology network of m x m , where 8 m ^ 32. T h e simulation results indicate that the percentage of m a x i m u m number of affected communications decreases as the total number of nodes increases.  B  0.4  10  15 20 26 Total numlier of row* (columns) In the gird  30  Figure 4.9: Percentage of m a x i m u m number of affected communications i n a grid topology network.  4.5  Wormhole Attack Countermeasure  A s mentioned i n Section 4.2, the existing wormhole countermeasures can be divided into proactive and reactive countermeasures. Proactive countermeasures 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 i n certain scenarios without using specialized hardware. For example, using the algorithm proposed i n [57], each node can detect a wormhole by analyzing its local neighbor information. However, we will show i n 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 i n either hidden or participation mode. However, they do not prevent the formation of wormhole and do not avoid the wormhole if it is used for a n invisible (passive) attack such as the traffic analysis attack. In this section, we propose a proactive countermeasure based on timing analysis. T i m i n g analysis techniques are based o n 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 T i m e {PTT) by the light speed (c). T h e existing methods to compute PTT can be divided into two classes of synchronous and asynchronous methods. T h e synchronous methods are based on accurate time synchronization. For example, i n the method proposed i n [50], each sender stamps the packet w i t h the time at which it is sent. T h e receiver can then compute PTT by comparing the time stamp w i t h 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 i n , for example, medium access control protocols based on C S M A [50 . Asynchronous methods do not require time synchronization. These methods 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. T h i s 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 i n I E E E 802.11-capable hardwares. In this method, link verification is performed i n two phases. In the first phase, the nodes exchange nonces (i.e., randomly generated numbers) v i a a single R T S - C T S - D A T A - A C K exchange. In the second phase, they m u tually authenticate themselves by signing and transmitting their respective nonces. One of the common drawbacks of the aforementioned asynchronous methods 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 w i t h 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 a l l its neighbors i n 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 a l 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 i n the received Hello messages together w i t h 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 w i t h their transmission time. Therefore, the nodes do not require to compute a signature while having to timestamp the packet w i t h its transmission time. Suppose that node A receives 5 ' s Hello message after sending its own. W h e n A receives a follow-up packet from B, it first checks its corresponding nonce i n 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 m a x i m u m transmission range. Node A considers S ' s Hello message as a response to its Hello message. T h e 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)  -  2  (JA -  JA^B)  ^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 all the information used by 5 or C to estimate dB,c is available i n 5 ' s and C ' s follow-up packets. After the second round, each node has a hst of a l 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. T h e 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 w i t h 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. T h e malicious node may do selection based on the power of received packet. In other words, they can only forward packets w i t h power higher t h a n 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 w i t h our proposed scheme. T h e o r e m 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 information.  4.6  Summary  In this chapter, we investigated the effect of the wormhole attack on shortestp a t h routing protocols. We showed that two strategically located attackers can disrupt on average 32% of a l l communications across the network, when the nodes are distributed uniformly. We also studied the effect of the wormhole 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 i n which the malicious nodes attack a target node i n the network. For this scenario, we showed that two malicious nodes can d i s r u p t / c o n t r o l on average 30% to 90% (based on the location of the target node i n the network) of a l l communications between the target node and a l l other nodes i n the network. We also evaluated the effect of the wormhole attack on grid topology networks. In these networks, we showed that wormhole attack can d i s r u p t / c o n t r o l about 40% to 50% of a l 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. M o r e 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 i n wireless ad hoc networks," In Proc. of IEEE INFOCOM, 2003. [51] S. C a p k u n , L . B u t t y a n , and J . P. Hubaux, " S E C T O R : Secure tracking of node encounters i n 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, " U s i n g directional antennas to prevent wormhole attacks," In Proc. of Network and Distributed System Security Symposium, 2004. [53] K . Sun, P. N i n g , C. Wang, A . L i u , and Y . Zhou, " T i n y S e R S y n c : Secure and resilient time synchronization i n 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 practical countermeasure to the wormhole attack i n wireless networks," In Proc. of IEEE International Conference on Network Protocols, 2006. 55] L . Lazos, R. Poovendran, C. Meadows, P. Syverson, and L . W . C h a n g , "Preventing wormhole attacks on wireless ad hoc networks: a graph theoretic approach," In Proc. of IEEE WCNC, 2005. [56] K . Rasmussen and S. C a p k u n , "Implications of radio fingerprinting on the security of sensor networks," In Proc. of IEEE SecureComm, 2007. 57] R. Maheshwari, J . G a o , 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. N i t a - R o t a r u , and H . Rubens, " A n ondemand secure routing protocol resilient to byzantine failures," In Proc. of ACM Workshop on Wireless Security (WiSe), 2002. [59] I. Avramopoulos, H . Kobayashi, R . W a n g , and A . Krishnamurthy, " H i g h l y 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 i n 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, Computational Geometry: Algorithms and Applications, 2"^* ed. New Y o r k : Springer-Verlag, 2000. [63] H . B r e u and D . K i r k p a t r i c k , " U n 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 i n order to reduce the required bandwidth/memory. One t r i v i a l way to do this is to represent a point by its x-coordinate a n d an additional b i t . T h e elliptic curve equation is a quadratic equation i n y, thus given x we can obtain at most two possible solutions of y. T h e 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. I n this case, an elliptic curve point is typically represented by b o t h its x-coordinate and y-coordinate. In the first part of the chapter, we introduce a novel double point compression scheme which allows a compact representation of elliptic curve points without the computational cost associated w i t h ordinary single point compression. W e also extend double point compression to triple point compression i n order to get more savings. Using the proposed double point and triple point compression schemes we can save about 2 5 % and 3 3 % of the bandw i d t h / m e m o r y , respectively. Moreover, the compression process of the proposed schemes requires almost no computational effort, a n d 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. T h e proposed point compression schemes can be trivially 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 w i t h three field multiplications. T h e second part of the chapter deals w i t h speeding up random point m u l tiplication. Point multiplication, kP, is a fundamental operation which dominates 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 i x e d Point M u l t i p l i c a t i o n ( F P M ) algorithms are used when a fixed base point is multiplied several times. In this case, a lookup table can be generated once and used every time a multiplication of the base point is required. R a n d o m Point M u l t i p l i c a t i o n ( R P M ) algorithms, on the other hand, are designed for the case where the base point is multiplied only once. To speed up the operation, these algorithms typically use low average H a m m i n g weight integer representations such as K ; - N A F (see [67]) and the representation proposed i n [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 P a r t i a l l y R a n d o m Point M u l t i p l i c a t i o n ( P R P M ) algorithms. We introduce the first P R P M algorithm which uses MoUer's algorithm [69] i n its evaluation stage. We speed up the precomputation stage of the algorithm using Montgomery's trick for simultaneous inversion. We then compare the performance of the proposed P R P M algorithm w i t h 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 m u l t i plication i n any devices, particularly those w i t h constrained computational power or servers overloaded w i t h 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. T h e 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 algoritlim and extend it to triple point compression. In Section 5.4, we review some of the best fixed and random point m u l t 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 substantial performance improvement i n speed can be obtained when multiple processors are available. Finally, we present a summary i n Section 5.6.  5.2  Elliptic Curves: Definition and Operations  A n elliptic curve E over the field F is a smooth curve i n 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 . E q u a t i o n (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 w i t h a "point at infinity" denoted O). It is well known that E{F) together w i t h the point addition operation given i n Table 5.1 form an abelian group. W h e n the two operands are equal, i.e. P i = P j , the operation is called point doubling. A s shown i n Table 5.2, point inversion i n this group can be computed easily. Thus, point subtraction has virtually the same cost as point addition. Note that i n Tables 5.1 and 5.2, the points P i = ( 2 ; i , y i ) , P 2 = (x2,2/2) and P 3 = (0:3,2/3) are represented by affine coordinates. Alternative coordinates such as projective coordinates or Jacobian coordinates can be used to avoid field inversion when field inversion is much more expensive t h a n 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.  Pi ^ Char{F)  ±P2  = 2  X2+X1 X3 = + X + xi + X2 + a yz = {xi + X3)X + yi + X3 xz = X'^ + X + a  Pl = P2  y3 = {Xi + X3)X + Pi ^ Char{F)  ±P2  ^2,3  yi+X3  X2-XI X3 = X"^ - Xi - X2 = {xi - X3)X - yi , 3x(+a X3 = X^ — 2xi  Pl=P2  ys = {xi - X3)X - yi Table 5.1: E l l i p t i c curve point addition, P3 = Pi + P2.  Char{F) Char(F)  = 2 ^2,3  -Pi  = (a;i,a;i - l - y i )  -Pi  = {xi,  -yi)  Table 5.2: E l h p t i c 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. T h i s is because given x, the elliptic curve equation becomes quadratic i n y. T h e 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 o d d order [70]). For example, for the case of F p , 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 m a i n 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 m o d 4, we need to compute a V m o d 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 i n Section 5.4, we are required to transmit/store multiple points. In these cases, we can use double point compression as given i n Proposition 5.1 below to reduce the required b a n d w i d t h / m e m o r y 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. T h e o r e m 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. T h e points P i = {xi,yi) and P2 = (2:2,2/2) can be represented by {xi,X2,yi + 2/2)- G i v e n 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)  T h i s is because, using (5.2), we have -  - X2) ( 3 ( x i + x^f + (rci - X2f + 4 a )  + {8A)-\xi  = - + ( 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 b o t h 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 / . W h e n 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 a n d 2/1 + 2/2 = 0. Now, suppose that Char{F) = 2 and X1+X2 0. T h e points Pi = {xi, 2/1) and P2 = ( 3 : 2 , 2 / 2 ) can be represented by {xi,X2,yi + 2/2)- G i v e n xi, X2 a n d 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  + X2)-\  and 2/2 = >1 - 2/1  (or 2/2 = ^ + 2/1 since Char{F)  = 2).  T h i s is because, using (5.3), we have ((a + X2){xi  = {xl +xl  =  ((2/1 +  + X2) + xj)  + y l ( A + X2)(xi  + ax\ + a2;^)(2;i + xz)"^ + + a x j + b) + ( 2 / 2  + ^2)"^  (2/? + 2/2  + 0:2 + « 2 : 2 +  + 2/1^^2 +  2/23^2 + &) +  2/2a;2)(2;i +  2/12^2) ( 2 ; i  +  3:2)'^ X2)~^  = {yixi + 2/ia:2)(a;i + X2)~^ = 2/1Therefore, computing b o t h 2/1 a n d 2/2 costs 3M + 3 + 1, a n d decompressing each point costs 1 . 5 M + 0.55 + 0 . 5 / . W h e n 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 a n d P2 = —PiFor 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 i n 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. T h e o r e m 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  and  + y3 = A  + yl-  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 2(2/3 + yi)(z/3 + 2/2).  B = A^+ yl-yl-yl^  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).  G i v e n 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 , {A' + yl -y\= y^ + ^  AAB y\ - "^Ay^f - 4y\yl 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. A s 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. T h e n 2/3 is ys  =  -(yi  +2/2).  Now suppose that yi = 2/| and 2/| ^ vl for different integers i, j, k G {1,2,3}. W i t h o u t loss of generality, we assume that yf =  and  2/2^  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 Finally, suppose that 2  2  2  y i = 2/2 = 2/3In this case, the points can simply be represented as ( x i , X 2 , X 3 , 2 / 1 ) . additional bits would then be sufficient to differentiate the cases 2/2  =  yi,  2/2  2/1)  2/3  =  -yi  =  -2/1-  Two  and 2/3  =  • Table 5.3 summarizes a l l possible cases w i t h the corresponding point representation and decompression cost. The conditions given i n the second colu m n can be verified using (5.2) when we have X i , X 2 and X 3 . A l g o r i t h m 5.1 provides pseudo code for triple point decompression. Note that i n 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. Finally, it is worth mentioning that triple point compression requires almost no effort as the conditions given i n Table 5.3 can easily be verified just by comparing the 2/-coordinates of the points.  A l g o r i t h m 5.1 Triple Point Decompression Input: A 4-tuple {xi,X2, X3,T) and additional bits 61,62 e {0,1} O u t p u t : 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: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20:  21:  c^B' + ATVs - ^yfyl D<- 2 ( ( T + By - T 2 - B^) = 4TB E^TD-C D-^ ^ E{DE)-^ E-^ <- D{DE)-^ 2/3 ^ CD~^ 2/2-è((yi-y?)i^^-' + ^-2/3) 2/1 <- T - 2/2 - 2/3 end if if (hi == 0) then yi^l{{y!-yl)T-'+T) 2/2 * - T - 1/1 2/3 <  (2/1 + 2/2)  end if end case {#!}: case condition #2:  2/.-è((2/.^-2/|)r-l+T)  22: 23: 24: 25: 26:  Vj^T - 2/fc 2/i ^ (26i - 1)% e n d case {#2}: case condition #3: 2/2 ^ (26i - 1)2/1  27: 28:  2/3 ^ (262 - 1)2/1 e n d case {#3}:  # 1 J.  2  Condition  Additional Bits  Point Representation  Vi ^ yf, where  h = l bi=0  ( a ; i , X 2 , a ; 3 , y i + 2/2 + 2/3)  yf = y] a n d ^ ^ where 1 ^ i,j,k  yl ^ 3  bi = l bi = 0  1 1,62 = 0 0,62 = 1 0,62 = 0  {Xi,X2,X3,yi  +2/2)  {xi,X2,xs,yj  +yk)  Decompression Cost per Point ^ / + 4 M + 2S ^I + IM + S ll + lM + S  61 = 1,62 = 3  yf = 2/1 = 2/3  61 = 61 = 61 =  {Xi,X2,X3,yi)  Table 5.3: Triple Point Compression.  M + S  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 b a n d w i d t h / m e m o r y savings. Suppose that we need to transmit/store m ^ 2 points. Clearly, any integer m ^ 2 can be uniquely written i n 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 a l l the ycoordinates. Montgomery's trick for simultaneous inversion can be employed to do this using one field inversion and 3{v + u — 1) field multiplications. T h i s can significantly speed up the decompression process as a field inversion costs more t h a n three field multiplications i n 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 i m i t e d extra information is available.  5.4.1  Fixed point multiplication ( F P M )  F i x e d 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 m u l t 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  / e„ 6 {0,1}, a = bv,b=  6-1  [—], kij = "-^  cia+jb+t'^*. t=o  The points h-1  ^UM  h-1  = 2 6^2'"^'''^foi^O^j <v, where / = ^ ^^2' t=0  i=0  are then precomputed and stored i n a lookup table, and used to compute kP as follows 6-1 kP = Y,2' t=0  \  /v-l  h-1  , w h e r e , = 2 e^a+,-6+t2\  Y,^\-hM  i=0  J  \j=Q  MoUer's algorithm represents the multiplier k i n w - N A F form (see [67]) and divides i t into n subblocks of length s = [^]. It stores the points d{2^^P) for 0 ^ j < n a n d for a l l o d d integers 1 < d < 2'^~^ i n a lookup table, and uses them t o compute kP  where h e {+1, + 3 , . . . , ±{2""-^ - 1)} u {0}.  5.4.2  Random Point Multiplication ( R P M )  R a n d o m point multiplication algorithms are designed for the case where the base point is multiplied only once. I n this case, generating a lookup table is not practical since it is computationally expensive. There are many a l gorithms t o 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 evaluation stage. A l g o r i t h m 5.2 is an example of such algorithms. T h e precomputation stage of this algorithm consists of two steps. In Step 1, the multipher k is receded t o a ^-representation A; =  2  Q^i<l  ki2\  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 A l g o r i t h m 5.2 can be considered as a sliding window algorithm. In sliding window algorithms, the recoding process may be done i n the evaluation stage. T h i s happens when the recoding and evaluating processes scan the multiplier digits i n the same direction. In this case, b o t h the recoding and evaluating processes can be carried out simultaneously. A l g o r i t h m 5.2 R a n d o m Point M u l t i p l i c a t i o n ( R P M ) Input: A n integer k and a point P e  E{F)  O u t p u t : kP P r e c o m p u t a t i o n Stage: 1: Compute the ^-representation of the multiplier k = Xlo<i<! ^^2% h B u {0} 2: Compute and store dP for a l l integers d e B, d > 1 E v a l u a t i o n 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: r e t u r n R  e  T h e integer representation of the multiplier plays an important role i n the performance of the R P M algorithm. Some useful integer representations 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 i n A l g o r i t h m 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 precomput a t i o n stage is required. In this case, the average number of point a d d i tions required i n the evaluation stage is reduced to (| - 1). T h i s is because  the average H a m m i n g weight (the number of nonzero digits i n the representation) of N A F is |. In fact, N A F has the m i n i m a l average H a m m i n g weight among a l l ^-representations w i t h B = {+!}. The N A F representation can be generalized to w - N A F . The l y - N A F representation has the m i n imal average H a m m i n g weight of i^;^) among a l l ^-representations w i t h B = {+1, + 3 , . . . , +(2'^-i - 1)} [67]. W h e n f y - N A F is used i n A l g o r i t h m 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 a l 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 m u l t i p l y a base point P only once but we can have some limited extra information regarding P. For example, i n 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 w i t h some limited extra information by including it i n its certificate. A trivial way to do this is to add a lookup table to the certificate. The entity A can use the lookup table together w i t h a fixed point multiplication algorithm i n order to compute kPB faster. T h i s 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 i n 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 i n a certificate. In addition, suppose that Moller's algorithm is used as the fixed point multiplication algorithm. We can add the points 3 P , (2^=1 P ) and 3(2f^lp) to the certificate i n 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 l p ) , ( 2 2 x m p ) and {2^''^-^^P). To use the same l y - N A F representation {w = 3 ) as i n the previous case, A must compute the points 3 P , 3 ( 2 f 5 l p ) , 3 ( 2 2 ' ^ f 3 l p ) 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 Jn-i =  {2f^l"'P,...,2f^l^Mp}  to the certificate. T h i s 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 t y p i c a l size for an X . 5 0 9 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 t h a n 5% and 2.5% when the points are represented i n an uncompressed and a compressed format, respectively.  5.5  Partially Random Point Multiplication (PRPM)  A s shown i n A l g o r i t h m 5.3, MoUer's algorithm can be used to compute r a n dom point multiphcation kP using the redundant information J „ _ i . We refer to A l g o r i t h m 5.3 as Partially R a n d o m Point M u l t i p h c a t i o n ( P R P M ) algor i t h m 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 information is available. Therefore, P R P M is expected to be faster t h a n 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 t h a n the R P M algorithm. W e 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. A l g o r i t h m 5.3 P a r t i a l l y R a n d o m Point M u l t i p l i c a t i o n ( P R P M ) Input: A n integer k, the base point P and the set r „ _ i O u t p u t : kP P r e c o m p u t a t i o n 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 a l l integers d e B, d > 1 and 0 ^ j < n E v a l u a t i o n 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 if {ksj+i > 0) then R^R + ksj+i{2'JP) else if {kgj+i < 0) then Ji^R-{-ksj+i){2^^P) 12: e n d if 13: e n d for 14: e n d for 15: r e t u r n R 8: 9; 10: 11:  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. W h e n u ; - N A F is employed, this computation can be accomphshed i n 2^'^ steps by computing the point Q = 2Pij i n the first step a n d the points P j j = Pi-i,j + Q in the i-th step  ^  for 0 ^ j < n, where Pij = 2*^P a n d 2 i ^ 2^""^. In the precomputation stage, it is preferable to represent the points Pij using affine coordinates i n order to reduce the amount of memory required t o 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 i n each step. Montgomery's trick for simultaneous inversion enables us to do this using one field inversion a n d 3(n — 1) field multiphcations [66]. Thus, for large n , one field inversion is replaced by approximately three field m u l tiplications, which is a significant cost saving as a field inversion costs more than three field multiplications i n most useful fields. Using this approach, we still need 2"^~^ field inversions. T h e number of field inversions can be further reduced t o {w — 1) i n a second approach by computing the points 2Pj i n the first step, the points ( 2 ' - i + l)Pj, (2^-1 + 3)Pj,...,  (2^ - 1)P,-, i2')Pj  i n 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 i n 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 A l g o r i t h m 5.3 would be n 2 ^ - 2 / + n2'"-^M + n ( 2 ^ - 2 + 1)5. Using Montgomery's trick for simultaneous inversion i n 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-3M).  The second approach has a computational cost of {w - 1)1 + {bn{T-^ + w-3)-Zw  + 3)M + « ( 2 ^ - ^ ^2w-  T h i s can result i n more savings for large values of I/M.  5)5.  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 algorithms. To do this, we consider the binary, N A F and w-NAF integer representations. A binary representation requires no recoding, thus it can be used in devices w i t h very limited resources. T h e N A F representation can speed up point multiplication at the cost of recoding the integer, so it may be used i n restricted devices i n order to accelerate point multiplication. Finally, w-NAF {w > 2) can result i n 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 w i t h 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 s  n  \-\-t 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. A s shown i n this figure, the higher the values of t and n , the better the performance improvement achieved by replacing the R P M algorithm w i t h the P R P M algorithm. T h e 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 A l g o r i t h m s 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 b o t h 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 coordinate 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 ( N I S T ) . 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 i n the precomputation stage, modified Jacobian coordinates (denoted by J"^), and Jacobian coordinates (denoted by J) i n the evaluation stage [76]. T h e 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 algorithms 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 parameter 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 t h a n or equal to that of the R P M algorithm. Therefore, the P R P M algorithm may result i n more speed up when more storage is available. T h e fifth column of Tables 5.5 to 5.7 indicates the percentage increase i n certificate size when the proposed point compression schemes are used. w  # stored points  Cost  5  8  4/ + 1789M  5 6 5 6  8 16 8 16  4/ 5/ 47 5/  P.384  6  16  5/ + 3492M  P_521  6 7  16 32  5/ + 4714M 67 + 4 6 9 5 M  P-192 P.224 P_256  + + + +  2084M 2066M 2378M 2351M  Table 5.4: Cost of the R P M algorithm.  w  # Stored Points  Cost  Certificate Increase  Performance Improvement  4  8  37 + 1 1 8 0 M  2.5%  50%  4 5 4 5  8 16  3/ + 1371M 4/ + 1338M  2.8%  51% 52%  8 16  3/ + 1562M 41 + 1 5 1 6 M  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%  P_192 P-224 P_256  Table 5.5: Cost of the P R P M algorithm for n = 2. # Stored Certificate Performance w Cost Increase Improvement Points P_192  3  6  27 + 1 0 3 8 M  5.0%  73 -  P_224  4  12  37+ 1128M  5.6%  81 - 83%  P_256  4  12  37 + 1 2 8 0 M  6.4%  82 -  P_384  4  12  37 + 1 8 8 8 M  9.2%  84 - 85%  P_521  5  24  47 + 2 4 2 1 M  12%  91 - 9 3 %  74%  84%  Tab: e 5.6: Cost of the P R P M algorithm for n = 3. Certificate Performance # Stored w Cost Increase Improvement Points P_192  3  8  27 + 9 3 1 M  P_224  3 4  P_256  3 4  8 16 8 16  27 + 37 + 27 + 37+  P_384  4  16  37 + 1 6 8 2 M  18.4%  P.521  4 5  16 32  37 + 2 2 4 4 M 47 + 2 1 6 3 M  24%  1081M 1024M 1230M 1155M  10% 11.2% 12.8%  93% 93% 99 - 101% 94% 101 - 103% 105 -  107%  108 - 110% 114-116%  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 m u l t i p l i c a t i o n can be computed much faster w i t h multiple processors. For example, assume that n processors are available and we have J n - i - T h e n kP can be computed as follows kp  A-l  \  n-1  V=o  /  j=o \ \i=o  /  /s-1  \  \  = /  J  n-1 j=0  where Rj = (YHZQ ksj+i2^){2^^P)- T h e j ' - t h processor can then compute using A l g o r i t h m 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). T h e n [log2n\ point additions are required to compute the final result. Therefore the t o t a l 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 t h a n A l g o r i t h m 5.2 when n « I because ((^ (it  - 1) + ( 2 - 2 - \))A + ID  - 1) + ( 2 " ' - ' - 1) + [log2 n])A + sD  A + ID i ( l A + ID)  (5.7)  n. Note that for the algorithm used i n parallel processing, the optimal w is generally smaller t h a n that of A l g o r i t h m 5.2. However, we used the same w i n (5.7) for computational convenience. In fact, using the o p t i m a l w for parallel processing results i n a value closer to n t h a n i n (5.7). Consider the general case where we have m processors (m < n) and we know J n - i - R a n d o m point multiplication can then be computed i n the following (similar) way kP =  n-\ \ V^.2^  m—1 /  V=o  j=0  m-1 j=0  /  2  ks'j+i^ \  (2^'^P)  where s' = \^] x \^] and Rj = ks'j+i2'){2''^P). Note that i n this case, each processor uses A l g o r i t h m 5.3 instead of A l g o r i t h m 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. T h e compression process of the proposed 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 i n hyperelliptic curve cryptography [78].  Bibliography 64] N . K o b l i t z , " E l l i p t i c curve cryptosystems," Math. Comp., vol. 48, pp. 203-209, 1987. [65] I. Blake, G . Seroussy, and N . Smart, Elliptic Curves in Cambridge: Cambridge University Press, 1999.  Cryptography.  66] H . Cohen, A Course in Computational Number Theory, Graduate Texts in Math. 138. Springer-Verlag, 1993, t h i r d Corrected P r i n t i n g , 1996. 67] J . A . M u i r and D . R. Stinson, " M i n i m a l i t y and other properties of the with-io nonadjacent form," Preprint, 2004, Available from http://www.cacr.math.uwaterloo.ca/tech_reports.html. 68] M . K h a b b a z i a n , T . A . Gulliver, and V . K . Bhargava, " A new m i n i m a l 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," SpringerVerlag 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 Cryptography. C R C Press, 1997.  of  Applied  72] C. H . L i m and P. J . Lee, "More flexible exponentiation w i t h precomput a t i o n , " Springer-Verlag Lecture Notes in Computer Science, vol. 839, pp. 95-107, 1994. 73] D . G o r d o n , " A survey of fast exponentiation methods," J. vol. 27, pp. 129-146, 1998.  Algorithms,  [74] I T U - T , ITU-T Recommendation X.509 version 3 (1997), Information Technology - Open Systems Interconnection - T h e Directory A u t h e n t i cation Pramewordk, I S O / I E C 9594-8, 1997. 75] R . Zuccherato, " E l l i p t i c curve cryptography support i n 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 . K h a b b a z i a n , 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 . K o b l i t z , "Hyperelliptic cryptosystems," Journal of Cryptology, vol. 1, pp. 139-150, 1989.  Chapter 6 Summary and Conclusion T h i s work consists of four major breakthroughs in the area of wireless ad hoc networks. The first two, presented i n Chapters 2 and 3, deal w i t h broadcasting, a fundamental operation i n wireless ad hoc networks. In Chapter 2, we present two efficient broadcast algorithms based on 1-hop neighbor information. The first algorithm offers great improvements over one of the best neighbor-designating broadcast algorithms based on 1-hop neighbor information [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 i m u m number of forwarding nodes i n the lowest computational 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 algorithms. In fact, we prove that our first broadcast algorithm can reduce the time complexity of computing forwarding nodes to 0{n). The second improvement of our first broadcast algorithm is on reducing the m a x i m u m 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 i n our proposed algorithm, the number of forwarding nodes i n the worst case is 11. T h i s nice feature provides the capability of bounding packets overhead. O u r second broadcast algorithm, presented in Chapter 2, was proposed w i t h the objective of significantly reducing the number of transmissions. We show that our second proposed broadcast a l gorithm is very successful i n 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) i n the worst case. T h i s directed us to our next work, presented i n Chapter 3, i n which we investigated whether localized broadcast algorithms are able to provide b o t h 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 i n 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 i n the network. One of the breakthrough results, presented i n Chapter 3, is showing for the first time this belief is unfounded by designing an efficient broadcast algorithm that satisfies b o t h aforementioned properties. In fact, we prove that an extension of our second algorithm proposed i n Chapter 2 can achieve both full delivery and a constant approximation ratio to the o p t i m u m solution. In addition, we prove that the message complexity of the extended algorithm is 0{N), where N is the total number of nodes i n the network. T h i s 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 o p t i m a l algorithm to verify the responsibility condition • Removing nodes' IDs from the broadcast messages i n order to reduce b a n d w i d t h overhead • Representing location information using only a constant number of bits • Replacing the list of neighbors of the broadcasting node (piggybacked i n the packet) w i t h a significantly smaller subset of it w i t h the objective of further reduction i n bandwidth overhead • Relaxing several system model assumptions or replacing them w i t h practical ones: -  Distributing nodded i n 3-D instead of 2-D  -  Broadcasting under uncertain position information  -  Relaxing the Homogeneous Network A s s u m p t i o n  T h e other two major breakthrough of this work, presented i n Chapters 4 and 5, deal w i t h security issues i n wireless ad hoc networks. In Chapter 4, we first analyze the effect of wormhole attack, one of the most severe attacks i n ad hoc networks. We first draw a precise picture of the effect of the wormhole attack i n shortest p a t h routing protocols. We then show, i n contrast to the  common belief, the wormhole attack launched by two malicious nodes cannot d i s r u p t / c o n t r o l 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 i n the network. We also analyze a scenario i n which several attackers make wormholes among each other and a case where two malicious nodes attack a target node i n the network. We show how to evaluate the m a x i m u m effect of the wormhole attack on a given network topology. T h e n , we compute the m a x i m u m effect of the wormhole attack on grid topology networks and show that the attackers can d i s r u p t / c o n t r o l around 40% to 50% of all communications when the wormhole is strategically placed i n 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 shortcomings: • T h e nodes require tightly synchronized clocks • E a c h node has to be capable of fast switching between the receive and send modes • E a c h node needs one-to-one communication w i t h a l l its neighbors • E a c h 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 i n ad hoc networks. We propose two point compression schemes, i n C h a p t e r 5, that can be used to reduce m e m o r y / b a n d w i d t h required to store/transmit elliptic curve points. T h e compression using our schemes can be done w i t h 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 t h a n single point compression scheme, when square root operation is computationally expensive. A l l the results presented i n this work can be used to improve the efficiency 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 localized broadcast algorithms can achieve b o t h full delivery and a good bound on the o p t i m a l solution without using location information. A l s o , it is worth analyzing the effect of the wormhole attack i n routing protocols not based on shortest path. In Chapter 5, we showed that the wormhole attack countermeasure presented i n [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 i n [80] to resolve this issue without using any specialized hardware such as accurate clocks (note that timing-based solutions require accurate clocks).  Bibliography [79] H . L i u , P. W a n , X . J i a , X . L i u , and F . Yao, "EfRcient flooding scheme based on 1-hop information i n 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 . K h a b b a z i a n , M d . Jahangir Hossain, and V . K . Bhargava, " E x a c t M e t h o d for the Error P r o b a b i l i t y Calculation of Three-Dimensional Signal Constellations," accepted for publication IEEE Transactions on Communications, 2008. • H . Mercier, M . K h a b b a z i a n a n d 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 . K h a b b a z i a n and V . K . Bhargava, "Locahzed Broadcasting w i t h Guaranteed Delivery and Bounded Transmission Redundancy," accepted for publication in IEEE Transactions on Computers, 2008. • M . K h a b b a z i a n , H . Mercier and V . K . Bhargava, "Severity Analysis and Countermeasures for the Wormhole A t t a c k i n Wireless A d H o c Networks," accepted for publication in IEEE Transactions on Wireless Communications, 2008. • M . K h a b b a z i a n and V . K . Bhargava, "Highly Efficient Broadcasting i n M o b i l e A d H o c Networks," accepted for publication in IEEE Transactions on Mobile Computing, 2007. • M . K h a b b a z i a n , T . A . Gulliver and V . K . Bhargava, "Double Point Compression w i t h Applications to Speeding up R a n d o m Point M u l tiplication," IEEE Transactions on Computers, v o l . 56, no. 3, pp. 305-313, M a r . 2007. • M . K h a b b a z i a n , T . A . Gulliver and V . K . Bhargava, " A New M i n i m a l Average Weight Representation for Left-to-Right Point M u l t i p l i c a t i o n Methods," IEEE Trans. Computers, vol. 54, N o . 11, pp. 1454-1459, Nov. 2005.  Journal papers (submitted) • K . K . Leung, C. W . Sung, M . K h a b b a z i a n and M . A . Safari, " O p t i m a l Phase C o n t r o l i n M I M O Systems w i t h Quantized Feedback," submitted to IEEE Transactions on Information Theory, M a r . 2008.  Selected conference papers • P. Kaligineedi, M . K h a b b a z i a n , and V . K . Bhargava, "Secure Cooperative Sensing Techniques for Cognitive R a d i o Systems," IEEE International Conference on Communications (ICC), M a y 2008. • M . K h a b b a z i a n and V . K . Bhargava, "Reducing Broadcast Redundancy i n Wireless A d Hoc Networks," IEEE Global Communications Conference, Nov. 2007. • M . K h a b b a z i a n , H . Mercier and V . K . Bhargava, "Wormhole A t tack i n Wireless A d Hoc Networks: A n a l y s i s and Countermeasures," in Proc. IEEE Global Communications Conference, Nov. 2006. • M . K h a b b a z i a n , K - K . Leung and M . A . Safari, " O n the O p t i m a l Phase C o n t r o l i n M I M O Systems w i t h Phase Q u a n t i z a t i o n , " in Proc. IEEE International Communications Conference, vol. 9, pp. 42724277, J u n . 2006. • M . M . Rashid, E . Hossain, M . K h a b b a z i a n , and V . K . Bhargava, " O n Access-Based Self-Organized Clustering i n A d Hoc M o b i l e W i r e less Networks," in Proc. IEEE Conference on Communication System Software and Middleware (COMSWARE), J a n . 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}]}"
                            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:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0066825/manifest

Comment

Related Items