A QUALITY OF SERVICEAWARE ROUTING BASED ON ADAPTIVE
GOSSIPING ALGORITHM FOR AD HOC WIRELESS NETWORKS
by
Ahyoung Lee
B.E., Hansung University, 2001
M.S., University of Colorado Denver, 2006
A thesis submitted to the
University of Colorado Denver
in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Computer Science and Information Systems
2011
2011 by Ahyoung Lee
All rights reserved.
This thesis for the Doctor of Philosophy
degree by
Ah Young Lee
has been approved
by
Ilkyeun Ra (Advisor)
AnatoliLA, pahalskii (CoAdvisor)
Tom Altman
Michael Mannino
//30X0//
Date
Lee, Ahyoung (Ph.D., Computer Science and Engineering).
A Quality of ServiceAware Routing Based on AdaptiveGossiping Algorithm for
Ad Hoc Wireless Networks.
Thesis directed by Associate Professor Ilkyeun Ra
ABSTRACT
The qualityofservice (QoS) is a set of requirements to ensure the timely delivery
of data infonnation through the network from one source to a destination, which
raises new challenges for the development of ad hoc wireless networks (AWNs).
One of the main goals of QoSaware routing in AWNs is to be able to provide end
toend delay guarantee and the requested bandwidth to delaysensitive applications.
A solution to reach this goal is to improve the performance of ad hoc routing
protocols that incorporate QoS metrics. This work involves a design of QoSaware
routing protocol to provide a delay guarantee, but also to minimize routing
overhead and save energy consumption. To achieve the goals, we studied different
routing strategies and evaluated them by using mathematical analysis and
simulation. The main work included the following tasks:
1. Develop an adaptivegossiping routing algorithm based on a probabilistic
broadcast mechanism that can reduce the redundant routing packets, thereby
minimizing the overall energy consumption in AWNs.
2. Develop a new analytical model for estimating average endtoend delay in a
multihop wireless ad hoc network.
3. Implement a QoSaware routing protocol based on our adaptivegossiping
algorithm.
4. Carry out a comparison algorithm of existing algorithms and our proposed
approach.
Both analytical and simulation results indicated that our proposed QoSaware
routing protocol based on adaptivegossiping routing algorithm can perfonn
efficiently for conserving network resources and supporting QoS in AWNs.
This abstract accurately represents the content of the candidates thesis,
recommend its publication.
Signed
Ilkwmn Ra
DEDICATION
I dedicate this thesis to my mother, who gave me an appreciation of learning and
taught me the value of perseverance and resolve. I also dedicate this to my brothers
for their support and understanding while I was completing this thesis.
ACKNOWLEDGEMENT
First of all, 1 would like to express my profound gratitude to my advisor, Dr.
Ilkyeun Ra, who has continually encouraged me to achieve great things and
supported me at every step of my study. From the bottom of my heart, thank you
for everything you have done for me!
My genuine appreciation goes to my great coadvisor, Dr. Anatolii A. Puhalskii,
who has patiently taught me probability theory needed to develop an analytical
model of an ad hoc wireless network. Parts of this work would not have been
possible without him.
1 am truly thankful to Dr. Tom Altman for his sincere support as a thesis committee
member, who also has encouraged me and for the Mieczyslaw Altman scholarship
that has helped me take a step closer to achieving the Ph.D.
I would like to thank Dr. Boris Stilman for being my committee member and also
allowed me to take his course, Artificial Intelligence, which has given me a lot of
insight into how to solve largescale network problems.
I would also like to thank Dr. Michael Mannino for being my committee member,
with special thanks for his many valuable comments when I took his course,
Analytic Research in Information Systems, which greatly improved my technical
writing skills.
My special sincere thanks have to go to Dr. Alaghband Gita, who is a Chair of the
Department of Computer Science and Engineering, for offering me a teaching job
and for her encouragement.
Additionally, my sincere thanks go to Frances Moore, who is a program assistant in
the Department of Computer Science at UCD, for her firm friendship and caring
about me like a family member.
Finally, this thesis is dedicated to my mother, Choi, HeeJa. It is her love,
encouragement, belief and understanding that made everything I have possible.
Once again, I would like to thank everyone mentioned for your professional advice
and feedback, friendship, and family love that enabled me to successfully
accomplish both my academic and research goals.
TABLE OF CONTENTS
Figures.....................................................................x
Tables ....................................................................xv
Chapter
1. Introduction...........................................................1
1.1 Description of Research Challenges...................................1
1.1.1 Issues of Ad Hoc Wireless Networks.................................1
1.1.2 Challenges of QoSAware Routing in Ad Hoc Wireless Networks........3
1.2 Research Goal and Contributions.......................................5
1.2.1 Goal...............................................................5
1.2.2 Contribution.......................................................5
1.3 Outline of The Dissertation...........................................6
2. Preliminary Studies....................................................7
2.1 Overview of Preliminary Studies.......................................7
2.2 Ad Hoc Routing Protocols with GossipingBased Approach [33]..........7
2.2.1 Introduction.......................................................7
2.2.2 Overview of Routing Protocols......................................9
2.2.3 Dynamic Source Routing (DSR).......................................9
2.2.3.1 Ad Hoc OnDemand Distance Vector Routing (AODV)...................10
2.2.3.2 GossipingBased Ad Hoc Routing (AODV+G)...........................11
2.2.3.3 Comparison of Routing Protocols...................................11
2.2.4 Simulation and Performance Metrics................................14
2.2.4.1 Traffic Models....................................................14
2.2.4.2 Mobility Models...................................................14
2.2.4.3 Performance Metrics...............................................16
2.2.5 Simulation Results................................................17
2.2.6 Summary...........................................................24
2.3 AdaptiveGossiping for EnergyAware Routing in WSNs [77]...........25
2.3.1 Introduction......................................................25
2.3.2 EnergyAware Routing Protocol and Energy Analysis.................26
2.3.2.1 EnergyAware Routing Protocol Based on AdaptiveGossiping.........26
2.3.2.2 Energy Analysis...................................................29
2.3.3 Simulation and Performance Metrics................................31
vii
to to to to to
2.3.3.1 Simulation Setup..................................................31
.3.3.2 Performance Metrics...............................................33
.3.4 Evaluations.......................................................34
.3.4.1 Node Traversal Time (NTT).........................................34
.3.4.2 Communication Network Traffics....................................37
.3.5 Summary...........................................................40
3. Analysis of Ad Hoc Wireless Networks [107, 108].....................41
3.1 Introduction.....................................................41
3.2 General Network Model of Ah Hoc Wireless Networks..................43
3.2.1 Network Topology..................................................43
3.2.2 Assumptions.......................................................43
3.2.3 Basic Theoretical Concepts.......................................46
3.2.3.1 Graph Theory......................................................46
3.2.3.2 Node Degree.......................................................46
3.2.3.3 Connectivity......................................................47
3.3 Analysis of Communication Area for AdaptiveGossiping.............51
3.3.1 Neighbor Nodes of A Node..........................................51
3.3.2 Transmission Range with High Connectivity.........................57
3.4 Analysis of Hop Count...............................................60
3.4.1 Hop Count for Flooding............................................60
3.4.2 Hop Count for AdaptiveGossiping..................................65
3.4.3 Hop Count Between Random Source and Destination...................72
3.4.3.1 Distance Between Random Two Points in OneDimensional Case........72
3.4.3.2 Distance Between Random Two Points in TwoDimensional Case.......73
3.5 Analysis of Delay...................................................77
3.6 Performance Evaluation..............................................82
3.6.1 Analytical Results of Energy Consumption..........................82
3.6.2 Simulation Results................................................83
3.7 Summary.............................................................87
4. Queuing Analysis of Ad Hoc Wireless Networks [110]..................88
4.1 Introduction.........................................................88
4.2 Queuing System Model................................................89
4.2.1 The Network Model.................................................89
4.2.1.1 FloodingBased Ad Hoc Routing.....................................89
4.2.1.2 AdaptiveGossiping Based Ad Hoc Routing...........................90
4.2.2 The Traffic Model.................................................91
viii
4.2.3 The Queuing Network Mode...................................
4.3 Queuing Analysis of EndtoEnd Delay.........................
4.3.1 Packet Service Rate........................................
4.3.2 Packet Arrival Rate........................................
4.3.3 Packet Drop Probability....................................
4.4 Performance Evaluation........................................
4.4.1 Analytical Results.........................................
4.4.2 Simulation Results.........................................
4.5 Summary.......................................................
5. QoSAware Routing in Ad Hoc Wireless Networks..................
5.1 Introduction..................................................
5.2 Design Considerations of QoSAware Routing in AWNs............
5.2.1 Constraints of Providing QoS...............................
5.2.2 Constraints of Network Resources in Providing QoS..........
5.2.3 QoS Requirements Based on Constraints......................
5.2.4 QoS Metrics Based on Constraints...........................
5.3 QoSAware Routing Based on AdaptiveGossiping Algorithm........
5.3.1 QoSAdaptiveGossiping Routing Scheme and Network Architecture..
5.3.2 Implementation of QoSAdaptiveGossiping Routing...........
5.3.2.1 Estimation of Available Bandwidth..........................
5.3.2.2 Estimation of Delay........................................
5.3.3 Mechanisms of QoSAG Routing with AODV.......................
5.3.3.1 Route Discovery............................................
5.3.3.2 Route Maintenance..........................................
5.4 Performance Evaluation........................................
5.4.1 Simulation Results.........................................
5.5 Summary.......................................................
6. Conclusions and Future Work....................................
APPENDIX A.........................................................
APPENDIX B.........................................................
APPENDIX C.........................................................
APPENDIX D.........................................................
APPENDIX E.........................................................
APPENDIX F.........................................................
APPENDIX G.........................................................
REFEERNCES.........................................................
.91
.93
.93
.96
.99
101
101
106
111
112
112
113
114
115
116
117
121
121
125
125
130
135
135
135
139
139
145
146
149
150
151
153
155
156
157
158
IX
to
LIST OF FIGURES
Figure
1.1 Example of wireless radio links in AWNs where the numbers next to
THE RADIO LINKS REPRESENT THEIR RESPECTIVE BANDWIDTH IN MEGABITS PER
SECOND.......................................................4
2.2 Packet delivery fractions for 50 nodes and 150 nodes at a variety
OF PAUSE TIMES..............................................20
2.3 Average endtoend data packet delays for 50 nodes and 150 nodes
AT A VARIETY OF PAUSE TIMES.................................20
2.4 Routing overheads for 50 nodes and 150 nodes at a variety of pause
TIMES.......................................................21
2.5 Normalized routing loads for 50 nodes and 150 nodes at a variety
OF PAUSE TIMES..............................................21
2.6 Throughputs for 50 nodes and 150 nodes at a variety of pause times.
..................................................................22
2.7 Average used node energies for 50 nodes and 150 nodes at a variety
OF PAUSE TIMES..................................................22
2.8 Routing overheads and average used node energies for 150 nodes
WITH A HIGHER TRAFFIC RATE OF 4 PACKETS/SEC......................23
.9 AdaptiveGossip algorithm GOSSIP..,,,,ri{p/N,K,m).................28
. 10 Packet sent rate 1 per second by increasing NTT values............35
2.11 Packet sent rate 1 per second by increasing NTT values............36
2.12 Peertopeer application traffic by increasing packet sent rates in a
STATIC BASE STATION WSN..........................................38
2.13 MULTITOONE APPLICATION TRAFFIC BY INCREASING SPEEDS OF MOBILE
NODES (ALL SENSORS AND A SINK) IN A MOBILE BASE STATION WSN.....39
3.14 Scope of this studys work in the field of ad hoc wireless network
research: The inner zone presents topics in the main focus area of
fundamental properties of ad hoc wireless networks for a realistic
MATHEMATICAL MODEL. THE MIDDLE ZONE INCLUDES IMPORTANT TOPICS
USED TO DEVELOP A QoSAWARE ROUTING PROTOCOL AND MAKE
ASSUMPTIONS FOR EVALUATING PERFORMANCES. THE OUTER ZONE PRESENTS
X
BROAD TOPICS NOT INCLUDED IN THIS STUDY BUT ARE CONSIDERATIONS
RELATED TO ENERGY EFFICIENCY...........................42
3.15 The model of network topology is an undirected random geometric
graph. Nodes are randomly distributed in a network of size A = axb
AND EACH NODE HAS THE SAME RADIO TRANSMISSION RANGE r0......44
3.16 ILLUSTRATION OF AN ISOLATED NODE.............................47
3.17 Connectivity: The graph G has nodeconnectivity 1, edge
connectivity 2 AND THE MINIMUM NODE DEGREE 3 RESPECTIVELY K(G) = 1,
K,;,X;e(G) = 2 AND DW,V
REMOVING EITHER A SINGLE NODE SUCH AS C AND REMOVING TWO EDGES
SUCH AS AC AND BC...........................................50
3.18 AdaptiveGossip algorithm GOSSIP^.^Cv, a:, m), where pn is different
FROM FWr IN FIGURE 2.9......................................55
3.19 Comparison of broadcasting mechanisms: (a) flooding method
TRANSMITS ROUTINGRELATED PACKETS TO ALL NEIGHBORS OF A NODE
WITHIN ITS TRANSMISSION AREA OF a2n[r, (N)f BUT (B) ADAPTIVE
GOSSIPING METHOD WITH pn = (1 / /?) log(N) SENDS ROUTINGRELATED
PACKETS TO ONLY SELECTED NEIGHBORS OF A NODE WITHIN ITS /r(rg(A0)
IN THE NETWORK AREA OF SIZE A = (1000x500)m2 WITH N = 100 NODES FOR
rg(N) = a[rf (A)) BY (3.22)......................................56
3.20 Comparison of the critical transmission range for flooding
ALGORITHM AND ADAPTIVEGOSSIPING ALGORITHM.......................58
3.21 The critical transmission range (CTR): The analysis results are
COMPARED WITH rf(N) AND rg(N) FOR FLOODING FROM (3.24) AND
ADAPTIVEGOSSIPING FROM (3.25) RESPECTIVELY, BY INCREASING NODES N
BETWEEN 60 AND 2000 IN A SIMULATION AREA OF SIZE A = (1000 X 500) m2 .
.......................................................59
3.22 Perhop progress: the next hop is the farthest node {Â£ = .y) in an
AREA OF ( 7r/2,7r/2) TOWARD THE DESTINATION NODE, WHERE (0 IS
UNIFORM ON [0,zr/2]......................................61
3.23 The expected perhop progress of flooding routing algorithm in the
CRITICAL TRANSMISSION RANGE (CTR).
XI
E(() = Ft (0,rf(N),A) = F, [n,r, (jV),2 104) FROM (3.30), WHERE rf(N) IS
DEFINED FROM (3.24) WITH THE TOTAL NUMBER OF NODES N BETWEEN 60 AND
2000 IN A SIMULATION AREA OF SIZE A = 1000 X 500 m2.............64
3.24 The expected perhop progress of adaptivegossiping routing
ALGORITHM IN THE CRITICAL TRANSMISSION RANGE (CTR).
E(() = F,(6,rg(N),A) = F((x,rg{N),2\0~4) FROM (3.43), WHERE rg(N) IS
DEFINED FROM (3.25) WITH THE TOTAL NUMBER OF NODES TV BETWEEN 60 AND
2000 IN A SIMULATION AREA OF SIZE A = (1000X 500) m2............70
3.25 Comparison of the expected perhop progress with flooding and
ADAPTIVEGOSSIPING ROUTING ALGORITHM WITHIN THEIR CRITICAL
TRANSMISSION RANGE (CTR). Ft (;r, rf (N),210"4) FOR FLOODING AND
Ff (x,rg (TV), 2 1 O'4 ) FOR ADAPTIVEGOSSIPING FROM (3.30) AND (3.43)
RESPECTIVELY, WHERE rf (N) AND r (N) ARE THE CRITICAL TRANSMISSION
RANGE FOR FLOODING AND ADAPTIVEGOSSIPING DEFINED FROM (3.24) AND
(3.25) RESPECTIVELY. THE TOTAL NUMBER OF NODES NBETWEEN 60 AND
2000 ARE RANDOMLY DISTRIBUTED IN A SIMULATION AREA OF SIZE
A = (1000x500)m2................................................71
3.26 The expected number of hops between a random source and
DESTINATION PAIR. THE ANALYSIS RESULTS ARE COMPARED WITH FLOODING
AND ADAPTIVEGOSSIPING IN A GIVEN NETWORK SIZE OF (1 000x500)AC
ACCORDING TO EQUATION (3.56)....................................76
3.27 Link available time. It impacts the average endtoend delay
BETWEEN RANDOM SOURCE AND DESTINATION. WHERE E(() IS THE DISTANCE
BETWEEN TWO NEIGHBOR NODES AND n,, AND ( IS THE DISTANCE NODE M,
TRAVELED TO MOVE AT A RELATIVE VELOCITY V,. OUT OF ITS NEIGHBOR S
TRANSMISSION RANGE rf (N).......................................79
3.28 The expected link available time: The analysis results are
compared with E{T) = F, (vimx,/y(N),E(Â£)) and
E(T) = F,(vm,rt(N),Eie)) FOR FLOODING AND ADAPTIVEGOSSIPING
RESPECTIVELY, WHERE EACH NODE HAS THE SAME VELOCITY OF Vmax = 20A//5
Xll
WITH THE TOTAL NUMBER OF NODES N BETWEEN 60 AND 2000 IN A
SIMULATION AREA OF SIZE A = (1000x500)/772 ACCORDING TO EQUATION
(3.67)........................................................81
3.29 IN (A) SHOWS A COMPARISON OF THE ENERGY CONSUMPTION OF THREE
BROADCAST MECHANISMS: FLOODING AS PROBABILITY=l; STATICGOSSIPING
WITH PROBABILITY P=0.65; AND ADAPTIVEGOSSIPING WITH PROBABILITY
/V=(l//V)LOG(A0. In (b) shows the results for ONLY ADAPTIVEGOSSIPING
FROM (A). The TOTAL NUMBER OF NODES ./V BETWEEN 50 AND 2000 IN A
SIMULATION AREA OF SIZE A=( 1000x500)Ar........................83
3.30 The simulation results of ad hoc routing protocols based on three
DIFFERENT BROADCAST MECHANISMS: FLOODING AS PROBABILITY=l, STATIC
GOSSIPING WITH PROBABILITY P= 0.65 AND ADAPTIVEGOSSIPING WITH
PROBABILITY Py={ Vn)LOG(N).....................................84
3.31 The simulation results of ad hoc routing protocols based on THREE
DIFFERENT BROADCAST MECHANISMS: FLOODING AS PROBABILITY=l, STATIC
GOSSIPING WITH PROBABILITY P=0.65 AND ADAPTIVEGOSSIPING WITH
PROBABILITY /V=( 1 /V)LOG(TV)..................................85
4.32 The expected endtoend delay: E(D) is between a random source
AND DESTINATION PAIR. THE ANALYSIS RESULTS ARE COMPARED WITH
FLOODING AND ADAPTIVEGOSSIPING FOR 32 AND 512 BYTES FOR VOICE AND
VIDEO DATA RESPECTIVELY. WHERE (X) IS THE TOTAL NUMBER OF NODES N
FROM 100 TO 1000 AND (Y) IS THE PACKET GENERATION RATE PER SECOND
FROM 1 TO 100 IN A GIVEN NETWORK SIZE OF (1 000x500)AT ..... 104
4.33 The delay ratio is an analysis of endtoend delay which is less
THAN LINKAVAILABLE TIME.................................... 105
4.34 The simulation results of multimedia communications with packet
SIZES OF 32 AND 512 BYTES FOR VOICE AND VIDEO DATA, RESPECTIVELY. THE
COMPARISON OF FLOODING AND ADAPTIVEGOSSIPING IS BETWEEN 100 AND
1000 NODES WITH 1 PACKET SENT PER SECOND IN A GIVEN NETWORK SIZE OF
(1000x500)Ar...............................................108
4.35 The simulation results of multimedia communications with packet
SIZES OF 32 AND 5 12 BYTES FOR VOICE AND VIDEO DATA, RESPECTIVELY. THE
COMPARISON OF FLOODING AND ADAPTIVEGOSSIPING IS BETWEEN 100 AND
1000 NODES WITH 1 PACKET SENT PER SECOND IN A GIVEN NETWORK SIZE OF
(1000x500)Ar...............................................109
Xlll
4.36 Comparison of the analysis and simulation results for average end
toend delay (s). The comparison of flooding and adaptivegossiping
IS BETWEEN 100 AND 1000 NODES WITH PACKET SIZE OF 512 BYTES FOR 1
PACKET SENT PER SECOND IN A GIVEN NETWORK SIZE OF (1000x500)Ar 110
5.37 Network architecture based on QoSAdaptiveGossiping routing.
..........................................................124
5.38 Illustration of the 802.11 RTS/CTS/DATA/ACK access mechanism.
........................................................126
5.39 The flow chart of execution of QoSAG routing protocol...137
5.40 Sequence diagram of QoSAG routing protocol..............138
5.41 QoS REQUIREMENT OF AVERAGE ENDTOEND DELAY D WITH 100 NODES
BETWEEN 5A/SAND 160A/S.................................. 141
5.42 QOS REQUIREMENT OF AVERAGE ENDTOEND DELAY D WITH 100 NODES
BETWEEN SMS AND 160A/S................................. 142
5.43 QoS REQUIREMENT OF AVERAGE ENDTOEND DELAY D WITH 300 NODES
BETWEEN 5MS AND 160 MS.................................. 143
5.44 QoS REQUIREMENT OF AVERAGE ENDTOEND DELAY D WITH 300 NODES
BETWEEN 5A/5AND 160 ATS................................. 144
XIV
LIST OF TABLES
Table
2.1 Comparison of Routing Protocols..............................13
2.2 Simulation Parameters........................................15
2.3 Simulation Parameters........................................32
3.4 Notations....................................................45
4.5 Physical Layer Parameters: Protocol and channel parameters are
SPECIFIED BY THE IEEE 802.1 1 DCF STANDARD WITH DIRECTSEQUENCE
Spread Spectrum (DSSS) [52]................................103
5.6 Applications for AWNs and their QoS requirements...........117
XV
1. Introduction
In the modem Internet, the tremendous worldwide growth of users of
wireless network access, mobile services, and applications has resulted in
approximately 1 billion users by September 30, 2009 [1,2]. A network or a service
provider may be willing to offer different kinds of customized services to personal
users. In a network, data packets may follow different paths from a source to
destination(s). Network resources, such as link bandwidth and buffer space, are
shared by packets from multiple flows of traffic. However, this network
architecture does not support service requirements when users request different
kinds of services. A service can be defined [9] by a set of measureable sendee
requirements such as minimum bandwidth, maximum delay, and maximum packet
loss rate. To accept a service request from a user, the network has to guarantee that
service requirements of the flow are met by the user. Thereby, quality of service
(QoS) support is critical in the network to ensure a set of service guarantees for the
duration of the flow (a packet stream from source to destination).
To provide a service request, the network routing protocol has to find a suitable
path with sufficient available resources to meet the QoS requirements of the desired
service. A set of QoS requirements is directly affected by the network performance
of the underlying routing system. Hence, one of the main issues is ensuring QoS
routing that allows selecting network routes with sufficient available resources for
requested QoS parameters. Moreover, it is unclear which satisfying QoS
parameters will be incorporated effectively into new types of wireless networks
such as mobile ad hoc networks (MANETs) or wireless sensor networks (WSNs)
that are based on ad hoc networks.
1.1 Description of Research Challenges
1.1.1 Issues of Ad Hoc Wireless Networks
Unlike conventional wireless networks that are often connected to a wired
network (ATM or Internet), an Ad Hoc Wireless Network (AWN) is a self
configuring network of mobile nodes connected by wireless links to form an
l
arbitrary topology without the use of any existing infrastructure or centralized
administration. In such an environment, each node performs as a router and a host
and forwards packets to other nodes by discovering multiple hop paths. This type
of network can be used in battlefield communications, vehicle networks,
inaccessible environments such as disaster recovery, monitoring ocean depth or fire
detection, and group communication in a conference hall, etc. However, AWNs
have several constraints.
1) Ad hoc network status is unpredictable in the dynamically changing network
topology of AWN because nodes are mobile independently, causing imprecise
knowledge of the current network state. Consequently, sessions are connected
and disconnected in an unpredictable way due to frequent link breaks, thereby
requiring reestablishment of routes over new paths, which causes a significant
increase in routing overhead. Hence, the delivery of data packets guaranteed by
the endtoend performance of QoS support for the whole duration of a session
from source to destination is not practical in AWNs.
2) Network state information is imprecise due to dynamic changes in network
topology and impairments in a shared radio channel. Each node in an ad hoc
network should maintain both the linkspecific state information and the flow
specific state information. The linkspecific state information includes
bandwidth, delay, delay jitter, loss rate, error rate, stability, and distance values
for each link. The flowspecific state information from source to destination
includes session ID, source address, destination address, and QoS requirements
of the flow (such as minimum bandwidth requirement, maximum delay, and
maximum delay jitter). Hence, network state information is hard to obtain and
estimate accurately to meet QoS support.
3) Resource availability is limited in AWNs. Resources, such as bandwidth,
battery life, buffer space, and processing capability, are very important when a
route is discovered. The most significant fact is that the mobility of nodes
imposes the limitation of battery life on their power capacity. Thus, if resources
are not sufficiently available, the capability of the providing QoS mechanism
can be seriously degraded.
4) Other issues include physical characteristics such as channel contention due to
the broadcast nature of wireless medium without a central controller. Some
setup, new neighbor discovery and control operations have to take place on a
common contended channel; hence, high packet collisions occur due to packets
sent simultaneously by independently distributed nodes even when using the
RTS/CTS control packet exchange mechanism. Therefore, routing overhead
and energy consumption increase significantly, which affect the endtoend
delay of QoS support.
There are some other issues related to wireless channel problems such as hidden
terminal problems and insecure wireless channels. However, this dissertation does
not focus on these issues.
1.1.2 Challenges of QoSAware Routing in Ad Hoc Wireless Networks
The concept of QoS is a guarantee by the network to provide a set of
measurable service requirements to the user in terms of endtoend delay, available
bandwidth, and probability of packet loss [3,5,11,12], According to AWNs
constraints, the network operates in a connectionless and stateless mode. The
network of routers is not aware of any associations of flow between source and
destination. Each packet is routed individually without any infonnation about the
state of flow from source to destination. To provide a service request from the user
in the network, QoS routing is the most important element in QoS support. The
essential task is to find a suitable path among the different routes with sufficient
available resources that are used by the flow of packets from the source to
destination. The network must guarantee the availability of a set of resources (e.g.,
link bandwidth, buffer space, processing power) while transporting the flow of
packets. For example, suppose that the packet flow from A to E requires a
bandwidth guarantee of 4 Mbps. QoSaware routing will then select path
A>B*CE instead of path A>D>E although the latter has fewer hops, because
the path A>BC>E meets the bandwidth constraint of 4 Mbps (see Figure 1.1).
Therefore, this work focuses on the following research questions based on the
above constraints of AWNs that must be solved to improve the performance of
QoSaware routing protocols in AWNs.
1) What is the best way to estimate endtoend delay and/or available bandwidth
to achieve highaccuracy of QoS measurements and lowoverhead of routing
communications?
2) Which class of routing protocols would work better for providing QoS routing
to balance routing overhead and endtoend delay?
3
Figure 1.1 Example of wireless radio links in AWNs where the numbers next to
the radio links represent their respective bandwidth in megabits per second.
3) Which broadcasting mechanisms would work better for providing QoS routing
to balance routing overhead and endtoend delay?
4) How can the tradeoff between the reduced routing overhead and the minimized
delay associated with providing QoS routing best be addressed?
5) How can energy efficiency be achieved to prolong the network lifetime to meet
QoS requirements?
4
1.2 Research Goal and Contributions
1.2.1 Goal
The main research goal of this work is to develop an adaptive QoSaware
routing protocol based on the proposed adaptivegossiping algorithm in order to
provide delay guarantee while minimizing routing overhead and saving energy
consumption in a given AWN while addressing the previously stated questions. In
particular, the work includes the following:
1) Develop an adaptivegossiping algorithm based on a probabilistic broadcast
mechanism [79] that will reduce the redundant routing packets in order to
minimize the overall energy consumption in AWNs.
2) Present a new analytical model for estimating average endtoend delay that is
the accumulation of single hop delays. The delay is defined as the time to send
a packet from a source to a destination in multihop wireless communications.
It includes queuing delay, transmission delay and propagation delay.
3) Design a network architecture based on QoSaware routing, which is combined
with the proposed adaptivegossiping algorithm.
4) Implement a QoSaware routing for the delay guarantee and the available
bandwidth parameter values as set up by QoS application users. This QoS
aware routing will be applied to some existing ad hoc routing protocols and our
proposed routing algorithm.
5) Present results on performance evaluation of the proposed adaptivegossiping
algorithm, and compare with flooding algorithm and staticgossiping algorithm
based on numerical analysis and simulation tests.
1.2.2 Contribution
There are various problems in QoS routing. Many of them have been
studied only providing endtoend guarantee QoS without considering routing
overheads that may seriously affect energy efficiency in AWNs. Thus, this
dissertation provides specific contributions in the following areas:
5
1) Identify metrics that are used to specify QoS requirements in AWNs. The QoS
metrics, such as node degree, connectivity, capacity, hop count and queuing
delay, will be concrete foundations for the analysis of an AWN.
2) Provide an analysis of QoSaware routing protocols. We discover main
attributes that will significantly impact endtoend delay and overall network
resource consumption.
3) Provide a QoS architecture that is extended QoSaware routing in ad hoc
routing protocols based on the requirements of available bandwidth and delay
guarantee and which is designed at the network layer through the MAC layer.
4) Provide performance evaluations of QoSaware routing protocols in AWNs
including a comparison of floodingbased routing and adaptivegossiping based
routing, QoSAODV routing protocols and QoSAG routing protocols,
respectively.
5) Discuss both the analytical results and empirical results.
Ultimately, the goal is to determine which routing protocol is best for supporting
QoS to reduce overhead, minimize delay, and conserve energy.
1.3 Outline of The Dissertation
This dissertation begins in Chapter 2 with a presentation of preliminary
studies that are crucial to accomplishing the goals. Chapter 3 describes an analysis
of AWNs and Chapter 4 addresses the queuing network model for delay analysis of
AWNs that are the foundation for identifying QoS metrics. Chapter 5 presents the
implementation of QoSaware routing protocol based on adaptivegossiping
algorithm including design considerations and mechanisms of QoSadatpvie
gossiping routing, and finally, in Chapter 6, conclusions are drawn from the
research work and a discussion of future work for developing a QoSaware routing
protocol in AWNs.
6
2. Preliminary Studies
2.1 Overview of Preliminary Studies
Preliminary studies primarily addressed two aspects of the issues: how to
provide QoS routing to balance routing overhead and endtoend delay, and how to
deal with a tradeoff between reducing routing overhead and minimizing delay
associated with providing QoS routing while achieving an energyefficient QoS.
The first preliminary study, an ad hoc routing protocol with a gossipingbased
approach, assessed the performance of a gossipingbased and floodingbased
routing protocol in order to identify the strengths and weaknesses of each protocol
and suggest appropriate AWN environments for each routing protocol. This was
the primary study designed to solve the questions regarding the constraints of
AWNs, basically answering research questions #2 (Which class of routing
protocols would work better for providing QoS routing to balance routing overhead
and endtoend delay?) and #3 (Which broadcasting mechanisms would work better
for providing QoS routing to balance routing overhead and endtoend delay?). The
second preliminary study developed an energyaware routing protocol implemented
by an adaptivegossiping algorithm that reduces redundant routing messages so that
it can minimize the overall energy consumption of an AWN, which provides the
basic answers for research questions #4 (How can the tradeoff between the
reduced routing overhead and the minimized delay associated with providing QoS
routing best be addressed?) and #5 (How can energy efficiency be achieved to
prolong the network lifetime to meet QoS requirements?).
2.2 Ad Hoc Routing Protocols with GossipingBased Approach 33
2.2.1 Introduction
A Mobile Ad hoc Network (MANET) is a selfconfiguring network of
mobile nodes connected by wireless links to form an arbitrary topology without the
use of any existing infrastructure or centralized administration. In such an
environment, each node acts as a router and a host, and forwards packets to other
nodes by discovering multiple hop paths. Many ad hoc routing protocols have been
7
designed to efficiently establish routes and deliver packets between mobile nodes
with minimum communication overhead while ensuring high throughput and low
endtoend delay in MANETs. Early researchers have pointed out the critical
performance issues, such as increasing node density and traffic in MANETs, which
include an appropriate selection of routing protocols [12,13]. It is a challenging
task to determine which protocols may perfonn best under a number of different
network scenarios, network size, and node mobility. Due to these problems, a
number of routing protocols have been proposed for MANETs using a flooding
strategy at each node to share its link information by periodically broadcasting
routing packets to all other nodes in the network topology. However, the problem
with flooding is that many routing messages are propagated unnecessarily. The
worst case of the computational complexity of this algorithm is 0(N~). Therefore,
routing protocols based on the use of flooding are not efficient in largescale
MANETs when taking into consideration the constraints of available bandwidth,
channel contention, and energy consumption.
This study investigated a gossipingbased algorithm (GOSSIP3) [14] that uses a
simple concept of probability such as tossing a coin to decide whether or not to
forward a packet for reducing the number of routing packets sent. The AODV+G
protocol was implemented by adding the GOSSIP3 algorithm into the Adhoc On
Demand Distance Vector Routing protocol (AODV) [15]. AODV+G is a
lightweight probabilistic broadcast protocol and is scalable because it can
significantly reduce the communication overhead compared with flooding
protocols in dynamic and frequently changing systems such as MANETs; it reduces
the number of routing packets required for getting routing information.
To evaluate the gossipingbased routing protocol, the performances of AODV+G,
AODV, and Dynamic Source Routing protocol (DSR) [16] were compared. AODV
and DSR are reactive routing protocols; their routes are determined when they are
needed (ondemand) by the source nodes using a path discovery process. The
proactive protocols, such as DestinationSequenced DistanceVector (DSDV) [17]
and the Optimized Link State Routing (OLSR) [13], determine routes by a routing
table periodically maintained in all of the possible destinations within the network,
which are not efficient in largescale networks. Thus, reactive ad hoc routing
protocols (ondemand) are better able to reduce routing overheads than proactive
protocols [13,14,18,20,21].
The purpose of this study was to compare the performances of AODV+G, AODV,
and DSR to determine which protocol performs best and to analyze the strengths
and weaknesses in terms of design considerations of ad hoc routing protocols and
8
critical performance issues. To achieve these goals, six performance metrics were
identified: packet delivery fraction, average endtoend delay of data packets,
routing overhead, normalized routing load, throughput, and average node energy
used, which is ignored in many previous research studies but is a very important
issue in ad hoc routing.
2.2.2 Overview of Routing Protocols
This section provides a brief description of the key features of the routing
protocols: DSR, AODV, and AODV+G.
2.2.3 Dynamic Source Routing (DSR)
DSR is an ondemand routing protocol. The motivation of DSR design is to
reduce routing overheads and to avoid the routing updates necessary with
conventional routing protocols such as distance vector or link state in an ad hoc
network. One of the key factors of DSR is the presence of a source route in the
packets header of each sender, and another is that a route cache is maintained in
each mobile node for caching the source routes learned. Thereby, DSR is capable
of adapting quickly to routing changes when node movement is frequent.
Route discovery and route maintenance are the basic operations of DSR. In route
discovery, when one node sends a packet to another node, each sender first checks
its route cache for a source route to the destination. If a route is found, the sender
uses this route to transmit the packet; otherwise, the sender initiates a route
discovery by broadcasting a route request packet and receiving a route reply packet
from the desired destination node or an intermediate node that has a route for the
target destination in its route cache. In route maintenance, a route error packet and
an acknowledgement are used. A route error is generated at a node when either a
link fails or a link can no longer be used due to a change in network topology.
When the sender receives the route error packet, the sender and all the intermediate
nodes remove the route link from their cache. Then, the sender can use an
alternative route in its cache to the destination or can initiate route discovery again
to find a new route [16].
Therefore, these two basic operations can reduce the number of overhead packets
by using the route cache, which means the source node can check its route cache
for a valid route before initiating route discovery, and if a valid route is found, there
is no need for route discovery. It is the key advantage of DSR because intermediate
9
nodes do not need to maintain routes in order to route the packets, which leads to
less control overhead [18]. The DSR protocol does not require any periodic
broadcasting or hello message exchanges for route maintenance; thus, it can save a
considerable amount of bandwidth in MANETs. However, the disadvantage is that
DSR will not be effectively scalable in a large mobile network and in a highly
dynamic mobile network since it is based on a source routing that requires each
packet to carry the full address such as every hop in the route from source node
to the destination [13].
2.2.3.1 Ad Hoc OnDeniand Distance Vector Routing (AODV)
AODV is based on combining the DSDV (DestinationSequenced Distance
Vector) and DSR algorithms. The motivation of AODV design is to use bandwidth
efficiently and to be capable of scalability to large populations of nodes in
dynamically changing networks. AODV uses an ondemand approach applied from
DSR, and thus, a route is established only when a source node needs to send
packets to some destination. In addition, AODV uses hopbyhop routing that relies
on routing tables and the sequence numbers applied from DSDV. Hence, a node
updates its route information only if the destination sequence number in the
currently arrived packet is greater than the destination sequence number already
stored at the node. It is to ensure all routes are loopfree routing.
To find a route from a source node to the destination, the basic operation of AODV
is a similar route discovery procedure as in DSR using the three messages: a route
request (RREQ) used to discover routes, a route reply (RREP) sent as an answer to
a RREQ, and a route error (RERR) reporting the new unreachable destinations.
However, unlike DSR, AODV route discovery uses hopbyhop routing, in which
each node remembers only the next hop and not the entire route as does DSR using
source routing. In route maintenance, AODV uses both a RREQ message and a
HELLO message. If the source node does not receive a RREP before its route
request expiration timer, then the source node rebroadcasts the RREQ message. If
the source node moves, then it can reinitiate a new route to the destination. If an
intermediate node moves, then the neighbors of the moved node can detect the link
failure by a HELLO message broadcasted periodically within a default rate of once
per second to maintain the local connectivity of a node, and sends a special RREP
to its upstream neighbors until it reaches the source node that can reinitiate route
discovery if still needed [15],
The key advantage of AODV is that it is adaptable to highly dynamic changing
networks because AODV can reduce routing overheads by ondemand based on
10
hopbyhop routing that only carries the destination IP address and the destination
sequence number [13]. Also, AODV has great knowledge of network connectivity
by using the HELLO message [12]. However, the HELLO message leads to
unnecessary bandwidth consumption. Also, flooding RREP messages in response
to a single RREQ message may lead to high routing overheads and packet
collisions.
2.2.3.2 GossipingBased Ad Hoc Routing (AODV+G)
AODV+G is a lightweight probabilistic broadcast protocol based on on
demand routing in MANETs. The motivation of AODV+G is to reduce the
redundant routing packets, thus reducing network bandwidth overhead and battery
power usage. The AODV+G protocol implemented by this studys simulation test
bed is based on the gossipingbased algorithm that is GOSSIP3(/j, k, m) [14]. The
concept of the gossipingbased routing algorithm is simple. A node broadcasts the
route request to its neighbors with probability 1. When a node first receives a route
request, it broadcasts the request message with probability p to its neighbors, and
discards the request message with probability 1 p. If the node receives the same
route request again, it discards it. Hence, the node broadcasts a received route
request at most once. However, if the gossiping operates with too low a probability,
the route request message may J/e out in a certain fraction of the executions.
To avoid the dieout problem, GOSSIP3(/?, k, m) was developed by Hass et al. [14],
The concept of GOSSIP3(/?, k, m) is that if the message does not die out, the node
assumes that all its neighbors would get the same message as well, and thus, if the
gossiping probability is p, it should receive pn messages for (m<=pn) from its n
neighbors. This algorithm function stipulates that at the beginning, a node
broadcasts the request message to its neighbors with probability 1 for the first k
hops and with probability p for the rest; if a node with n neighbors receives a
message and does not broadcast it, but then does not receive the message from at
least m neighbors within a reasonable timeout period, it broadcasts the message to
all its neighbors with probability 1. The heuristic values of p0.65, Al, m= 1 for
GOSSIP3(0.65, 1,1) were used, based on the experiments of Hass et al.[14] that
showed a reduction of message overhead up to 35% compared to flooding, and
applied it to the AODV+G approach. Therefore, AODV+G provided significant
performance improvements in largescale networks, especially reducing the number
of routing messages sent unnecessarily.
2.2.3.3 Comparison of Routing Protocols
11
The basic differences of the above three routing protocols are listed in Table
2.1. Time complexity (TC) is defined as the time required for the number of steps
to perform a protocol operation, and communication complexity (CC) is defined as
the number of messages exchanged in performing a protocol operation [22]. Route
discovery in ondemand routing protocols usually occurs by flooding a route
request message through bidirectional links or by piggybacking the route in a
route reply packet via flooding [13]. Thus, DSR and AODV have relatively the
same time complexity = 0(2D) and communication complexity = 0(2TV).
Gossipingbased routing protocol is based on the percolation theory [10], where in
each step, a node chooses a random node to forward messages uniformly with
probability p. Thus, the time complexity needed for all nodes in a diameter of the
network with size D is 0(log D), and the communication complexity is 0(log TV)
[19]. Therefore, a gossipingbased routing protocol is more efficient and scalable
than floodingbased ad hoc routing protocols by reducing the communication
overhead. For reliability, gossipingbased routing protocols depend on the
gossiping probability p. If p is equal to 1, its perfonnance is equivalent to flooding
routing as almost all nodes get the message in almost all executions, but if p is
below 0.59, then the gossip dies out in almost all executions [14].
Table 2.1 Comparison of Routing Protocols
Parameter DSR AODV AODV+G
Classification Reactive Reactive Reactive
Routing Source Hopbyhop Hopbyhop
Broadcasting method Flooding Flooding Gossiping
Route maintained in Route cache Route table Route table
Periodic updates No, as required in routing No, as required in routing No, as required in routing
Hello messages No Yes Yes
Loop free Yes Yes Yes
Suitable network Small networks Large networks & dynamically changing Large networks & dynamically changing
TC 0(2D) 0(2 D) 0(log D)
CC O(2A0 0(2N) 0(log A)
Advantages Reduce route discovery overhead Adaptable to large & highly dynamic topologies Reduce number of routing packets sent & small delays
Disadvantages Large delays Large delays Reliability depends on gossiping probability
D = diameter of the network,
N = number of nodes in the network,
p = probability
Small networks = up to few hundred nodes (< 200 nodes) in MANETs
13
2.2.4 Simulation and Performance Metrics
Simulations were performed using the ns2 network simulator with version
ns2.32 [23] over IEEE 802.11b. Details of the basic ad hoc mobile simulation
scenarios are as follow.
2.2.4.1 Traffic Models
The application traffic is CBR (constant bit rate). The sourcedestination
pairs are spread randomly over the network. Two traffic models were generated: 50
nodes as a small network scenario and 150 nodes as a large network scenario.
There are maximum connections of 30 nodes with a sending rate of 2 packets per
second. The data packet size is 512 bytes.
2.2.4.2 Mobility Models
The mobility model uses the Random Waypoint model in a rectangular field
of 1500/x300/m with 50 nodes, and in a rectangular field of 3300mx600m with 150
nodes. In this mobility model, each node starts its journey from a random location
to a random destination with the speeds of nodes randomly distributed between 0 to
20mis. Once the destination is reached, another random destination is chosen after a
pause time. Simulations run for 525 seconds for both the 50 nodes and 150 nodes
with changes in pause time, as from 0 to 500 seconds, by 100second increases. At
0 pause time, nodes are kept moving until 525 seconds simulated time; at 500 pause
time, nodes halt until end of simulation time. For fairness, identical mobility and
traffic scenarios are used across protocols. Simulation parameters are listed in
Table 2.2.
14
Table 2.2 Simulation Parameters
Parameters Value
Studied protocols DSR, AODV, and AODV+G
Number of nodes 50/150 nodes
Simulation time 525 seconds
Simulation area 1500aa?x300aa? for 50 nodes, 3300aa/x600aaa for 150 nodes
Node movement model Random waypoint
Traffic model CBR(UDP)
Speed of nodes 020ah/.v
Packet size 512 bytes/packet
Packet rate 2 packets/sec for 30 connections
Node pause time 0500 by 100 second increases
MAC layer IEEE 802.1 lb
Physical layer IEEE 802.11b
Bandwidth 11 Mbps
Gossiping probability 0.65
15
2.2.4.3 Performance Metrics
For performance comparison, six performance metrics [18,20,60] were
evaluated. They are as follow.
A. Packet deliveiy fraction (%): The ratio of data packets delivered to the
destinations to those generated by the CBR sources.
PDF =
f total packets received'
K total packets sent J
xl00(%)
(2.1)
B. Average endtoend delay (sec.): The interval between the data packet
generation time and the time when the last bit arrives at the destination. This
includes all possible delays caused by buffering during route discovery latency,
queuing at the interface queue, retransmission delays at the MAC layer,
propagation and transfer times.
ElEdelay = pkt start time pkt arrive time (2.2)
C. Routing overhead (packets): The total number of routing packets (in bytes)
transmitted during the simulation. For packets sent over multiple hops, each
transmission of the packet counts as one transmission. In our simulations, packets
are counted both in the RTR and the MAC layer transmissions.
RoutingOverhead total routing packets sent (2.3)
D. Normalized routing load (packets): The number of routing packets transmitted
per data packet delivered at the destination. Each hopwise packet transmission is
counted at the RTR layer as one transmission.
NRL =
f total routing packets sent + forwarded'
v total packets received ,
(2.4)
E. Throughput (bits/sec): A dimensional parameter that gives the fraction of the
channel capacity used for useful transmission, such that the total number of
16
delivered data packets divided by the total duration of simulation time is the
throughput.
Throughput =
r total packets received x pkt sizex 8^
v simulation time ,
(2.5)
F. Average node energy used (Joule): The average amount of energy used by
nodes to deliver correctly one byte of packets with respect to their transmit, receive,
and idle power consumption from a given initial amount of energy to each node.
NEU = node initial energy node final energy (2.6)
2.2.5 Simulation Results
To compare the performance of three protocols with respect to six
performance parameters, six pair graphs are presented. Each pair group shows the
performance results for both the small size (50 nodes) and large size (150 nodes)
network for different traffic pause times. Figures 2.2 (a) and (b) show the packet
delivery fractions of the routing protocols dependent on the network size. Figure
2.1(a) shows that AODV and AODV+G have similar performances and high packet
delivery between 70% and 90% from 0 to 500 pause times for 50 nodes. However,
in the large network size (150 nodes), Figure 2.2(b) shows that AODV outperforms
both AODV+G and DSR. DSR has a lower packet delivery rate: about 47% in the
small network and 9% in the large network at higher mobility as 0 pause time. DSR
packet delivery rate, at higher mobility rate when pause time is 0, drops about 69%
and 97% for the small and the large networks, respectively. As AODV+G
broadcasts packets with probability 0.65, it shows a good performance in the small
network and it outperforms DSR in the large network. DSR drops about 96%
packet delivery rate at the interface queue (1FG) compared with AODV+G
dropping about 27%, which is much lower than DSRs packet dropping. The major
reason for packet dropping in DSR is that the IFG is full due to carrying full
routing information for each packets header file; hence, a number of incoming
packets will be dropped. However, AODV and AODV+G drop packets mostly at
the RTR layer and MAC layer, about 40% and 15% respectively at higher mobility.
The average endtoend delays are shown in Figure 2.3 (a) and (b), the small
network and large network, respectively. DSR has high delay compared to AODV
and AODV+G, especially in the large network; from 200 to 400 pause time, DSR
17
demonstrates significantly higher delay than AODV and AODV+G. DSR has a
high packet drop, about 70% to 80% higher than other protocols, which means
DSR uses a source routing and route cache required a refreshment. In the large
network (see Figure 2.3(b)), AODV+G performs about 13% better than AODV at
high mobility as 0 pause time because AODV has to keep flooding packets to
broadcast its neighbors for exchanging RREQ and RREP messages until it
discovers a route.
The routing overheads are shown in Figures 2.4 (a) and (b), the small network and
large network, respectively. AODV clearly has the highest overhead at all traffic
mobility in both the small network and the large network from 200 to 500 pause
time because packets are kept flooding due to exchanging RREQs and RREPs.
DSR has a significantly high routing overhead at high mobility as 0 pause time.
The reason is that DSR routing requires each packet to carry the full address from
source node to the destination. Hence, we can expect that DSR is not good for
largescale networks. AODV+G performs about 13% better than AODV and much
more than DSR at high mobility in the large network because DSR suffers heavy
routing load at the RTR layer, about 72% more than AODV+G.
The normalized routing loads are shown in Figure 2.5 (a) and (b), the small
network and large network, respectively. AODV+G outperforms both AODV and
DSR at high mobility in the small network, and the routing load performance of
AODV and AODV+G is close to each other for most mobilities in the large
network. Also, DSRs normalized routing load is increased significantly at high
mobility in the large network because it depends on the packet delivery fraction and
the node movement.
The throughputs are shown in Figures 2.6 (a) and (b). The comparison between the
routing protocols is based on throughput measured in Kbits/second using different
mobilities. DSR has low throughputs at 0 through 400 pause times. In the small
network, AODV+G performs fairly consistently for most all mobilities (as from
100 to 500 pause time). In the large network, however, AODV performs its
throughput about twice better than AODV+Gs throughput at high mobility as 0
pause time because AODV has more packets sent than AODV+G; however, this
makes heavier work for the routing layer and network congestion.
Figures 2.7 (a) and (b) show the average used node energies of the routing
protocols for both the small and large networks, which heavily depend on the
routing overhead performance. In the small network, the three protocols consume
similar levels of energy. However, in the large network, DSR consumes almost
18
100% energy at high mobility as 0 and 100 pause times due to its high routing
overhead. Additionally, to show concrete evidence of the relationship between
overall routing overhead and energy consumption for each size of network, the
performances of these three protocols in a high traffic model based on a sending
rate of 4 packets per second in the large network (150 nodes) were compared. The
results are shown in Figures 2.8 (a) and (b). For the routing overhead, AODV+G
has less than both AODV and DSR, as shown in Figure 2.8(a). For the average
used node energy, AODV+G also consumes less, and it is fairly stable as is AODV
with increasing node mobility from low movement (500 pause time) to high
movement (0 pause time), as shown in Figure 2.8(b). Hence, one can expect that
AODV+G may be the most efficient routing protocol in largescale MANETs.
19
Figure 2.2 Packet delivery fractions for 50 nodes and 150 nodes at a variety of
pause times.
12 12
* AODVgossip
10 i *AODVgossip in ~#~A0DV k
A0DV ~ 4 DSR ,
8 i DSR l 8
* >\ \
3 6  6
4
f 4 V \ f 4 r"
< .A < i
2 "'"i ""
o 0
0 100 200 300 400 500 0 100 200 300 400 500
(a) 50 nodes / Pause rime (sec) (b) 150nodes 'Pause time (sec)
Figure 2.3 Average endtoend data packet delays for 50 nodes and 150 nodes at a
variety of pause times.
20
Figure 2.4 Routing overheads for 50 nodes and 150 nodes at a variety of pause
times.
Figure 2.5 Normalized routing loads for 50 nodes and 150 nodes at a variety of
pause times.
21
Figure 2.6 Throughputs for 50 nodes and 150 nodes at a variety of pause times.
Figure 2.7 Average used node energies for 50 nodes and 150 nodes at a variety of
pause times.
22
Figure 2.8 Routing overheads and average used node energies for 150 nodes with a
higher traffic rate of 4 packets/sec.
23
2.2.6 Summary
The main objective of this study was to measure the performance of three
ad hoc routing protocols (AODV, DSR, and AODV+G) and identify their
weaknesses and strengths under two different sizes of network: a small network
and a large network. To achieve these goals, we simulated these protocols using ns
2 network simulator with version ns2.32.
The simulation analysis results allowed us to find the following: First, DSR
performs very well at most traffic mobilities in the small network, although it uses
source routing. However, it is not suitable for the largescale network with high
traffic and node movement models because each packet carries full routing
information. Second, both AODV and DSR use flooding packets, and they have a
low endtoend packet delay especially for AODV, but high routing overhead. The
high routing overhead makes each node consume more energy as shown in Figure
2.8 (b). Finally, AODV+G is a promising and efficient protocol for high traffic and
node movement situations in a largescale network like cellular phone networks.
However, the AODV+G protocol needs more improvement in its throughput in
order to be widely accepted by many wireless applications.
24
2.3 AdaptiveGossiping for EnergvAware Routing in WSNs [77]
2.3.1 Introduction
Recent advances in wireless technologies and communications have
allowed wireless sensor networks (WSNs) to enable the development of lowcost
networking, low power consumption, and very small size devices, usually for low
data rate transmissions. WSNs require selforganizing capabilities [24] to be
capable of random deployment in inaccessible environments (e.g., monitoring of
ocean depth, fire detection, temperature) or ubiquitous environments (e.g.,
intelligent buildings, healthcare, living environments). Thus, various types of
sensor network applications in WSNs need wireless ad hoc network techniques
including routing protocols and algorithms to provide seamless and efficient
services to users. Many articles in the literature [2426] address the typical
challenges of sensor networks: (1) resource constraints such as limited processing
speed, communication bandwidth and energy supply, and (2) routing challenges
due to the dense deployment of sensor nodes either deterministically or randomly
distributed. The densely deployed sensors may require a high degree of interaction
between sensor nodes that generally use a conventional ad hoc routing method
based on a flooding algorithm.
This study focused on routing challenges to conserve the power of sensor nodes as
well as to increase communication efficiency. There are some critical problems
with flooding overhead causing broadcast storms [29] because many routing
messages are propagated unnecessarily. Furthermore, there exist high packet
collisions due to rebroadcasting sensor nodes that are close to each other and
periodical rebroadcasts. Therefore, routing protocols based on the use of flooding
are not efficient and significantly affect energy conservation that is the essential
consideration in WSNs.
To solve the problem, we propose an energyaware routing protocol improved by a
new adaptivegossiping algorithm that is a probabilistic broadcast mechanism
based on the percolation theory [10]. The concept of adaptivegossiping is simple 
when routing packets are broadcasting with a gossiping probability p, the p is
assigned by depending on the number of neighbor nodes. It is scalable because it
can significantly reduce the communication overhead compared to flooding and
other gossiping approaches for dense networks as WSNs. In the literature
[14,27,30,31], most gossipingbased routing protocols are static; that is, all nodes
have the same gossiping probability p for all gossip packets during executions
throughout the whole network, which is unnecessary. Some other adaptive
gossiping approaches [28,32] are not scalable effectively because a gossiping
probability p depended on a node of the reception of a gossip message within a
time interval, which raises overhead due to the duplicate messages.
In addition, we observe the performance impact of Node Traversal Time (NTT) that
should be enough to allow neighboring nodes to gossip for reliable communications
and suggest an optimal NTT value [14,15]. Therefore, this studys approach is not
only to choose an optimal value of gossiping probability p, but also to find an
optimal NTT so that it can support higher reliability and throughput, and save
energy in WSNs. We evaluate the proposed approach with two new energy
performance metrics: {Delay x Energy;) and {Normalized Routing Load x Energy').
These metrics suggest the energy consumption associated with both packet losses
and packet delivery successes that affect delay and routing overhead respectively.
Our simulation results indicate that the adaptivegossiping based approach
outperforms and uses less energy compared to flooding and (static) gossiping
based protocols for low data rate, densely deployed sensor nodes in a small
network with both static and mobile base stations, and different types of network
topologies such as peertopeer and multitoone (sink type) that is the important
topology in WSNs, where communications are typically between multiple sensor
nodes and a sink node or base station.
2.3.2 EnergyAware Routing Protocol and Energy Analysis
This section (1) briefly discusses the key features of the energyaware
routing protocol based on the adaptivegossiping algorithm called A_GSPUO(/v, and
then (2) mathematically analyzes the energy consumption of the broadcast
mechanisms.
The AODV [15] routing protocol was chosen to implement A_GSP
analyzing the energy consumption and evaluating performances of the adaptive
gossiping algorithm. Our first preliminary study [33] showed that reactive ad hoc
routing protocols such as AODV are better able to reduce routing overheads than
proactive protocols, and the simulation results showed that AODV outperformed
others at high mobility in a large network. Thus, to reduce energy consumption,
AODV may be preferable to other broadcast algorithms.
2.3.2.1 EnergyAware Routing Protocol Based on AdaptiveGossiping
26
A_GSPuo^. is designed based on the adaptivegossiping algorithm to reduce
redundant routing packets, which can save energy consumption by reducing
network overall overhead. Our adaptivegossiping algorithm has been developed
based on GOSSIP3(/?,A,/n) developed by Hass et al. [14]. This algorithm stipulates
that at the beginning, a node broadcasts the request message to its neighbors with
probability 1 for the first k hops and with probability p for the rest; if a node with n
neighbors receives a message and does not broadcast it, but then does not receive
the message from at least m neighbors within a reasonable timeout period, it
broadcasts the message to all its neighbors with probability 1.
However, there are some critical issues for broadcasting a message with probability
p depending on n neighbors in GOSSIP3(/?,A,/n). For example, given
GOSSIP3(ft65,/,7) is defined as
f if n < m, broadcast with p = 1
, (2.7)
[it n > m, broadcast with p = 0.65
which means this algorithm does not consider how many nodes are neighbored to a
node that broadcasts a message with p to its neighbors. For example, a node with
too many neighbors could yield high overhead and collisions, while too few
neighbors could result in unreliability even with a good heuristic gossiping
probability p. Thus, this static value of the gossiping probability p might not
improve overall performances in a sensor network where sensor nodes are densely
deployed in a WSN.
Therefore, our adaptivegossiping algorithm, called GOSSIP adapt(p/n>k,m), differs
from the GOSSIP3 for determining a gossiping probability p that is an essential
element of gossiping; this adaptivegossiping algorithm is designed for dense
sensor networks for a largescale network. From equation (2.7), let the adaptive
gossiping probability called piHtaPi be defined as
if n < m, broadcast with padapt = 1
if n > m, broadcast with padapt = p/n'
(2.8)
which means our gossiping probability pMu,pt is an adaptivegossiping dependent on
the number of neighbor nodes n to broadcast messages as illustrated in Figure 2.9.
27
We prove that our adaptivegossiping, A GSPao
energy efficiency significantly relative to routing overhead and endtoend delay by
both analytical and empirical results in the following sections.
For rest of k
Figure 2.9 AdaptiveGossip algorithm GOSSIP,,
28
2.3.2.2 Energy Analysis
This section analyzes the energy consumption of the broadcast mechanisms:
flooding, gossiping (static), and adaptivegossiping. At each node we consider only
the power consumed for both transmitting and receiving packets. The idle listening
power is ignored in our computation because it is the same for all nodes with small
amount power charged. We denote by N the number of nodes and n the average
number of neighbors of a node within the same radio transmission range in the
sensor network. We assume that the power required aPw for transmitting and the
power required Pw for receiving during a packet broadcasting process, where the
transmit power a required for a packet is about at least three times more than the
receiving power [61,62] to reach the next hop. The total number of packets sent per
node (SENT) and the average number of packets received per node (REVD) are
defined in the following subsections.
A. Flooding: When each node receives a requested packet, it simply rebroadcasts
the packet once to all its neighbors n. The average number of packets sent and
received per node during flooding is defined by
SENT,looiliilg = 1 (2.9)
REVD floating = n (2.10)
The average energy consumption ENG is obtained by (2.9) and (2.10) that
ENG
(aN + nN)xPw
flooding
N
= (a + n)Pw
(2.11)
B. Gossiping: When each node receives a requested packet, it broadcasts the
packet with probability p to its neighbors, and discards the request packet with
probability 1 p. The average number of packets sent and received per node during
gossiping is defined by
SENT***, st'Pl'VoPT = P
Nf,
o v' y
(2.12)
29
(2.13)
RE VDgossiping = X ''{ ] P ( '1 P = "P
i=0
The average ENG is given by
ENG.
(aA p + np N) Pw
gossiping
N
= (a + n) p Pw
(2.14)
C. AdaptiveGossiping: When each node receives a requested packet, it broadcasts
the packet to its neighbors with probability p/n where n is its neighbor nodes, and
discards the request packet with probability 1 p/n.
SENTadapl gossjpjn!, X i
i=0
' n' (p ] Y, P \
n 1 n
\n J l n /
Ni
= P
REVD
adopt gossiping
r\r vc
\l J
P_
\nj
P_
V nj
y
P
= n = p
n
(2.15)
(2.16)
The average ENG is given by
ENG
adapt
gossiping
(aN p + pN)Pv
N
a p Pw
(2.17)
Clearly, the adaptivegossiping algorithm has less energy consumed than the other
broadcast techniques from equations (2.11), (2.14) and (2.17) for n >1 and a >3 as
follows
(a + n)Pw> (a + n)p Pw>apPw
(2.18)
To prove that the A_GSPw,,/r outperforms AODV, we have experimented with
A_GSPUO(/, in two aspects of simulation testbeds: one for the static base station
WSN, and the other one for the mobile base station WSN.
30
2.3.3 Simulation and Performance Metrics
Simulations were performed using the ns2 network simulator with version
ns2.32 [23] over IEEE 802.15.4 [36], concentrating on the most important
consideration: energy efficiency. The simulations aimed to evaluate the
performance of the A_GSPa0(/, routing protocol compared with the original AODV
in tenns of main energy performance metrics: (Delay x Energy) and (Normalized
Routing Load x Energy).
2.3.3.1 Simulation Setup
Two scenarios designed to evaluate the performance of the A_GSPaw/v.
routing protocol over IEEE 802.15.4 were simulated: peertopeer and multitoone
(sink type) communication networks. The two scenarios were deployed basically in
a combination of beacon enabled mode and nonbeacon enabled mode followed by
the experimental setup [34], which showed a very high successful association rate
(more than 99%). The first scenario was for a peertopeer application traffic in a
WSN with statically fixed nodes; the second scenario was for a sinktype
application traffic, which is the important application for WSNs since traffic is
typically between multiple sensor nodes and a sink node or base station, in a mobile
WSN with randomly distributed nodes. Both scenarios ran in a multihop
environment and performances were evaluated with respect to the following
parameters.
Beacon enabled mode There were 101 nodes in an (80*80)/;; area with a 10
meter transmission range, where node 0 is the PAN coordinator as a sink node,
and all the other nodes as sensor nodes. For the beacon enabled mode, the same
value was set for beacon order (BO) and superframe order (SO) as BO=SO=6;
performance was a high successful rate 100% [34] with a low packet collision
rate [35].
Traffic models The application traffic that is CBR (constant bit rate) was used
for two traffic modes: peertopeer communications over a static sensor
network, and multitoone communications over a mobile sensor network. The
data packet size was 90 bytes with a sending rate of 0.1, 0.2, 1, and 2 packets
per second, respectively.
Mobility models The mobility model used the Random Waypoint model for
the mobile sensor network. Each sensor node starts its journey from a random
31
location to a random destination as a sink node with the speeds of nodes
randomly distributed between 0 to 0.02/h/.v and 0.2mis for 525 seconds
simulated time.
AdaptiveGossiping parameters Heuristic values were p = 0.65, k = 2, m = 1
for GOSSIParfa/(0.65//?, 2, 1), where the value p is based on the experiments of
Hass et al. [14]. We also agree that the gossip threshold of about 0.65 is an
optimal gossip probability value in this studys simulations associated with
NTT = (/ x Node Traversal Time) for /= 1, 2, 3, and 4 and given Node
Traversal Time = 30ms.
Table 2.3 Simulation Parameters
Parameter Value
Number of nodes 101 nodes in 80x80m2
Transmission range 10 meters
BO and SO 6
Traffic model CBR(UDP)
Traffic direction Peertopeer for 20 flows Multitoone for 30 flows
Packet size 90 bytes/packet
Packet rate 0.1,0.2, 1, 2 packets/sec
Node movement model Random waypoint
Speed of nodes 00.02 m/s, 00.2 nils
Gossiping probability 0.65
Active_Route_Timeout 40 sec
N ode_T raversal_time 30, 60, 90, 120 ms
Initial energy 600 J
txPower 0.6 mW
rx Power 0.3 mW
ildePower OASmW
32
2.3.3.2 Performance Metrics
For performance evaluations, our two means of performance metrics,
{Delay x Energy) and {Normalized Routing Load x Energy), are presented for
analyzing energy efficiency. Also we consider other important performance metrics
for routing protocol evaluation. The two performance metrics are as follow.
A. Delay x Energy> (DE): The energy consumption associated with packet loss
ratio that impacts on delay; the equation is defined as:
where PDF is the packet delivery fraction, which is the ratio of data packets
delivered to the destinations to those generated by the CBR sources; E2Edelayavg.,
which is the average endtoend delay that includes all possible delays caused by
buffering during route discovery latency, queuing at the interface queue,
retransmission delays at the MAC layer, propagation time, and transfer time; and
NEUavg., which is the average node energy used, in Joules, from a given initial
amount of energy to each node.
B. Normalized Routing Load x Energy (NRLE): The energy consumption
associated with packet delivery successes that impact on routing overhead; it only
concerns routing packets as forwarded packets and received packets at each
intermediate node in a given sensor network. For analyzing energy efficiency of a
routing protocol, it is a very interesting performance metric, which equation is
defined as:
where NRL is the normalized routing load for the number of routing packets
transmitted per data packet delivered at the destination. Each hopwise packet
transmission is counted at the RTR layer as one transmission. Thus, NRL is an
important factor to evaluate the efficiency of the routing protocol. The following
simulation results have been averaged over 10 times run with different seeds.
I 100 )
(2.19)
NRLE = NRL x NEU
(2.20)
33
2.3.4 Evaluations
To compare the performance of two protocols, A_GSPIJ0(/V and AODV, with
respect to the above performance parameters, we present important graphs of the
performance results in the sections that follow.
2.3.4.1 Node Traversal Time (NTT)
For a high efficiency of energy consumption, node traversal time for one
hop is a significantly important factor in the adaptivegossiping parameters. If one
chooses a short NTT that causes a new route discovery even if a valid route is still
available, resending packets with p = 1 is like flooding to neighboring nodes; if
one chooses a toolong NTT, it might send packets on an invalid route, hence
packet delay, eventually increasing endtoend delay. Thus, these two cases of NTT
seriously diminish energy efficiency and also overall performance in a dense
deployment of sensor networks.
Our experimental results enabled us to find an optimal NTT value. As shown in
Figure 2.10, the performance results are based on a packet sent rate of 1 per second
by different NTT values between 30ms and 120/n.v in the test bed of a static ad hoc
WSN. Figures 2.10 (a) and (b) present the packet delivery fraction and the
throughput, respectively, and show that A_GSPno
particular, A_GSP(TO(/, has a 56% higher packet delivery and a 55% higher
throughput rate than AODV at 120/n.v of NTT. As shown in Figures 2.11 (d) and
(e), the adaptivegossiping algorithm consumes much less energy than the AODV
floodingbased method, whereas A_GSPU0(/, has significantly less E2E delay,
between 87% to 91% at each NTT compared to AODV, as shown in (d)
DelayxEnergy performance. In addition, Figure 2.11(e) shows that A_GSPaodv
demonstrates significantly lower routing overheads than AODV, 86% lower at
120ms of NTT, even though Figure 2.10(c) shows that the average node energy
used in A_GSPoa/, and AODV is close to each other for most NTT values. The
reason is that AODV has to keep flooding packets to broadcast to its neighbors for
exchanging RREQs and RREPs until it discovers a route.
34
aodv 85.25 I 75.62 ! 56.33 35.74
Node Traversal Time (ms)
Figure 2.10 Packet sent rate 1 per second by increasing NTT values.
35
5*
*
C3
Q
600
Node Traversal Time (ms)
Figure 2.11 Packet sent rate 1 per second by increasing NTT values.
36
2.3.4.2 Communication Network Traffics
In the peertopeer communication network that has stationary sensor nodes
in a WSN, comparison results between the two routing protocols with respect to
Throughput, DelayxEnergy, and NRLxEnergy analyzed by different packet sent
rates per second (pps) are shown in Figures 2.12 (a), (b) and (c). The throughputs
of A_GSP00(/V are slightly better at most packet sent rates. In addition, A_GSP(rojv
outperforms AODV in the DelayxEnergy performance measured (b); AODV
consumes much more energy (associated with endtoend delay caused by packet
loss), about 92% at 0.1 pps and about 54% at 2 pps. Moreover, as shown in (c) for
the NRLxEnergy performance measured, A_GSPao
(between 22% and 51 %) than AODV. This happens because AODV creates a route
with higher routing overhead to keep flooding packets due to exchanging RREQs
and RREPs that also cause higher endtoend delay in a network.
In the multitoone (sink type) communication network that has mobile sensor
nodes in a WSN, its performances are measured by differing the speeds of mobile
nodes between 0 to 0.02mls and O.lmls for all packet traffics through sensor nodes
to a sink node. A comparison of performance of the two protocols based on the
speeds of mobile nodes has been analyzed by differing the packet sent rates per
second as shown in Figure 2.13.
According to the throughput data in Figure 2.13(a), the two protocols perform
similarly at low packet sent rates of 0.1 pps and 0.2 pps. A_GSPa0(/v outperforms
AODV at a high packet sent rate of 2.0 pps with a high speed of mobile nodes as
O.lmls. As presented in Figure 2.13(b) DelayxEnergy and (c) NRLxEnergy,
performance results show concrete evidence of the relationship between endtoend
delay for packet loss and energy consumption. A_GSPÂ£/W/, consumes much less
energy than AODV, especially for 2 pps; about 40% less energy is consumed at
low speed O.Olm/s and about 66% less energy is consumed at high speed O.lmls. It
also suggests substantial evidence of the relationship between overall routing
overhead for packet delivery successes and energy consumption. AODV has a
greater routing overhead for most all packet sent rates and speeds of mobile nodes,
significantly for 2 pps (about 72% at low speed O.Olm/s and about 76% at high
speed O.lmls). Hence, we can expect that A_GSPUO(/v may be the most efficient
routing protocol in high traffic WSNs. Through observation of the performance
results, it is clear that lower endtoend delay and overall routing overhead are
significant factors in terms of energy efficiency.
37
3
C.
5Jj
3
2000
Â§5 1500
o [5 1000 '
* 500 jjp
QÂ£ o
Z 0.1
; 0a_gsp 363.91
; naodv 629.42
0.2
336.21
654.18
0.5
433.61
569.22
1.0
567.57
734.53
2.0
882.44
1827.81
Packet Sent Rate (pkts/sec)
Figure 2.12 Peertopeer application traffic by increasing packet sent rates in a
static base station WSN.
38
300
0.1 0.2 0.5 1.0 2.0
Packet Sent Rate (pkts sec)
a_gsp*=0.02m s 0aodv*=O.O2m s Sa_gsp*=0.2m s E3aodv=0.2m's
Figure 2.13 Multitoone application traffic by increasing speeds of mobile nodes
(all sensors and a sink) in a mobile base station WSN.
39
2.3.5 Summary
The adaptivegossiping routing implemented by the A_GSP(JO(/,. protocol is
proposed as an energyaware routing for densely distributed WSNs. The gossiping
probability padapt was defined as an adaptive gossiping by controlling a number of
neighbor nodes n to broadcast messages associated with NTT parameters. To
evaluate the energyaware performance of A_GSP(,0(/V routing protocol based on
adaptivegossiping compared with the original AODV based on flooding, we
introduced two new performance metrics: (Delay x Energy) and {Normalized
Routing Load x Energy). Our analysis of energy efficiency performances proved
that our A_GSP0,/V approach greatly reduced endtoend delay and overall routing
overhead against the flooding problems, which significantly reduced energy
consumption and prolonged network lifetime in WSNs.
40
3. Analysis of Ad Hoc Wireless Networks [ 107, 108]
3.1 Introduction
In ad hoc wireless networks (AWNs), the provision of Quality of Service
(QoS) guarantees is much more challenging than in conventional wireless
networks, mainly due to node mobility, multihop communications, contention for
channel access and a lack of central coordination. QoS guarantees are required by
most multimedia applications in such networks. These applications typically have
delaysensitive and high bandwidth requirements, especially for wireless channels
shared among adjacent nodes (which represent hosts/routers in this paper), and
network topology can change as nodes are moving in an AWN. In recent years,
QoS routing has received increased attention because it plays an important role in
providing QoS in AWNs [65, 66] by selecting routes with satisfied QoS
requirements and achieving global efficiency in resource utilization [66]. In the
literature [67,68,69], many of the proposed solutions focus on two metrics, high
performance throughput and delay guarantee, based on providing QoS
requirements. Moreover, the majority of study results [70,71,72] in this field are
based on simulation models due to the complexity of ad hoc wireless networks.
This study investigates fundamental and important properties of ad hoc wireless
networks through realistic mathematical modeling of a given network. To develop
new theoretical models of AWNs, main studies focused on node degree,
connectivity, hop count, capacity and queuing network modeling, as shown in
Figure 3.14 at the inner zone. These fundamental properties of AWNs significantly
affect estimating endtoend delay for achieving highaccuracy of QoS
measurements and low overhead of routing communications. This study makes a
substantial contribution to a better understanding of core properties of AWNs
through clear formulated theoretical models.
41
Figure 3.14 Scope of this studys work in the field of ad hoc wireless network
research: The inner zone presents topics in the main focus area of fundamental
properties of ad hoc wireless networks for a realistic mathematical model. The
middle zone includes important topics used to develop a QoSaware routing
protocol and make assumptions for evaluating performances. The outer zone
presents broad topics not included in this study but are considerations related to
energy efficiency.
42
3.2 General Network Model of Ah Hoc Wireless Networks
This analysis of ad hoc wireless networks (AWNs) is based on fundamental
models for (1) the spatial node distribution, (2) the wireless channel between nodes,
and (3) the movement behavior of the nodes that are needed to represent the
dynamic topology of an ad hoc wireless network. Details of network topology,
common assumptions and notations are defined in the following.
3.2.1 Network Topology
Many challenging problems exist for each of the other related system
environments. Therefore, we model a network topology that is suitable for basic
evaluation of various routing mechanisms with regard to the challenges of QoS
aware routing in AWNs. The fundamental model of network topology is based on
homogeneous AWNs, where each mobile node shares the same radio capacity that
causes a serious bottleneck [ 111 ] so that most available bandwidth is consumed and
routing control packets are overhead when the traffic is heavy. Hence, the
homogeneous ad hoc network requires QoS support when it meets delaysensitive
applications. Other important assumptions are that the network topology is an
undirected random geometric graph where a set of network nodes is randomly
placed on a twodimensional simulation area of size A = axb for a > b ; each node
has the same radio transmission range r0; and two nodes can establish a wireless
link if they are within range of each other (see Figure 3.15).
3.2.2 Assumptions
Consider the following problem: From a set of N network nodes, each node is
independently randomly placed on a twodimensional simulation area A. A uniform
random distribution is used, such that with Poisson process for large N and large A,
one can define a constant node density A = N/A To model the wireless
transmission between the nodes, a radio link model is assumed in which each node
has a certain transmission range r0. Two nodes are able to communicate directly
via a wireless link if they are within the range of each other. In the transmission
space, the homogenous transmission range guarantees that all links are
bidirectional. All nodes are free to move in the system area according to a certain
mobility model (e.g., random waypoint, random direction, street model, etc.). Table
3.4 lists the notations used in this section.
43
Figure 3.15 The model of network topology is an undirected random geometric
graph. Nodes are randomly distributed in a network of size Aaxb and each node
has the same radio transmission range r0.
44
Table 3.4 Notations
A : Twodimensional simulation area of A = axb for a > b
N : The total number of nodes in a given network
A
'i(v)
Â£()
r,(N)
rjN)
(
CO
E(()
E(L)
E(H)
T
m
r,
E(T)
The number of neighbors of a node for (/? = 0,1,2,) defines within
its transmission range
The node density A = N/ A under the total number of nodes per unite
area
The same fixed transmission range of each node
The expected number of neighbors of a node within its transmission
range
The critical transmission range of a node based on the flooding routing
algorithm
The critical transmission range of a node based on the adaptive
gossiping routing algorithm
The distance from a node to the next hop node is the farthest neighbor
node (Â£" = x) of a node within its transmission range
The uniform distribution on
The expected perhop progress
The expected distance within a rectangle of size ax[a/ 2)
The expected hops between random sourcedestination pairs
The link available time
The distance that the farthest node (as a relay node) traveled to move
out of the transmission range of its neighbor
The relative velocity between the two neighbor nodes
The expected link available time
45
3.2.3 Basic Theoretical Concepts
AWNs are generally modeled as communication graphs. We provide a brief
review on basic graph theoretical concepts, including some definitions of graph
theory, node degree, and connectivity.
3.2.3.1 Graph Theory
In this network model, we can represent an AWN as an undirected graph G.
A graph of a pair G = (F, E) consists of a set of n nodes (V = vertices) and a set of
m node pairs (E = edges). In a graph G, the set of nodes, denoted by V(G) = {v/, ...,
v, represents ad hoc nodes as the networkenabled ad hoc devices, and the set of
edges, denoted by E(G) = \e/, .e\, represents the wireless communication links.
3.2.3.2 Node Degree
The degree d(v) of a node (vertex) v is the number of neighbors of a node v,
such as the number of links (edges) at v [37]. A node of degree d = 0 is isolated,
which means it has no neighbors (see Figure 3.16).
Hence, for G=(V, E) with d(v) > 0, Vve V is equivalent to dmm(G) > 1, the
minimum node degree of G is defined as
rfn(G) = min{
(3.1)
the maximum node degree of G is defined as
(3.2)
and the average node degree of G is defined as
(3.3)
Clearly,
d...(G) < daYg (G) < dmax (G)
(3.4)
46
Figure 3.16 Illustration of an isolated node.
3.2.3.3 Connectivity
A fundamental question about any graph is whether or not it is connected.
For example, a graph is connected if any two of its nodes (vertices) can be joined
by a path; otherwise, it is disconnected [37, 38]. Suppose that Aj,X2,A',,,XN
are independent random points in W1, and let the area of a unit ball be denoted n.
Let a set x~ iAj,A',,, A'^.} be independent random variables with the density
/ of the uniform distribution on a rectangular region of area A. Since
connectedness is a monotone property, a natural object of study is the connectivity
threshold for a finite set % c defined to be the minimum value of r such that
the graph G(X'J') is connected, where r is the transmission range. Such that the
threshold distance of G(X',r) has at least one edge which is the smallest interpoint
distance in x There is a variety of threshold distances for x We are interested in
the connectivity threshold for x *s als hie longest edge length of the minimal
spanning tree on x [78]. In terms of communication networks, all nodes of a
connected network can communicate with each other over one hop or multiple hops
47
(links), whereas in a disconnected network there are several islands of sub
networks that cannot reach one another.
If A is a positive integer (k = 1, 2,...), a graph G of order greater than k +1 is said
to be knodeconnected, or in short, Aconnected if it cannot be disconnected by the
removal of Al or fewer nodes. The node connectivity A(G) of a connected
graph G is the minimum number of nodes whose removal disconnects G such that
if k(G) > k the graph G is called Aconnected, otherwise disconnected if k(G) = 0.
From the Aconnected, we define A connectivity threshold from Penroses definition
[78]. For a finite set N in W1, and a positive integer A, the kconnected threshold
rk (%) is the infimum of all r, for which G{x\r) is Aconnected.
Second, a graph G is said to be Aec/geeonneeted, or ec/geconneeted, if it cannot be
disconnected by the removal of Al or fewer edges. The edge connectivity
kedge(G) of a connected graph G is the smallest number of edges whose removal
disconnects G such that if kedge{G) > A, the graph G is called Ac'c/geconneeted,
otherwise disconnected if kedge(G) = 0 The kedgeconnected threshold rk (X) is
the infimum of all r or the threshold value of r, for which G(%\r) is kedge
connected. Let the largest Anearestneighbor link denoted by r, (y) be the
**imn
threshold value of r, for which G(x;r) has minimal degree at least A. One has
A (G) < A,(/?c, (G) < dmin (G) for any graph as shown in Figure 3.17, and if / is a
finite set in M^with more than A +1 elements, then
.U) (35)
Therefore, we will apply the kconnected threshold rk(x) for high connectivity of
an ad hoc wireless network.
In this study we also concentrate on the special case of the dense limit regime that
is based on asymptotic properties of the graph G(x,i](N)) with N vertices. The
dense limit regime is expressed as
48
r\(N)~
Alog(N)
\i/rf
N
(3.6)
where the typical node degree grows logarithmically in N. When
jVrj (,/V)
regime [78].
One can obtain as follows the asymptotic of t](N) for all N. Suppose that the
dimension d = 2 and the points xN are uniform distributed on the twodimensional
area of A = axb for a > b. Hence, with probability 1 (w.p. 1),
lim
,v~
(
\
Kn{r\N)f
log(A)
= A
(3.7)
by Penrose in Theorem 13.2 [78], (see Appendix A for equation 3.7). We have the
expected number of neighbor nodes for all nodes N, expressed as
(3.8)
In early researches, Gupta and Kumar [49] studied connectivity among nodes
distributed uniformly in a unit disc. They determined that if the units transmission
range is set to r(N) = r^^ + c(JV) ^ tjien tie resulting network is asymptotically
V JtN
connected with probability 1 if and only if c(jV)>+. The minimum value of
r(N) that ensures connectivity with high probability is called the critical
transmission range. Xue and Kumar [50] concluded that the number of neighbors
of each node needs to grow (log A)for connectivity as shown in the following
theorem. Santi [51] studied the critical transmission range for connectivity in
mobile ad hoc networks and showed r= cj
v ;
Jin A
kN
for some constant c > 1. The c
value is assigned by the random waypoint model with pause time p and node
49
velocity v, such as c 
0.521405
In TV
N
 if p> 0. When p 0, they have r
with high probability for connectivity. However, according to Gupta and Kumar
[48], connectivity of the entire network may not be needed; rather, only needed is
that every source is able to communicate with its chosen destination. Thus, the
Santi model is appropriate for sparse networks. In another approach [39], for a two
dimensional random node deployment, the transmission range required to achieve
connectivity probability p is defined by r >
to 1, then Y >+.
ln( 1 /?v)
Xn
. However, if the p is close
Thus, the next sections are concerned with the following questions. Given
r0(N)>0, first, how many neighbor nodes n are in /t(/0(jV))2 of G(/;r0( A'))?
The second question, what is the smallest value of r0(N)2 That is the largest
nearestneighbor link for which G(x,r0(N)) has minimum degree?
Figure 3.17 Connectivity: The graph G has nodeconnectivity 1, edgeconnectivity
2 and the minimum node degree 3 respectively k(G) = 1, kClige(G) = 2 and c/,nui(G) =
3. The graph G can be disconnected by removing either a single node such as c and
removing two edges such as ac and be.
50
3.3 Analysis of Communication Area for AdaptiveGossiping
3.3.1 Neighbor Nodes of A Node
Ad hoc wireless communication systems consist of nodes that share a
common communication medium such as a radio channel; for example, nodes that
can communicate with each other within the transmitter power range r0(N) over a
wireless channel. Two nodes can communicate with each other with one hop if the
distance between them is less than r0(N) [40]; a group of nodes can communicate
with each other with a multihop path if they are located in the range r0(N) [39],
Thus, an isolated node cannot exchange any information with other nodes unless it
moves into the range of another node or until another node passes by in a mobile ad
hoc network. This might cause an unacceptable message delivery delay.
What is the probability that n neighbor nodes of all N nodes are within a certain
distance ru(N) in the twodimensional network area A? The entire area A of the
network is viewed as a large rectangular area. To solve this problem, we consider
all nodes of the network with the following assumption.
Assumption 3.1 All nodes are placed uniformly and independently in the two
dimensional network area A.
With Assumption 3.1, the probability of finding n nodes in a range r0(N) is defined
by the binomial probability mass function as
' N'' U(r0(N)f] / .> \ *('()
{J A J A v 7
(3.9)
Assumption 3.2 Assume that
A
From Assumptions 3.1 and 3.2, we can approximate equation (3.9) with the
Poisson distribution with mean A = N/A The probability that the number of n
neighbors of a node within its transmission range r0(N) is given by
51
/>(;,)= ^/q(A^ ) e^m2' n = 0i 1?2,.
(3.10)
The probability that a node has no neighbor nodes (i.e., it is isolated) is
_ n\ 
P(n = 0) = e
(3.11)
and if we say that a node v has no neighbor, i.e.,
P(d (v) = 0) = P(n = 0) = e~Mru{X)]2. (3.12)
A network graph G in which none of the N nodes is isolated is satisfied as
d(v) > 1, Vve G<Â£=> dmin (G) > 1 by (3.1) and (3.5).
The probability that a node has at least one neighbor within its transmission range
r0(N) is
P(n > 1) = 1 P(n = 0) = i _ (3.,3)
Thus, the expected number of neighbors of a node within its transmission range r0
is
E{n) = Aff{r0(N))\ (3.14)
which can be expressed that let rt (N) denotes the transmission range of a node for
flooding based broadcasting mechanism as
^(/^(AO)2 =log(A). (3.15)
/i
Next, we consider that the number of neighbor nodes for adaptivegossiping, rather
than for flooding. According to the definition 3.1, what is the probability that the
52
number of neighbors is selected to forward packets, denoted by na within a certain
distance rn(N) in the twodimensional network area .4 with given Nnodes?
Definition 3.1 The adaptivegossiping is a broadcasting mechanism that
forwarding nodes are selected with a probability that assigned by the number of
neighbors of a node, instead of the flooding that is simply to broadcast all of
neighbors of a node as probability one.
We know that the expected number of neighbors for flooding is log(jY) The
flooding method transmits routingrelated packets to all neighbors of a node within
its transmission area of , but the adaptivegossiping method with
probability pn sends routingrelated packets to only selected neighbors of a node
within its x(rg(N)y.
Since the average of neighbors is log(A^) by (3.8), we can define an adaptive
gossiping probability pn at each node for sending packets to its neighbors
N
n
A
, expressed
as
npn=\og(N) (3.16)
log {N) Pn = (3.17)
n
for n > log(7V). Therefore, the adaptivegossiping probability pn can be defined by
P
which means pn will be assigned a value of (1 / n)\og(N) if and only if the actual
number of neighbors is larger than the expected number of neighbors, otherwise it
will take a high probability 1, (see in Figure 3.18).
= min
log {N)
(3.18)
53
log(jV)
We need that< 1 most ot the time, so we impose the condition that for
n
a > 1 for adaptivegossiping
er log (TV) <Â£(). (3.19)
So the expected number of nodes of a node for adaptivegossiping is
= or log(7V). (3.20)
Since log(yV) = (AO) ,
^x(rg(N)f = a2 ^(r, (N)f (3.21)
A A
/;(7V) = cr(/(yV)). (3.22)
In a given network area of A with N nodes, where all the nodes have the same
critical transmission range for flooding and adaptivegossiping, denoted by rt (N)
and / (AO respectively. Figure 3.19 shows a comparison of the number of neighbor
nodes with flooding and adaptivegossiping for rg(N) = a^rt (N)J in the given
network A. However, flooding is much heavy overloaded to communication each
other where the network A is full connected, compared to adaptivegossiping with
high connectivity of given network A. Therefore, our adaptivegossiping algorithm
can conserve the network resources in ad hoc routing communication networks.
54
For rest of k
Figure 3.18 AdaptiveGossip algorithm GOSSIP,,,k, in),
where pn is different from padapt in Figure 2.9.
55
50C
40C
30C
200 
100
0
0 200 400 6C0 800 1000
(a) Flooding
(b) Adaptivegossiping
Figure 3.19 Comparison of broadcasting mechanisms: (a) flooding method
transmits routingrelated packets to all neighbors of a node within its transmission
area of ccn{if (A))", but (b) adaptivegossiping method with
pn = (1 / n)log(A) sends routingrelated packets to only selected neighbors of a
node within its ^(^(/V)) in the network area of size A (1000x500)m2 with
A = 100 nodes for rg(N) = (A)) by (3.22).
56
3.3.2 Transmission Range with High Connectivity
Consider the problem: What is the critical transmission range for
connectivity in the twodimensional network area of A? When the range r0(TV) for
transmission is too small, an ad hoc wireless network loses connectivity and loss of
packets from increasing r0(TV) due to the area of the conflict involved [48], Most
studies consider how the transmission range is related to the number of nodes TV,
distributed according to uniform or Poisson distribution in a unit area.
First, let us concern ourselves with the case of flooding. We assume that a network
has TV nodes placed randomly at uniform in the rectangular area [a, b] of A, and
each node has the critical transmission radius ;y(TV). Thus, we have the critical
transmission range r, (TV) for flooding by (3.15) as
w*))='"f0 (3.23)
(3.24)
which guarantees asymptotic connectivity of an ad hoc wireless network with high
probability 1, if and only if TV > oo by (3.7) for a routing algorithm based on
flooding mechanism.
Next, our concern is the adaptivegossiping. We know that the expected number of
neighbors of each node for adaptivegossiping is a2 log (TV) from (3.20).
We can define the critical transmission range of adaptivegossiping by (3.20)
r (TV) = or
lA log(TV)
kN
(3.25)
Therefore, the result of the critical transmission ranges is
r.rW
(3.26)
57
In simulation tests, for the example of flooding, let us find the radio range of all
nodes to guarantee asymptotic connectivity of the network with probability 1 for TV
= 100 nodes in a simulation area of size/l = (1000x500)aw2 which yields a node
density of A2.10^ According to equation (3.24), we can set the critical
transmission range rt (TV) ~ 86/;/ to achieve high connectivity. Therefore, the
number of neighbors of a node with rt (TV) ~ 86m is n = log(TV) = 4 which is equal
to the expected number of neighbors of
E(n) = A/r(/) (TV))' = 2 10~4 x3.14x862 = 4 according to equation (3.14) and
(3.15). For the adaptivegossiping, the number of neighbors for the adaptive
gossiping can be obtained as that E(n) Ak^v^N)^' = a2 log(A) = 10 for a = 1.5
by according to equation (3.20). Hence, the critical transmission range
rg{N)~\28m to achieve high connectivity is computed by equation (3.25). Figure
3.20 provides a graphical comparison of CTR for flooding and adaptivegossiping
algorithm for rt (TV) < rg(N). The graphs of CTRs with our adaptivegossiping and
flooding algorithms for values of a between 1.5 and 5.0 are shown in Figure 3.21.
Figure 3.20 Comparison of the critical transmission range (CTR) for flooding
algorithm and adaptivegossiping algorithm.
58
600
CTR: flooding
CTR: adaptive
CTR: adaptive
CTR: adaptive
CTR: adaptive
CTR: adaptive
CTR: adaptive
CTR: adaptive
CTR: adaptive
gossiping
gossiping
gossiping
gossiping
gossiping
gossiping
gossiping
gossiping
w a!pha=1 5
w alpha=2.0
w alpha=2 5
w alpha=3.0
w a!pha=3.5
w a!pha=4.0
w alpha=4.5.
w alpha=5.0
60 260 460
660 860 1060 1260
N = Total number of nodes
1460
1660
1860
2000
Figure 3.21 The critical transmission range (CTR): The analysis results are
compared with r, (AT and rg(N) for flooding from (3.24) and adaptivegossiping
from (3.25) respectively, by increasing nodes N between 60 and 2000 in a
simulation area of size A = (1000x500)/2.
59
3.4 Analysis of Hop Count
3.4.1 Hop Count for Flooding
An analysis of the delay properties in AWNs requires quantifying the
relationship between the source and destination distance, denoted by L, and other
parameters, such as the transmission range and the node density. This studys hop
count model attempts to estimate the expected number of hops for a routing packet
through a source to a destination assuming a routing protocol based on the shortest
path principle.
Using typical modeling assumptions, it is assumed that all nodes are homogenous
and have the same fixed transmission range rt (N), where a node can reach any
nodes within the transmission range for a given node density X N/A We present
the analysis for the twodimensional case where nodes are deployed in a
rectangular area as (A = axb) for a > b The distance from a node to the next hop
node is denoted by C, and the mapped perhop progress onto the line connecting
the source and the destination nodes is denoted by C. We present the analysis for
the twodimensional case where nodes are deployed in a square area of A. We
assume that the next hop is the farthest node, denoted by x, in an area of between
/r/2 and /r/2 towards the destination node, where 6n for the next hop is
limited within this area (see Figure 3.22).
60
Figure 3.22 Perhop progress: the next hop is the farthest node (Â£" = x) in an area
of (~n/2,rc/2) toward the destination node, where CO is uniform on [0,^/2].
61
The probability that a node has at least one neighbor node within the area of
(A0)~ .v2 jis defined by
P(C >x) = l/?r((r/(^))2x2) = 0
= \e
(A^))'.r2
(3.27)
/iff (r, (A))"v2 /. .7 , \
where e v ;is there is no node in the area of k (>>(/Â¥)) x~ then the
cumulative distribution function F of a continuous random variable tfis F(x)that
can be expressed in terms of the probability P(Â£ < x) as
F(x) = P(Cx)
r /ifff(MzV))2.,2)
= 1 1 e K
^fff(r((.V))2.v2]
= e v
(3.28)
Thus, the distance of a point to its farthest point x is defined by the probability
density function f(x) of the farthest distance of P{Â£ = .y) for x > 0 as
f(x)=^F(*)=F'(x)
/Iffff, (V))2.!'2!
= e J
Xff(r, (.V )) +/iff.v2
e '
= 2Xkx e
/lff(/, (.Vlf.v2)
(3.29)
62
To estimate the expected perhop progress, we assume that the angle, denoted by co
is uniform on [0,/r/2], between the line connecting the node to its next hop
({T='v)(that x is the farthest node within the transmission range;;) and the line
connecting the source node and the destination node is uniformly distributed
between nj2 and k/2. Thus, the expected progress E(C) is
E(t) =
XCOSO) dxdco
n
aN
4sin
A
KX2 N
' dx
aN
 4sin
A
( K^
V2y
2k N
A
4kq rfi
kN
a
, A >
(See Appendix B for equation 3.30).
(3.30)
The expected perhop progress can be represented as Fl[0,rf(N),A) = E(Â£)
because we only need to know the area 0, the minimum transmission range /; and
the node density A to compute the expected perhop progress E{(). For example, if
Ft (tt,86,2104) where 0n , rt(N) 86;;; with N = 100 nodes,
A = 100/(1000x500)m2, then the E(C) = 48;;;. In Figure 3 .23 shows the results of
the expected perhop progress for flooding. Therefore, the hop count for the
distance L between a random source to destination pair is
L
WY
(3.31)
63
Figure 3.23 The expected perhop progress of flooding routing algorithm in the
critical transmission range (CTR). E{C) = F(\d,rt{N),X) = Ft{n,rt{N),2\0~4)
from (3.30), where rt (N) is defined from (3.24) with the total number of nodes N
between 60 and 2000 in a simulation area of size A = 1000x5002.
64
3.4.2 Hop Count for AdaptiveGossiping
In this subsection, we present a hop count for adaptivegossiping that
receiving nodes are selected randomly from a sending node with probability
assigned by the number of neighbors of the sending node. Suppose that n the
number of neighbors in ^(^(N))", Â£ = the distance of the farthest node v in the
critical transmission range, Â£ = the number of neighbors picked for transmission
(tor gossiping), and 6 = k that is . The adaptivegossiping probability
/?;i=min was defined from (3.18), where n is the actual number of
neighbors in 7T
For flooding: The cumulative distribution function (cdf) of Â£ with conditional
probability of Â£
p(
( \ > nx~ II ( \ x~
(3.32)
The distribution of Â£ is the expectation of P(Â£ < x/7), expressed as
P(Â£
( \
>
X~
(3.33)
For adaptivegossiping: The conditional cdf of Â£ given Â£ nodes picked for
transmission is
P(C
x~
(3.34)
65
The conditional expectation of C, given Â£ nodes picked for transmission for given
n neighbors is
P(C
(
X~
V
(X")f
y
(3.35)
Then, the conditional distribution of Binomial with parameters n and pn is
expressed as
V
P(Â£
Y
n
=Z
A0
('i(JV))2
n I k /1 \n~li
kMp)
(3.36)
where pn = min
f log(N)
\
,1 .
If n is large, by using the Poisson distribution with parameter ( A = npn )
Â£ ~ Poisson (npn), then
P(Â£
f \ ~> X s
ikwfj
= E
b'lot!
/;,(A'))
\
66
/ \
since npn = min (log (A),??)
min
= e
(log(A')./f)
1
(3.37)
(3.38)
Since forwarding nodes are in an area of 0 = n that is
, then
n ~ Poisson
%w);
2 A
N
V
(3.39)
According to equation (3.39), we have a condition about the expected number of
neighbors log( N) that should be less than the actual number of neighbors n such
that n > log(TV), which is expressed as
E(n)
1 2
2 A
N > log(A).
(3.40)
Hence, the conditional distribution of Poisson is expressed as
/>(fÂ£jr) = Â£[>(f <*!)]
67
LMv)Ji
= I
*= o
f
k
iog(,v;
71
e
(3.41)
k\
K
fe(AO)
2 "\
N
 x(rg(X)) log(.V)
2 A
+ e
[('k^r
Next, the distance of a point to its farthest point x is defined by the probability
density function f(x) of the farthest distance of P(Â£ x) for .v > 0 as
Llog(.V)Jl
n*)= I
A=0
2 xk
(r,m)
T
2j[log(A') j
(r'Wf
log(A')
=1
A'!
i
2 ~\
N
2 A
+
2vlog( .V)
log(A')
e
TTI
(r,(.v>r
2x log (yv)
(r,(iV))2 ^
log(,V)
(3.42)
2 A
To estimate the expected perhop progress, we assume that the angle, denoted by to
is uniform on [0,;r/2], between the line connecting the node to its next hop
(
connecting the source node and the destination node is uniformly distributed
between /r/2 and /r/2, where d = n. Thus, the expected progress E(C) is (and let
rg(N) = r for the limited space)
E( C) =
l /2 i) ^ ( A ) A C0S 03 d* ^0)
7T
68
.rcosft*
I
2xk
2.vlog(/V) 1
 e
1 f 1 nr\
2 A
N e
is 2.vlog(/V) l'*V
i h e
n
2.vlog(.V) "OM Lis
>e e l I
2 sin f 2a:A ..*(?') 2.v: log(yv) d.x f 1 M^ N k 1 nr; ,, e A
{ 2 )x h ^ J A! [24 j
r 2.v: log (TV) is('v)(A1) ; e v J dx r.2Vlog()
J,
^'f)j l
i"s(v) ;i
[Z loy (A)
\Kr e er
:/'(Vlog(/V)) 'Tx(~k rg erfi[4k)
2>g(A0
2jk
_1_
it!
2 A
J
er//(N/log(;V) j 1 nr; v 0 1 A ' 'Jjrrge ]oe{S) erfi^\og(N)^
* 2 Vlog(A) g 2N/log(A) v /_
(3.43)
(See Appendix C for equation 3.43).
The expected perhop progress of adaptivegossiping can be represented as
Ft (9,rg(N),A) = E(() because we only need to know the area 9, the minimum
transmission range r (N) and the node density k to compute the expected perhop
progress E((). For example, if Z7) (tt, 128,2 104) where 6 n, rg {N) = 128m with
TV = 100 nodes, A = lOO/l000x500m2 then the Â£(0 = 106/?;.
Figure 3.24 shows the results of the expected perhop progress for adaptive
gossiping. The comparison of the expected perhop progress with flooding and
adaptivegossiping routing algorithm within their critical transmission range is
shown in Figure 3.25.
69
160
Figure 3.24 The expected perhop progress of adaptivegossiping routing
algorithm in the critical transmission range (CTR).
E(C) = F( (&,rg(N),A) = Ft [n,rg(N),2 lCT4) from (3.43), where rg(N) is defined
from (3.25) with the total number of nodes N between 60 and 2000 in a simulation
area of size A = (I000x500)//?2.
70
Figure 3.25 Comparison of the expected perhop progress with flooding and
adaptivegossiping routing algorithm within their critical transmission range
(CTR). Ff (jV),2 10"4) for flooding and F, {x
gossiping from (3.30) and (3.43) respectively, where i)(N) and /;(Ar) are the
critical transmission range for flooding and adaptivegossiping defined from (3.24)
and (3.25) respectively. The total number of nodes N between 60 and 2000 are
randomly distributed in a simulation area of size A = (1000x500)/2.
71
3.4.3 Hop Count Between Random Source and Destination
To analyze the delay from a source to destination, we consider a hop count
between a random source and destination. This study adopted the probability>
density; function (jjdf) introduced by Bettstetter et al. in [43, 44] for the analysis of
the distance between random source and destination pairs by considering only the
distribution of the distance between two independent points placed randomly in the
network system area [44],
3.4.3.1 Distance Between Random Two Points in OneDimensional Case
First, we consider a onedimensional case in a line segment [0, a\. Two
random points are uniformly placed on this segment; hence the pdf of a points
location P = Px is
.ip, M =
a
0,
for 0 < x < a
otherwise
(3.44)
Since both points are independent from each other, their joint pdf is
JK K (F *2) = fPxi (F) JK} (X2 )
, for 0 < x,, x, < a
a'
0, otherwise
(3.45)
The distance between two random points is defined by L=Py. Py The
probability that this distance is smaller than a given value u can be computed by the
integral of the joint pdf over the area defined by D = x, ,y2  u in the x, x2
space as
P(L
(3.46)
72
For 0
where ,/P P (.v,, *2) = /P (.r,) ,/P (x2) = ~ . Clearly,
P(La Taking into account the bounds of both D and
/P P (a'j a*2 ), the cumulative distribution function (cdf) is
/ X 1 / C* f vl + piIt fV.+H
p(is,,)='7(n + { l..M*,
+
a2
=+T,
a
(3.47)
(See Appendix D for equation 3.47).
Hence, the derivative of this function with respect to u yields by definition the
desired pdf'
fL{u) = ^P{L
ou a a
for 0 < u < a and f\ (;/) = 0, otherwise. The expected distance is
E(L) = f uf, (u)du = a . (3.49)
3
(See Appendix E for equation 3.49).
3.4.3.2 Distance Between Random Two Points in TwoDimensional Case
Now we consider the selection of two random points in a rectangular area of
size axb for a >b. The spatial distribution of the twodimensional points p = (jix,
pv) is now given by the uniform distribution
frA{x,y)
ab
0,
for 0 < v < and 0 < r < b,
otherwise
(3.50)
73
The distance between two points Pt (p p ) c/nd /f = (px pv ) is
Note that the random variable Lx = P Pxx  represents the random distance
between two uniformly distributed coordinates P and Px on a onedimensional
line segment [0, ]. Thus, its pdf is given by (3.48). The same holds for
Ly = P  if we replace a by b. In addition, both random distances are
independent of each other, and therefore the joint pdf of Z^and Lv is given by
for 0
Hence, we can derive the cdf P{L< it) by integration of flt (uxjiy) over the
circular area D = u2x + u2y < u in the ux ay space, such that
To solve these integrals for the righthand side of equations (3.52) and (3.53), this
study adopted the result of the probability distribution of the distance between two
random points derived by Ghosh in [45] and proved by Bisnik, et al. [46], which is
the equivalent result from Bettstetter and Eberspacher [44] of the pdf of the
transition length L of nodes moving according to the random waypoint mobility
model in a rectangular area of size axb,a>b and is
fLJ.(llxdly) = fl(llx)fI(lly)
a'b
(3.52)
(3.53)
./i() = 77T0(),
air
(3.54)
where
74
for 0
abaubu+ u2,
2 ?
a^sin '
ab
ru\
\uj
+ a(z/2 b2 )2 au b2, for b
+ a(ii' b2}2 +b(u2 a2(z/2 +a2 + 62),
1
sin cos 
l U)
for a < u < \la2 +b2
The expected value of L is then computed for a > b as
E(L) = 
6
b2
cosh
i
( \_\
(a2+b2r
b
+cosh'
b
( _2
a +b
2
1 f 3 a b^ (a2 +b2)2 (2 ; 2 X a b .
H H r  + 3
15 a'J 15 {b a )
(3.55)
For example, the expected length within a square of size a x a is E(L) = 0.5214a,
and a rectangle of size of a x {all) yields E{L) = 0.402a [44],
Therefore, the expected number of hops between a random source and destination
pair, denoted by H is
E(H)
E(L)
E(t)
(3 56)
where Â£V)is the expected perhop progress by equation (3.30) and (3.43) for
Hooding and adaptivegossiping respectively. For example of flooding, E{C) = 48m
'y
with 100 nodes in the network size of A=a*b (=1000x500)/;?" from the example of
equation (3.37), hence the E{H) = 0.402a/48 = (0.402x 1000)/48 = 8 hop counts
between random source and destination pairs. For adaptivegossiping, E{()= 106m
from the example of equation (3.56), hence the E(H) = (0.402x 1000)/106 = 3 hop
75
counts between random source and destination pairs, which is much less hop counts
than flooding routing algorithm (see Figure 3.26).
N = Totol number of ikkW>
Figure 3.26 The expected number of hops between a random source and destination
pair. The analysis results are compared with flooding and adaptivegossiping in a
given network size of (1000x500)/' according to equation (3.56).
76
3.5 Analysis of Delay
The link available time is defined as the time during which a wireless link between
two mobile nodes will be active as long as they are within the transmission range of
each other. In an ad hoc wireless network, link availability is extended to path
availability [74], which means a packet is routed by a multihop path that is
available in the link duration. The link available time, denoted by T, is
where 8(9) is the distance that the farthest node (C, =.v) as a relay node need to
travel to move out of the transmission range of its neighbor, and \\ is the relative
velocity between the two neighbor nodes. In order to define the probability
distribution of link available time, the distributions of v, and 8(9) should be
measured.
First, we analyze the relative velocity that is a random vector with two random
variables of the direction 6 and the speed v; their absolute values as \d\ = d and
H = v are uniformly distributed between 0 and 2n and range from 0 to vmax
respectively. vi and v2 represent the velocity vector of two neighbor nodes as >h
and respectively, and their distance is smaller than i)(N) in the defined two
dimensional network region from (3.24). The relative velocity v, between nodes
n i and >h. is given according to the law of cosines as
For the simulation scenario, we also assume that the velocity vectors vi and v2 have
the same constant speed as v,liax and the relative velocity can be as large as
2vmax when two nodes move oppositely, such that
8(6)
(3.57)
(3.58)
v, = v, = v
(3.59)
77
Hence, v, can be expressed as
vr = vyj 22 cos 0 = 2vsin
F2vsin
(e'
\2)2 n
de
In
rlit
J 2vsin
k2j
(3.60)
(3.61)
(3.62)
Second, let us consider the distance S(0) in a onehop link between two neighbor
nodes 11 \ and }h Node is assumed to be a relay node of n\ and the initial
distance between them is E(C) from (3.30) in the critical transmission range f) (N)
for E(() < r, (AO. At the viewpoint of n\ node }h moves out of the range (AO at
a relative velocity v, when l1\ remains static, after a given time (see Figure 3.27).
The distance &{0) is given according to the law of cosines as
S{0) = ^j(rl(N)fE(Â£)2 shr(0)E(Â£)cos(0) (3.63)
*(*(*))rf>/(r' (Ar))2 ~E^2sin2 (0) 
de (3.64)
(See Appendix G for equation 3.64). Since,
r =
m
m
2vsin
(0>
v2y
(3.65)
Thus, we can obtain the expected link available time from (3.64) and (3.65), given
by
78
(3.66)
(3.67)
Therefore, the average endtoend delay between a source and destination should
be less than the expected link available time E(T); otherwise, an active link might
be disconnected and reconnected with a new route established, which means
packet delay will be increasing.
E{D) = E
IA
> = 1
(3.68)
Figure 3.27 Link available time. It impacts the average endtoend delay between
random source and destination. Where E(C) is the distance between two neighbor
nodes h, and /z,, and ( is the distance node /z, traveled to move at a relative
velocity v(. out of its neighbor h()s transmission range rt (N).
79
The expected link available time can be represented as
Fr[vimx,rf(N),E(Â£)^ = E(T) for flooding, because we only need to know the
maximum required velocity vinax, the critical transmission range r (N), and the
expected perhop progress E(C) that is the distance between two neighbors. For
adaptivegossiping, it can be represented as F1 (v,imN,r?(A0,Â£(^)) = Â£'(7') For
example of flooding case, if it is known that Fr(20ni/s,&6m,4$m) with jV = 100
nodes in the (1000><500)/fo network area, where vmax = 20mA ,/, (N) = 86/// and
Â£(0 = 48//; thus Â£(Â£) = 3 seconds. For example of adaptivegossiping case, if it
is know that F, (20mA, 118///, 62///) where vmax = 20/n/s rg(N) = 118/// and
Â£(0 = 62///, thus E(T) = 4 seconds (see Figure 3.28).
80
Figure 3.28 The expected link available time: The analysis results are compared
with Â£(7) = F/.(vnnx,/y(A0,Â£'(^))and E(T) = Fr(vm!X,rg(N),E(Â£)) for flooding and
adaptivegossiping respectively, where each node has the same velocity of
vmax = 20 mA with the total number of nodes jV between 60 and 2000 in a simulation
area of size A = (1000x500)m2 according to equation (3.67).
81
3.6 Performance Evaluation
3.6.1 Analytical Results of Energy Consumption
According to the energy analysis in Subsection 2.3.2.2, we present an
analysis of the energy consumption of three broadcast mechanisms: flooding from
(2.11), staticgossiping from (2.14) and our adaptivegossiping that was improved
by our new analytical model with adaptivegossiping probability pn from (3.18).
Thus the energy analysis of adaptivegossiping algorithm is shown as the following
details:
AdaptiveGossiping: When each node receives a requested packet, it broadcasts the
packet to its neighbors with probability p = (\ln)\og{N) where n is its neighbor
nodes, and discards the request packet with probability 1 p.
1 vV
VFA/71 _ V1 ^
1 adaptivegossiping ~ Zui=[
REVD.
.
adaptivegossiping
N) f yV/ Pn OAi) =Pn (3.69)
1 J
\
Pn 0 Pn = "Pn (3.70)
The average ENG is given by
ENG
radaptivegossiping
\ * n
N
(3.71)
(3.72)
In numerical analysis, we have that the number of neighbors is n = Atr(r0(N))2 from
(2.5). Assume that the transmission range r0(N) is fixed with 200/h and the constant
of Pw 1. For the staticgossiping, we apply a heuristic gossiping probability value
with p= 0.65 that was defined by Hass et al. [14]. The results of energy analysis for
a comparison of three different broadcast mechanisms are presented in Figure 3.29.
Adaptivegossiping has less energy consumption, about 98% and 97% than flooding
and staticgossiping respectively, at 7V=2000 nodes as a largescale network. Power
consumed is dependent on the number of activate nodes, such that the node degree
82
Average energy consumption
grows logarithmically in N as 0(log(N)/n) for adaptivegossiping; however, with
both flooding and staticgossiping, the node degree n is grown linearly as O(n) and
O(np) for flooding and staticgossiping, respectively. Therefore, our adaptive
gossiping routing algorithm with probability pn consumes significantly less energy
compared with the other two methods.
(a) Total number of nodes (N) (b) Total number of nodes (N)
Figure 3.29 In (a) shows a comparison of the energy consumption of three
broadcast mechanisms: flooding as probability 1; staticgossiping with probability
p=0.65; and adaptivegossiping with probability p=(l/n)log(./V). In (b) shows the
results for only adaptivegossiping from (a). The total number of nodes N between
50 and 2000 in a simulation area of size ,4=(1000* 500)m~.
3.6.2 Simulation Results
To prove that the adaptivegossiping based routing protocol (AGSP)
outperforms the other two routing protocols, flooding and staticgossiping, we
simulated these routing protocols using the ns2.32 network simulator [23] over
IEEE 802.1 lb channel [52],
For performance evaluations, our two means of performance metrics, Delay x
Energy (DE) and Normalized Routing Load x Energy' (NRLE) are used from (2.19)
and (2.20) respectively.
83
Throughput (%) Average endtoend delay (s)
(a) Average endtoend delay (s) (b) Packet loss fraction (PLF) (%)
(c) Throughput (%) (b) Average node used energy (mW)
Figure 3.30 The simulation results of ad hoc routing protocols based on three
different broadcast mechanisms: flooding as probability 1, staticgossiping with
probability p=0.65 and adaptivegossiping with probability p=( \/n)\og(N).
84
(e) Delay x Energy (f) NRL x Energy
x 10
N = Total umnber of nodes
(g) The number of data packets (h) The number of routing control packets
Figure 3.31 The simulation results of ad hoc routing protocols based on three
different broadcast mechanisms: flooding as probability 1, staticgossiping with
probabilityp=0.65 and adaptivegossiping with probabilityp={\!n)\og(N).
85
