# Constrained Delaunay Triangulation for Ad Hoc Networks

Authors: D. Satyanarayana; S. V. Rao
Journal: Journal of Computer Systems, Networks, and Communications
 (2008)

---

## Abstract

Geometric spanners can be used for efficient routing
in wireless ad hoc networks. Computation of existing spanners
for ad hoc networks primarily focused on geometric properties
without considering network requirements. In this paper, we
propose a new spanner called constrained Delaunay triangulation
(CDT) which considers both geometric properties and network
requirements. The CDT is formed by introducing a small set
of constraint edges into local Delaunay triangulation (LDel)
to reduce the number of hops between nodes in the network
graph. We have simulated the CDT using network simulator (ns-2.28) and
compared with Gabriel graph (GG), relative neighborhood graph
(RNG), local Delaunay triangulation (LDel), and planarized local
Delaunay triangulation (PLDel). The simulation results show that
the minimum number of hops from source to destination is less
than other spanners. We also observed the decrease in delay,
jitter, and improvement in throughput.


---

## Body

## 1. Introduction

An ad hoc network is a collection of wireless nodes
with no fixed infrastructure. In wireless ad hoc networks, routing is one of
the important challenging tasks because of its distributed nature, mobility,
limited transmission range, shared communication media, and limited node
capabilities. Many researchers proposed various network topologies for
efficient routing. These topologies are used to route the packets from source
to destination. These network topologies can be broadly divided into three
categories: flat, hierarchical, and hybrid network structures. The flat network
graphs form connected graph with all nodes in the network, for example, minimum
spanning tree (MST), nearest neighbor graph (NNG), relative neighborhood graph
(RNG), Gabriel graph (GG), Yao graph (Yao), and Delaunay triangulation (Del)
[1–3]. In the hierarchical
structures, only some subset of nodes is existed in the network graph based on
the hierarchies created by the network. Mainly, hierarchical structures are
based on dominating set, connected dominating set, and d-dominating set
[4–8]. On the other hand, hybrid
structures [9, 10] combine both hierarchical structures and flat
structures, and the graph contains the subset of nodes of the original network
graph.Another type of network graph is unit disk graph (UDG)
[11] which can be
defined as follows. Assume each node has the same and fixed transmission range
of one unit, then there exists an edge between two nodes u and v if and only if
their Euclidean distance ∥uv∥ is not more
than one unit. The number of edges in UDG is in O(n2), where n is the number
of nodes. The communication cost in this graph is high due to the large number
of edges.To reduce the communication cost over UDG, many
researchers derived various connected geometric subgraphs of UDG, called
spanner, with linear number of edges. The formal definition of spanners are as
follows. A spanning subgraphG1 is a t-spanner of a
graph G if and only if
the number of vertices in graph G1 is equivalent
to the number of vertices in graph G, and the length of the shortest path connecting any
two vertices in graph G1 is bounded by a
value t to the length
of the shortest path connecting the same vertices in the graph G. In other words, a graph G1 is a t-spanner of
graph G if V(G1)=V(G) and ∀u,v∈V(G), ∥πG1(u,v)∥≤t∥πG(u,v)∥, where V(G) is the vertex
set of graph G and ∥πG(u,v)∥ is the length
of the shortest path between two vertices u and v in the graph G.Computation of any geometric spanner requires position
of nodes. So, each node knows its position using some positioning techniques
such as global positioning system (GPS). Some of the important spanners are GG
[2], RNG [2], Del [12], Yao [3, 13], and variations of Delaunay
triangulation [1, 9, 10, 14–17].These spanners are used as underlying network graph by
various position-based routing protocols like greedy perimeter stateless
routing (GPSR) [18],
FACE routing [19],
adaptive FACE routing (AFR) [20], greedy FACE greedy (GFG) routing [19], GOAFR+ [21], and Bose's localized
routing protocols [22].


### 1.1. Survey

Recently, many researchers have shown interest in
geometric spanners because of its wide range of applications. Some of the
spanners often used in wireless networks are briefly discussed below.The edgeuv¯ exists between
two nodes u and v in GG if there
is no node w inside the
circle with uv as the diameter
as shown in Figure 1. In other words, the edge uv¯∈E if and only if
the circle centered at (u+v)/2 with the radius d(u,v)/2 does not
contain any other node inside, where d(u,v) denotes
distance between u and v. Bose et al. have
given a localized algorithm [19] to construct GG for ad hoc networks. The spanning ratio
of GG is bounded by O(n) [2, 23].Figure 1
Rules of GG,
RNG, and Yao graphs.Two nodesu,v∈V are connected
in RNG if and only if their lune Lu,v does not
contain any other node w∈V. The lune Lu,v is defined as
the intersection of the two circles of radius d(u,v) centered at p and q, respectively, see Figure 1. The algorithm to
construct RNG for wireless
networks is given in [18]. Bose et al. [2] have proved that the spanning
ratio of RNG is in O(n). RNG is a subgraph of GG.In Yao graph [3, 13], the transmission range circle of a node u is divided into k equal sectors,
where k≥6, as shown in Figure 1. In each sector, closest node
is connected with u by an edge if
exists. Ties are broken arbitrarily. The spanning ratio of Yao graph is bounded
by a constant. Unlike GG and RNG, Yao graph is not a planar graph.We can define Delaunay triangulation (Del) [12] of V as the
triangulation of all the nodes such that the circumcircle of each triangle
should not contain any other node x∈V, see Figure 2. Delaunay triangulation is a planar
graph. The spanning ratio of Del is 2.42 [24, 25]. Hence, it is a t-spanner of
UDG. RNG and GG are subgraphs of Del, but still it maintains linear number of
edges in the graph. Del is not suitable for ad hoc networks because it contains
longer edges than the transmission range. The unit Delaunay triangulation UDel
[15] can be obtained
from the Delaunay triangulation Del by removing all the edges longer than one unit.
UDel is a t-spanner of UDG
[9, 15].Figure 2
Rules of Del
and LDel.Though the unit Delaunay triangulation (UDel) is suitable
for ad hoc networks, it is not known how to construct UDel locally. Li et
al. [1] gave a
localized algorithm to construct Delaunay triangulation for ad hoc networks
called localized Delaunay triangulation (LDel). In LDe1, as shown in Figure 2, the
circumcircle of each triangle ▵u,v,w does not contain
any other node x such that x∈n1(u), x∈n1(v), and x∈n1(w) where n1(u) denotes the set
of 1-hop neighbors for node u. In this
algorithm, first it constructs LDel1 with one hop neighbors. LDel1 is a t-spanner of UDG
[15], but LDel1 is not a planar graph. A
planarization algorithm is applied on LDel1 to make it a planar graph, and
it is called planarized local Delaunay triangulation (PLDel) or simply localized Delaunay triangulation (LDel).
LDel is a planar 2.5-spanner of UDG
[1, 15]. It contains all the edges
that are in the both UDG and Del.Gao et al. [9, 14] proposed a spanner called restricted Delaunay graph
(RDG) which combines the node clustering algorithm with Delaunay triangulation
graph. Alzoubi et al. [10, 17] proposed another spanner which first constructs the
backbone using clustering algorithm followed by the Delaunay triangulation.LDel contains many desirable geometric properties
which are suitable for wireless ad hoc networks, but at the same time some of
the problems in LDel motivated us to propose a new spanner called constrained
Delaunay triangulation (CDT). The problems include high hop count between the
nodes and large packet delays.Some times, in LDel, packet traversal may take more
than one hop even though the nodes are in the communication range of each
other. This can happen due to the geometric property of LDel. For example,
consider the LDel shown in Figure3(a), the
outer circle indicates the transmission range of node a. Nodes b,c,d, and e are neighbor
nodes of a. Even though the node d is in the
transmission range of node a, the packet traversal from node a to node d takes more than
one hop. Thus, the edge ad¯ cannot be
placed in the LDel. The same thing can happen to other spanners also. For
example, Gabriel graph (see Figure 3(b)) does not
include the edge ac¯ in the graph
due to its property. In this paper, we propose a new spanner called constrained
Delaunay triangulation (CDT) by introducing longer edges to reduce the number
of hops and packet delay between the nodes. We call these longer edges as constraints
of localized Delaunay triangulation (LDel). The main objectives of the
constrained Delaunay triangulation are (1) reducing the
number of hops between the nodes in LDel and (2) reducing the
end-to-end packet delay. We have simulated CDT in ns-2.28 and compared
with PLDel, LDel1, GG, and RNG using various
greedy routing protocols. The simulation results show that CDT give better
performance in terms of number of hops, packet delay, jitter, and
throughput.More hops in LDel and GG.
(a)(b)Figure 4
Constraint
edges selection.Constraint
edgeaf¯ is added to
PLDel.
(a)(b)Figure 6
Non-Delaunay triangles▵abd, ▵adf, ▵ace, and ▵aef are created
in CDT.The remaining part of this paper is arranged as
fallows. In Section2, we define constrained Delaunay triangulation followed by
the algorithm to construct CDT. Section 3 presents the results of ns2
[26] simulation. We
conclude the paper with the future research direction in Section 4.


## 1.1. Survey

Recently, many researchers have shown interest in
geometric spanners because of its wide range of applications. Some of the
spanners often used in wireless networks are briefly discussed below.The edgeuv¯ exists between
two nodes u and v in GG if there
is no node w inside the
circle with uv as the diameter
as shown in Figure 1. In other words, the edge uv¯∈E if and only if
the circle centered at (u+v)/2 with the radius d(u,v)/2 does not
contain any other node inside, where d(u,v) denotes
distance between u and v. Bose et al. have
given a localized algorithm [19] to construct GG for ad hoc networks. The spanning ratio
of GG is bounded by O(n) [2, 23].Figure 1
Rules of GG,
RNG, and Yao graphs.Two nodesu,v∈V are connected
in RNG if and only if their lune Lu,v does not
contain any other node w∈V. The lune Lu,v is defined as
the intersection of the two circles of radius d(u,v) centered at p and q, respectively, see Figure 1. The algorithm to
construct RNG for wireless
networks is given in [18]. Bose et al. [2] have proved that the spanning
ratio of RNG is in O(n). RNG is a subgraph of GG.In Yao graph [3, 13], the transmission range circle of a node u is divided into k equal sectors,
where k≥6, as shown in Figure 1. In each sector, closest node
is connected with u by an edge if
exists. Ties are broken arbitrarily. The spanning ratio of Yao graph is bounded
by a constant. Unlike GG and RNG, Yao graph is not a planar graph.We can define Delaunay triangulation (Del) [12] of V as the
triangulation of all the nodes such that the circumcircle of each triangle
should not contain any other node x∈V, see Figure 2. Delaunay triangulation is a planar
graph. The spanning ratio of Del is 2.42 [24, 25]. Hence, it is a t-spanner of
UDG. RNG and GG are subgraphs of Del, but still it maintains linear number of
edges in the graph. Del is not suitable for ad hoc networks because it contains
longer edges than the transmission range. The unit Delaunay triangulation UDel
[15] can be obtained
from the Delaunay triangulation Del by removing all the edges longer than one unit.
UDel is a t-spanner of UDG
[9, 15].Figure 2
Rules of Del
and LDel.Though the unit Delaunay triangulation (UDel) is suitable
for ad hoc networks, it is not known how to construct UDel locally. Li et
al. [1] gave a
localized algorithm to construct Delaunay triangulation for ad hoc networks
called localized Delaunay triangulation (LDel). In LDe1, as shown in Figure 2, the
circumcircle of each triangle ▵u,v,w does not contain
any other node x such that x∈n1(u), x∈n1(v), and x∈n1(w) where n1(u) denotes the set
of 1-hop neighbors for node u. In this
algorithm, first it constructs LDel1 with one hop neighbors. LDel1 is a t-spanner of UDG
[15], but LDel1 is not a planar graph. A
planarization algorithm is applied on LDel1 to make it a planar graph, and
it is called planarized local Delaunay triangulation (PLDel) or simply localized Delaunay triangulation (LDel).
LDel is a planar 2.5-spanner of UDG
[1, 15]. It contains all the edges
that are in the both UDG and Del.Gao et al. [9, 14] proposed a spanner called restricted Delaunay graph
(RDG) which combines the node clustering algorithm with Delaunay triangulation
graph. Alzoubi et al. [10, 17] proposed another spanner which first constructs the
backbone using clustering algorithm followed by the Delaunay triangulation.LDel contains many desirable geometric properties
which are suitable for wireless ad hoc networks, but at the same time some of
the problems in LDel motivated us to propose a new spanner called constrained
Delaunay triangulation (CDT). The problems include high hop count between the
nodes and large packet delays.Some times, in LDel, packet traversal may take more
than one hop even though the nodes are in the communication range of each
other. This can happen due to the geometric property of LDel. For example,
consider the LDel shown in Figure3(a), the
outer circle indicates the transmission range of node a. Nodes b,c,d, and e are neighbor
nodes of a. Even though the node d is in the
transmission range of node a, the packet traversal from node a to node d takes more than
one hop. Thus, the edge ad¯ cannot be
placed in the LDel. The same thing can happen to other spanners also. For
example, Gabriel graph (see Figure 3(b)) does not
include the edge ac¯ in the graph
due to its property. In this paper, we propose a new spanner called constrained
Delaunay triangulation (CDT) by introducing longer edges to reduce the number
of hops and packet delay between the nodes. We call these longer edges as constraints
of localized Delaunay triangulation (LDel). The main objectives of the
constrained Delaunay triangulation are (1) reducing the
number of hops between the nodes in LDel and (2) reducing the
end-to-end packet delay. We have simulated CDT in ns-2.28 and compared
with PLDel, LDel1, GG, and RNG using various
greedy routing protocols. The simulation results show that CDT give better
performance in terms of number of hops, packet delay, jitter, and
throughput.More hops in LDel and GG.
(a)(b)Figure 4
Constraint
edges selection.Constraint
edgeaf¯ is added to
PLDel.
(a)(b)Figure 6
Non-Delaunay triangles▵abd, ▵adf, ▵ace, and ▵aef are created
in CDT.The remaining part of this paper is arranged as
fallows. In Section2, we define constrained Delaunay triangulation followed by
the algorithm to construct CDT. Section 3 presents the results of ns2
[26] simulation. We
conclude the paper with the future research direction in Section 4.


## 2. Constrained Delaunay Triangulation (CDT)

Localized Delaunay triangulation (LDel) [1, 15] is popular because of its
useful geometric properties and utility in wireless networks. In LDel, even
though two nodes exist in the communication range
of each other, they do not have a direct edge
between the nodes because of the geometric properties. The same things happen
in other geometric graphs such as GG and RNG. This leads to longer path from
source to destination, hence more number of transmissions and high latency. We
are motivated by this problem and proposed CDT which reduces the number of
transmissions and latency.If we have an edge between the nodesa and d in Figure 3(a)
or a and c in Figure
3(b), it reduces the number of hops between the nodes and in turn leads to
many other benefits such as reduction in the delay, jitter, and energy consumption;
but, these type of edges violate the geometric
properties of the spanner. So, in order to improve the various network
parameters, we introduce the so-called constraint edges into the network graph,
but most of other edges satisfy the Delaunay property. This gives us
improvement in network parameters and at the same time satisfying various
geometric properties.Constrained Delaunay triangulation is well-studied
problem in the area of computational geometry. Chew proposed a divide-and-conquer
algorithm for CDT [27].
This algorithm is not suitable for wireless ad hoc networks because it is a
centralized algorithm. In this section, we give a localized algorithm to construct
CDT for wireless networks.Constrained Delaunay triangulation is a triangulation
of the given set of nodesV with the
following properties: (1) CDT is a subgraph of UDG; (2) constraint edges exist
at two hop away; (3) CDT is a planar graph; (4) the total number of edges in
CDT is in O(n); and (5) CDT is a spanner of UDG.The algorithm to construct CDT is a localized
algorithm, that is, it uses only the constant number of neighborhood hop
information. In this algorithm, we assume that each node is static and knows
its location information. We can broadly divide the CDT algorithm into three
parts. First, we construct the planarized local Delaunay triangulation (PLDel)
[1, 15] with one hop neighborhood
information. For the sake of completeness, we briefly describe the algorithm.
Each node u computes
Delaunay triangles Del(u) with its 1-hop
neighbors. The Gabriel edges are computed from Delaunay triangles which will
never be deleted from local Delaunay triangulation (LDel). Remove all the
inconsistent triangles. A triangle ▵abc is called
consistent if the nodes a, b, and c contain the
triangle ▵abc. The resulting graph is called LDel1 which is not planar graph. A
separate planarization algorithm is applied on LDel1 to induce a planarized local
Delaunay triangulation (PLDel).In the second part of CDT algorithm, we find BLACK
nodes which are at least two-hop apart. These Black
nodes place nonintersecting constraint edges on top of PLDel and mark the other
side of the constraint edge to BROWN. The resulting graph is not planar graph.
The third part planarizes this graph and forms new triangles with the
constraint edges. The resulting graph is called constrained Delaunay
triangulation (CDT). Please note that the new edges added
belong to UDG. Formally, the algorithm is described
as shown in Algorithm1.Algorithm 1
Algorithm for CDT(1)  Construct PLDel, set color of each node to WHITE,and broadcast all its 1-hop neighbor informationusing the packet Neighbor_Packet.(2)  Nodes having lowestid among its 2-hop neighbors settheir color to BLACK.(3)  Each BLACK node chooses a setN of nodes from its1-hop neighbors using the followingmethod, see Figure 4.(a) N = empty(b) n1 = farthest
neighbor(c) N = N∪n1(d) for i=2,3,…{ni = choose ith farthest
neighborif ni makes more than 60∘ angle withn1,n2,…,ni−1then N = N∪ni}(4)  Each BLACK node adds the constraint edges to thenodes in N and broadcasts these constraint edgesinformation using the message Constraint_Packet.(5)  Each WHITE node sets itscolor = BROWN if it isother end of any constrained edges received usingConstraint_Packet.(6)  Each BROWN node broadcasts its constraint edge informationusing the control packet Constraint_Packet.(7)  All WHITE and BROWN nodes remove edges connec-ted to it which crosses constraint edges, see
Figure 5(b).This information is broadcasted using
Edgecross_Packet.(8)  Each BLACK node places a new edge from the
WHITEnodes, from which the edge was deleted in
the previousstep to form new triangles, see Figure 6.Constrained Delaunay triangulation can be maintained
efficiently in a distributed fashion. CDT has nice theoretical guarantees. The simulation results show that the
performance of CDT is better than PLDel, GG, and RNG.Theorem 1.
The expected number of BLACK nodes in
any2-hop disk is in O(1).Theorem 2.
The expected total number of BLACK and
BROWN nodes in a unit disk is inO(1).Proof.
From the definition of BROWN node, for each
BLACK node, the other side of each constraint edge is a
BROWN node. Since the maximum number of constraint
edges for each BLACK node is 5, the total number of BROWN nodes for a single BLACK node is inO(1). We know that the total number of BLACK nodes
in unit disk is in O(1), from Theorem 1. Thus, the total
number of BROWN nodes in unit disk is in O(1). Hence,
the total number of BLACK and BROWN nodes are in O(1).From theoretical point of view, the constraint edges in
CDT do not affect the link quality, as the definition of UDG
says that every node in its vicinity receives the transmitted
packet [1, 9–11, 14, 15, 16, 17]. On the
other hand, the quality of signal strength decreases with
the increase in distance to the receiving node [28–30]. In this case, the constraint edges may affect the link
quality, as the constraint edges are considerably long. In
addition to the distance, link quality also depends on walls,
buildings, mountains, and weather conditions, which might
obstruct signal propagation. We can use the following
models for link quality [31, 32]. In our proposed method,
we can consider distance parameter for link quality, while
selecting the constrained edges. In other words, consider
the link quality as a parameter for choosing the constraint
edges.In the remaining part of the section, we analyze the communication
cost in terms of the number of transmissions.
In addition to the messages of planarized local Delaunay
triangulation [1, 15], CDT uses the following control messages:(1)
neighbor_packet. This packet is used to broadcast the
1-hop neighborhood information;(2)
constraint_packet. This packet is used to broadcast
the constraint edge information;(3)
edgecross_packet. This packet is used to broadcast
the edgecross information.The messageneighbor_packet is broadcasted at most once by each node in the network graph. So, the communication
cost for this message is in O(n) bits, where n is the total number of nodes. Only BLACK and BROWN
nodes use the message constraint_packet. Each BLACK and
BROWN nodes broadcast the message constraint_packet at
most once. The communication complexity for the message
constraint_packet is in O(n). The message edgecross_packet
is used by only WHITE and BROWN nodes. Each WHITE
and BROWN node uses edgecross_packet at most once in
CDT. So, the message complexity for this packet is in O(n) bits. Hence follows the theorems.Theorem 3.
The communication cost of constructing
CDT from PLDel is inO(n).Theorem 4.
The communication complexity to construct
CDT is inO(nlogn).Proof.
We know that the message complexity
for constructing PLDel is inO(nlogn) [1]. The total number of
message exchanges by CDT, excluding PLDel, is in O(n). Thus, the total communication cost of constructing
the CDT is in O(nlogn). Hence, Theorem 4 the  is
proved.


## 3. Simulation and Performance

In order to evaluate the performance of the proposed
spanner, we have done various experimental work using networks simulator
(nanoseconds 2.28). We have simulated GG, RNG, LDel1, and PLDel, and compared with
our CDT spanner. The
following routing protocols are simulated to run on these spanners.(1)
Greedy
routing (Grdy). As shown in Figure 7(a), let the node b be the destination
node, then the current node a selects a node c as the next
relay node in its transmission range such that the distance ∥cb¯∥ is the smallest
among its neighbors. Here, the circle with the center at a represents the
transmission range of node a. Please note that if there exists a node in the
shaded area, then the node c cannot be next
relay node.(2)
Compass
routing (Cmp). Assume that the node b is the
destination node. The current node a sends packet to
the next relay node c which makes the
smallest angle, that is, ∠cab is the smallest
among all a's neighbors,
see Figure 7(b).(3)
Random
compass routing (RandCmp). It is similar to the compass routing. As shown
in Figure 7(c), let a and b be the current and
destination nodes, respectively. We compute the two nodes c and d, above and below the line ab¯, respectively.
Here, the angle ∠cab and ∠dab are the minimum
angles above and below the line ab, respectively, among a's neighbors.
The current node a sends packet to
the destination node, by randomly selecting, either node c or node d as the next
relay node.(4)
Most forward
routing (MFR). That is shown in Figure 7(d), the current node a selects the
next relay node c to transmit the
packet to the destination node b such that the
distance ∥db¯∥ is the smallest
among a's neighbors.(5)
Nearest
neighbor routing (NN). Let a and b be the current
and destination nodes, respectively, as shown in Figure 7(e). For a particular
angle α, node a selects the
next relay node c such that ∠cab≤α, and c is the nearest
neighbor of a.(6)
Farthest
neighbor routing (FN). In this routing protocol, for the given angle α, as shown in Figure 7(f), the current node a selects the
next relay node c such that ∠cab≤α, and c is the farthest
neighbor of node a. Here, b is the
destination node.Greedy routing algorithms.The greedy routing, compass routing, and random
compass routing provide guarantee delivery of packets if the underlying network
topology is a Delaunay triangulation [18, 19].


### 3.1. Performance Metrics

In this paper, we have considered the following
metrics to evaluate the performance of different spanners.(1)
Hop count. This metric
represents the total number of hops traveled by a
data packet from source to destination on the underlying network graph.(2)
Delivery ratio. The delivery ratio (DR) is the ratio
of the total number of packets received successfully to the total packets sent
by the source.(3)
Delay. Delay metric is the total time
spent by a packet during the data transmission from source to destination.(4)
Standard delay. Standard delay is the
standard deviation in the delay of a packet from source to destination. The
following mathematical formula is used to calculate the standard delay (Sd):
(1)Sd=1m×∑i=1m(ai−a¯),
whereai denotes delay
of ith packet, a¯ is average
delay, and m is total number
of packets.(5)
Throughput. Throughput is the total number
of packets transmitted per unit time from source to destination.In the simulation results, we have presented average,
minimum, and maximum of the above metrics.


### 3.2. Simulation Model and Results

Important parameters of the simulation are shown in
Table1. All experiments are conducted on ten different node scenarios. For
each scenario, we have considered ten different connection patterns, by
randomly choosing source nodes at one side and destination nodes at the other
side. In our simulation model, we do not consider the link quality, as we
assumed that the channel is error free.Table 1
Simulation parameters.
Grid size200×200m2Number
of nodes100Transmission
range40 mPropagation
modelTwoRay GroundMAC
layer typeIEEE 802.11CBR
packet size512 bytesSimulation
run time350 secAntennaOmniAntennaAntenna
height1.5 mMax
packet in ifq100Frequency914e+6 HzSystem
loss factor1.0Recv
power threshold3.652e-10 wCarrier
sense threshold1.559e-11Capture
threshold10.0 dbInitial
energy300 JThe first experiment is on delivery ratio. The average
delivery ratio of ten different scenarios with six different routing protocols
is shown in Table2. The delivery ratio of CDT is better than RNG and GG
because CDT is denser graph than RNG and GG. There is not much difference among
CDT, PLDel, and LDel1 because many edges are common
among them.Table 2
Delivery ratios.
RNGGGLDelPLDelCDTNN40.977.899.999.998.4FN43.578.192.891.995.4MFR73.786.999.899.899.8Compass90.097.899.999.999.9RandComp90.097.999.999.999.9Greedy72.893.9100100100In the second experiment, we have computed the minimum
hop count between source and destination on different network topologies. The
source node sends the packet to the destination greedily on five different
network topologies. The average hop count at different CBR intervals are shown
in Figure8. It clearly indicates that CDT has less average hop count than the
other spanners. This happens because CDT contains constraint edges which make
packet transmission from source to destination with fewer hops. Since the
constraint edges are not available in RNG, GG, LDel1, and PLDel, they take more
hops.Figure 8
Average hop
count.In third experiment we have checked the end-to-end
packet delay on different network topologies. Here, we consider only the
packets that reach the destination. The source node sends the packets greedily
to the destination on five different spanners at different transfer rates.
Figure9 shows the average delays. We can observe that CDT contains less
average delay compared to the other spanners. This is again because of
constraint edges in CDT, which make the packets to reach destination with less
number of transmissions.Figure 9
Average delay inμsec.In the fourth experiment, we have considered the
standard deviation in delay, called standard delay (Sd). Standard
delay is related to one of the quality of service (QoS) parameter called
jitter. One can see from Figure 10, the
standard deviation of the end-to-end packet delay on the spanner CDT is lesser
than the other spanners. This could happen because the total number of
transmissions on the spanner CDT is less which makes
the variation to the average delay will also be less.Figure 10
Standard delay inμsec.The minimum and maximum values of the packet
end-to-end delay for different network topologies are shown in Figures11 and
12, respectively, at different transfer rates for the five network topologies.
We can observe that the minimum and maximum packet's end-to-end delays of CDT
are lesser than the other spanners.Figure 11
Minimum delay inμsec.Figure 12
Maximum delay inμsec.The graphs for minimum and maximum hop counts are
shown in Figures13 and 14, respectively. Due to the constraint edges in CDT,
the minimum and maximum hop counts are lesser in CDT than the other spanners.Figure 13
Minimum hop count.Figure 14
Maximum hop count.Figures15 and 16 show the minimum and maximum
standard delays, respectively. From the experiments, we have seen that the
minimum and maximum standard delays are lesser in CDT.Figure 15
Minimum standard delay inμsec.Figure 16
Maximum standard delay inμsec.We have done the final experiment on throughput.
Figures17, 18 and 19 show that the constrained Delaunay triangulation has
better throughput compared to other spanners. This can happen because the
constraint edges in CDT make the packets to reach the destination with fewer
number of transmissions than in PLDel, LDel, GG, and RNG, which reduces the
collisions, and latency thereby increase the
throughput.Figure 17
Average throughput.Figure 18
Maximum throughput.Figure 19
Minimum throughput.


## 3.1. Performance Metrics

In this paper, we have considered the following
metrics to evaluate the performance of different spanners.(1)
Hop count. This metric
represents the total number of hops traveled by a
data packet from source to destination on the underlying network graph.(2)
Delivery ratio. The delivery ratio (DR) is the ratio
of the total number of packets received successfully to the total packets sent
by the source.(3)
Delay. Delay metric is the total time
spent by a packet during the data transmission from source to destination.(4)
Standard delay. Standard delay is the
standard deviation in the delay of a packet from source to destination. The
following mathematical formula is used to calculate the standard delay (Sd):
(1)Sd=1m×∑i=1m(ai−a¯),
whereai denotes delay
of ith packet, a¯ is average
delay, and m is total number
of packets.(5)
Throughput. Throughput is the total number
of packets transmitted per unit time from source to destination.In the simulation results, we have presented average,
minimum, and maximum of the above metrics.


## 3.2. Simulation Model and Results

Important parameters of the simulation are shown in
Table1. All experiments are conducted on ten different node scenarios. For
each scenario, we have considered ten different connection patterns, by
randomly choosing source nodes at one side and destination nodes at the other
side. In our simulation model, we do not consider the link quality, as we
assumed that the channel is error free.Table 1
Simulation parameters.
Grid size200×200m2Number
of nodes100Transmission
range40 mPropagation
modelTwoRay GroundMAC
layer typeIEEE 802.11CBR
packet size512 bytesSimulation
run time350 secAntennaOmniAntennaAntenna
height1.5 mMax
packet in ifq100Frequency914e+6 HzSystem
loss factor1.0Recv
power threshold3.652e-10 wCarrier
sense threshold1.559e-11Capture
threshold10.0 dbInitial
energy300 JThe first experiment is on delivery ratio. The average
delivery ratio of ten different scenarios with six different routing protocols
is shown in Table2. The delivery ratio of CDT is better than RNG and GG
because CDT is denser graph than RNG and GG. There is not much difference among
CDT, PLDel, and LDel1 because many edges are common
among them.Table 2
Delivery ratios.
RNGGGLDelPLDelCDTNN40.977.899.999.998.4FN43.578.192.891.995.4MFR73.786.999.899.899.8Compass90.097.899.999.999.9RandComp90.097.999.999.999.9Greedy72.893.9100100100In the second experiment, we have computed the minimum
hop count between source and destination on different network topologies. The
source node sends the packet to the destination greedily on five different
network topologies. The average hop count at different CBR intervals are shown
in Figure8. It clearly indicates that CDT has less average hop count than the
other spanners. This happens because CDT contains constraint edges which make
packet transmission from source to destination with fewer hops. Since the
constraint edges are not available in RNG, GG, LDel1, and PLDel, they take more
hops.Figure 8
Average hop
count.In third experiment we have checked the end-to-end
packet delay on different network topologies. Here, we consider only the
packets that reach the destination. The source node sends the packets greedily
to the destination on five different spanners at different transfer rates.
Figure9 shows the average delays. We can observe that CDT contains less
average delay compared to the other spanners. This is again because of
constraint edges in CDT, which make the packets to reach destination with less
number of transmissions.Figure 9
Average delay inμsec.In the fourth experiment, we have considered the
standard deviation in delay, called standard delay (Sd). Standard
delay is related to one of the quality of service (QoS) parameter called
jitter. One can see from Figure 10, the
standard deviation of the end-to-end packet delay on the spanner CDT is lesser
than the other spanners. This could happen because the total number of
transmissions on the spanner CDT is less which makes
the variation to the average delay will also be less.Figure 10
Standard delay inμsec.The minimum and maximum values of the packet
end-to-end delay for different network topologies are shown in Figures11 and
12, respectively, at different transfer rates for the five network topologies.
We can observe that the minimum and maximum packet's end-to-end delays of CDT
are lesser than the other spanners.Figure 11
Minimum delay inμsec.Figure 12
Maximum delay inμsec.The graphs for minimum and maximum hop counts are
shown in Figures13 and 14, respectively. Due to the constraint edges in CDT,
the minimum and maximum hop counts are lesser in CDT than the other spanners.Figure 13
Minimum hop count.Figure 14
Maximum hop count.Figures15 and 16 show the minimum and maximum
standard delays, respectively. From the experiments, we have seen that the
minimum and maximum standard delays are lesser in CDT.Figure 15
Minimum standard delay inμsec.Figure 16
Maximum standard delay inμsec.We have done the final experiment on throughput.
Figures17, 18 and 19 show that the constrained Delaunay triangulation has
better throughput compared to other spanners. This can happen because the
constraint edges in CDT make the packets to reach the destination with fewer
number of transmissions than in PLDel, LDel, GG, and RNG, which reduces the
collisions, and latency thereby increase the
throughput.Figure 17
Average throughput.Figure 18
Maximum throughput.Figure 19
Minimum throughput.


## 4. Conclusion

The existing geometric spanners GG, RNG, LDel1, and PLDel have smaller edges
due to their geometric properties, which
increase the hop count and delay. We have proposed
CDT by introducing larger constrained edges to reduce hop count and delay. The
experimental results substantiate our claim. Moreover, CDT is most suitable
geometric spanner for multimedia and real-time applications because of
lower standard delays. It would be interesting to study these spanners under
various mobility conditions.



---

*Source: 160453-2008-05-20.xml*