02-02-2010, 06:33 PM
[attachment=1690]
Scalable Wireless Ad-Hoc Network Simulation using XTC
Project Pre requisitions:-
The XTC ad-hoc network topology control algorithm shows three main advantages over previously proposed algorithms. First, it is extremely simple. Second, it does not assume the network graph to be a Unit Disk Graph; XTC proves correct also on general weighted network graphs. Third, the algorithm does not require availability of node position information. Instead, XTC operates with a general notion of order over the neighborsâ„¢ link qualities. In the special case of the network graph being a Unit Disk Graph, the resulting topology proves to have bounded degree, to be a planar graph, andâ€on average-case graphsâ€to be a good spanner. Employed on Euclidean and Unit Disk Graphs.
Topology Control:-
For two communicating ad-hoc nodes u and v, the energy consumption of their communication grows at least quadratically with their distance. Having one or more relay nodes between u and v therefore helps to save energy.
The primary target of a topology control algorithm is to abandon long-distance communication links and instead route a message over several small (energy-efficient) hops .For this purpose each node in the ad-hoc network chooses a handful of close by neighbors in all points of the compass. Clearly nodes cannot abandon links to too many far-away neighbors in order to prevent the ad-hoc network from being partitioned or the routing paths from becoming noncompetitively long. In general there is a trade-off between networks connectivity and sparseness. Let the graph G = (V;E) denote the ad-hoc network before running the topology control algorithm, with V being the set of ad-hoc nodes, and E representing the set of communication links. There is a link (u; v) in E if and only if the two nodes u and v can communicate directly. Running the topology control algorithm will yield a sparse sub graph
Gtc= (V; Etc) of G, where Etc is the set of remaining links. The resulting topology Gtc should have the following properties:
Property 1 (Symmetry):-
The resulting topology Gtc should be symmetric, that is, node u is a neighbor of node v if and only if node v is a neighbor of node u. Asymmetric communication graphs are unpractical, because many communication primitives become unacceptably complicated. A simple ACK message confirming the receipt of a Message, for example, is already a nightmare in an asymmetric graph.
Property 2 (Connectivity):-
Two nodes u and v are connected if there is a path from u to v, potentially through multiple hops. If two nodes are connected in G, then they should still be connected in Gtc. Although a minimum spanning tree (MST) is a sparse connected subgraph, it is often not considered a good topology, since close-by nodes in the original graph G might end up being far away in Gtc (G being a ring, for instance). Therefore Property 2 is usually strengthened:
Property 2+ (Spanner):-
For any two nodes u and v, if the optimal path between u and v in G has cost c, then the optimal path between u and v in Gtc has cost f©. If f© is bounded from above by a linear function in c, the graph Gtc is called a spanner. Researchers have studied a selection of cost metrics, the most popular being i) Euclidean distance and ii) various energy metrics. The cost of a link in model i) is the Euclidean distance of the link, in model ii) the distance is raised to a predefined power. In both models the cost of a path is commonly defined to be the sum of the costs of all links in the path. As mentioned, the primary target of a topology control algorithm is to abandon long-distance neighbors, or more formally.
Property 3 (Sparseness):-
The remaining graph Gtc should be sparse, that is, the number of links should be in the order of the number of nodes, i.e. jEtcj = O(jV j). This reflects that not too many close-by nodes must be chosen, which reduces interference and thus saves energy. Since there still might be some nodes with many neighbors (e.g. a star graph), also Property 3 features an improved version.
Property 3+ (Low Degree):-
Each node in the remaining graph Gtc has a small number of neighbors. In particular the maximum degree in the graph Gtc should be bounded from above by a constant. Since connectivity and sparseness run against each other, topology control has been a thriving research area. In addition to the properties 1, 2, and 3, one can often find secondary targets. For instance, it is popular (and often for free) to ask the remaining graph to be planar in order to run a geometric (a.k.a. geographic, location-based, position-based) routing algorithm, such as GOAFR/GOAFR+ [11, 13], or GFG/GPSR [2, 9].
Preliminaries:-
In a weighted graph G = (V; E) every edge (u; v) 2 E is attributed a weight! uv. When referring to a weighted graph we assume that the weights are symmetric: !uv = !vu. The nodes of a Euclidean graph are assumed to be located in a Euclidean plane. Furthermore the edge weight of an edge (u; v) is defined to be !uv = juvj, where juvj is the Euclidean distance between the nodes u and v. Note that the definition of Euclidean graphs does not contain a statement on the existence of certain edges. A Unit Disk Graph is a Euclidean graph containing an edge (u; v) if and only if juvj _ 1. Unit Disk Graphs are often employed to model an ad-hoc network where all network nodes are placed in an unobstructed plane and have equal (normalized) transmission power and isotropic antennas that is antennas sending with identical power in every direction of the plane. Strongly related to edge weights is the cost of an edge. The cost of an edge c(u; v) can be considered to represent the effort an algorithm is required to expend in order to send a message over (u; v). Common definitions of edge cost metrics include the hop or link metric c(u; v) _ 1, the Euclidean metric c(u; v) = juvj, and the energy metric c(u; v) = juvje for an attenuation exponent e _ 2. A path p(u; v) from a node u to a node v being a sequence of consecutively contingent edges starting at u and ending at v, the cost of a path jp(u; v)j is accordingly defined to be the sum of the costs of all edges contained in the path.
XTC Algorithm:-
The algorithm consists of three main steps:
I) Neighbor ordering,
II) Neighbor order exchange, and
III) Edge selection.
Detail Explanation:-
In the first step each network node u computes a total order over all its neighbors in the network graph G. From an abstract point of view, this order is intended to reflect the quality of the links to the neighbors. A node u will consider its neighbors in G (in the third step of the algorithm) according to _u ordered with respect to decreasing link quality: The link to a neighbor appearing early in the order _u is regarded as being of higher quality than the link to a neighbor placed later in _u. A neighbor w appearing before v in order _u is denoted as w _u v. The neighbor order reflects a much more general notion of link quality, such as signal attenuation or packet arrival rate. In the second step the neighbor order information is exchanged among all neighbors.
Typically a node u broadcasts its own neighbor order while receiving the orders established by all of its neighbors. During the third step, which does not require any further Communication, each node locally selects those neighboring nodes which will form its neighborhood in the resulting topology control graph, based on the previously exchanged neighbor order information. For this purpose a node u traverses _u with decreasing link quality: Good neighbors are considered first, worse ones later. Informally speaking, a node u only builds a direct communication link to a neighbor v if u has no better neighbor w that can be reached more easily from v than u itself.
Although the XTC algorithm is executed at all nodes, the detailed description as shown in the above box assumes the point of view of a node u. Lines 1 and 2 correspond to Steps I) and II). Lines 3-11 define Step III) in more detail: First the two sets Nu and _ Nu are initialized to be empty. Now the neighbor ordering _u established in Line 1, is traversed in increasing order. In Line 7 the neighbor order _u of the currently considered neighbor v is examined: If any of uâ„¢s neighbors w already processed appears in vâ„¢s order before u (w _v u) node v is included in _ Nu (Line 8); otherwise v is added to Nu (Line 10). After completion of the algorithm, the set Nu contains uâ„¢s neighbors in the topology control graph GXTC. More formally, the edge set EXTC of the graph GXTC = (V;EXTC) is EXTC = f(u; v)j 9u: v 2 Nug. In the algorithm as described above, each node constructs in Step I) a total order over all its neighbors in G. In a variant of the algorithm a node u could apply a growing radius technique†starting with the best neighbor†to decide on a neighbor vâ„¢s inclusion in Nu or _ Nuâ€based on _vâ€immediately when identifying v as the next worse neighbor found so far. Applying such interleaving of steps I), II) and III), u could terminate earlier, that is, as soon as having found enough neighbors. Property 1 is symmetry of the resulting graph, often has to be enforced by topology control algorithms.
Project Modules:-
The various modules in the protocol are as follows
Module 1:-
Sending the data in the form of packet
Module 2:-
Using the XTC algorithm the ranking for each node is calculated.
Distance
Energy
Link Quality
Module 3:-
Nodes exchange rankings with neighbors.
Module 4:-
Each node locally goes through all neighbors in order of their ranking
If the candidate ranks any of your already processed neighbors higher than yourself, then you do not need to connect to the candidate.
System requirements:-
S/w requirements:-
Operating system : Red Hat Linux, version 7.1 and above, Windows
Kernel Version : Linux Kernel 2.2
Programming Language : J2SD1.4.1
H/w requirements:-
RAM : 128 MB
Hard Disk Drive : 10GB
Processor : Pentium iii and above
Monitor : 15
Data Flow Diagram:-
Flow Chart Analysis :
Scalable Wireless Ad-Hoc Network Simulation using XTC
Project Pre requisitions:-
The XTC ad-hoc network topology control algorithm shows three main advantages over previously proposed algorithms. First, it is extremely simple. Second, it does not assume the network graph to be a Unit Disk Graph; XTC proves correct also on general weighted network graphs. Third, the algorithm does not require availability of node position information. Instead, XTC operates with a general notion of order over the neighborsâ„¢ link qualities. In the special case of the network graph being a Unit Disk Graph, the resulting topology proves to have bounded degree, to be a planar graph, andâ€on average-case graphsâ€to be a good spanner. Employed on Euclidean and Unit Disk Graphs.
Topology Control:-
For two communicating ad-hoc nodes u and v, the energy consumption of their communication grows at least quadratically with their distance. Having one or more relay nodes between u and v therefore helps to save energy.
The primary target of a topology control algorithm is to abandon long-distance communication links and instead route a message over several small (energy-efficient) hops .For this purpose each node in the ad-hoc network chooses a handful of close by neighbors in all points of the compass. Clearly nodes cannot abandon links to too many far-away neighbors in order to prevent the ad-hoc network from being partitioned or the routing paths from becoming noncompetitively long. In general there is a trade-off between networks connectivity and sparseness. Let the graph G = (V;E) denote the ad-hoc network before running the topology control algorithm, with V being the set of ad-hoc nodes, and E representing the set of communication links. There is a link (u; v) in E if and only if the two nodes u and v can communicate directly. Running the topology control algorithm will yield a sparse sub graph
Gtc= (V; Etc) of G, where Etc is the set of remaining links. The resulting topology Gtc should have the following properties:
Property 1 (Symmetry):-
The resulting topology Gtc should be symmetric, that is, node u is a neighbor of node v if and only if node v is a neighbor of node u. Asymmetric communication graphs are unpractical, because many communication primitives become unacceptably complicated. A simple ACK message confirming the receipt of a Message, for example, is already a nightmare in an asymmetric graph.
Property 2 (Connectivity):-
Two nodes u and v are connected if there is a path from u to v, potentially through multiple hops. If two nodes are connected in G, then they should still be connected in Gtc. Although a minimum spanning tree (MST) is a sparse connected subgraph, it is often not considered a good topology, since close-by nodes in the original graph G might end up being far away in Gtc (G being a ring, for instance). Therefore Property 2 is usually strengthened:
Property 2+ (Spanner):-
For any two nodes u and v, if the optimal path between u and v in G has cost c, then the optimal path between u and v in Gtc has cost f©. If f© is bounded from above by a linear function in c, the graph Gtc is called a spanner. Researchers have studied a selection of cost metrics, the most popular being i) Euclidean distance and ii) various energy metrics. The cost of a link in model i) is the Euclidean distance of the link, in model ii) the distance is raised to a predefined power. In both models the cost of a path is commonly defined to be the sum of the costs of all links in the path. As mentioned, the primary target of a topology control algorithm is to abandon long-distance neighbors, or more formally.
Property 3 (Sparseness):-
The remaining graph Gtc should be sparse, that is, the number of links should be in the order of the number of nodes, i.e. jEtcj = O(jV j). This reflects that not too many close-by nodes must be chosen, which reduces interference and thus saves energy. Since there still might be some nodes with many neighbors (e.g. a star graph), also Property 3 features an improved version.
Property 3+ (Low Degree):-
Each node in the remaining graph Gtc has a small number of neighbors. In particular the maximum degree in the graph Gtc should be bounded from above by a constant. Since connectivity and sparseness run against each other, topology control has been a thriving research area. In addition to the properties 1, 2, and 3, one can often find secondary targets. For instance, it is popular (and often for free) to ask the remaining graph to be planar in order to run a geometric (a.k.a. geographic, location-based, position-based) routing algorithm, such as GOAFR/GOAFR+ [11, 13], or GFG/GPSR [2, 9].
Preliminaries:-
In a weighted graph G = (V; E) every edge (u; v) 2 E is attributed a weight! uv. When referring to a weighted graph we assume that the weights are symmetric: !uv = !vu. The nodes of a Euclidean graph are assumed to be located in a Euclidean plane. Furthermore the edge weight of an edge (u; v) is defined to be !uv = juvj, where juvj is the Euclidean distance between the nodes u and v. Note that the definition of Euclidean graphs does not contain a statement on the existence of certain edges. A Unit Disk Graph is a Euclidean graph containing an edge (u; v) if and only if juvj _ 1. Unit Disk Graphs are often employed to model an ad-hoc network where all network nodes are placed in an unobstructed plane and have equal (normalized) transmission power and isotropic antennas that is antennas sending with identical power in every direction of the plane. Strongly related to edge weights is the cost of an edge. The cost of an edge c(u; v) can be considered to represent the effort an algorithm is required to expend in order to send a message over (u; v). Common definitions of edge cost metrics include the hop or link metric c(u; v) _ 1, the Euclidean metric c(u; v) = juvj, and the energy metric c(u; v) = juvje for an attenuation exponent e _ 2. A path p(u; v) from a node u to a node v being a sequence of consecutively contingent edges starting at u and ending at v, the cost of a path jp(u; v)j is accordingly defined to be the sum of the costs of all edges contained in the path.
XTC Algorithm:-
The algorithm consists of three main steps:
I) Neighbor ordering,
II) Neighbor order exchange, and
III) Edge selection.
Detail Explanation:-
In the first step each network node u computes a total order over all its neighbors in the network graph G. From an abstract point of view, this order is intended to reflect the quality of the links to the neighbors. A node u will consider its neighbors in G (in the third step of the algorithm) according to _u ordered with respect to decreasing link quality: The link to a neighbor appearing early in the order _u is regarded as being of higher quality than the link to a neighbor placed later in _u. A neighbor w appearing before v in order _u is denoted as w _u v. The neighbor order reflects a much more general notion of link quality, such as signal attenuation or packet arrival rate. In the second step the neighbor order information is exchanged among all neighbors.
Typically a node u broadcasts its own neighbor order while receiving the orders established by all of its neighbors. During the third step, which does not require any further Communication, each node locally selects those neighboring nodes which will form its neighborhood in the resulting topology control graph, based on the previously exchanged neighbor order information. For this purpose a node u traverses _u with decreasing link quality: Good neighbors are considered first, worse ones later. Informally speaking, a node u only builds a direct communication link to a neighbor v if u has no better neighbor w that can be reached more easily from v than u itself.
Although the XTC algorithm is executed at all nodes, the detailed description as shown in the above box assumes the point of view of a node u. Lines 1 and 2 correspond to Steps I) and II). Lines 3-11 define Step III) in more detail: First the two sets Nu and _ Nu are initialized to be empty. Now the neighbor ordering _u established in Line 1, is traversed in increasing order. In Line 7 the neighbor order _u of the currently considered neighbor v is examined: If any of uâ„¢s neighbors w already processed appears in vâ„¢s order before u (w _v u) node v is included in _ Nu (Line 8); otherwise v is added to Nu (Line 10). After completion of the algorithm, the set Nu contains uâ„¢s neighbors in the topology control graph GXTC. More formally, the edge set EXTC of the graph GXTC = (V;EXTC) is EXTC = f(u; v)j 9u: v 2 Nug. In the algorithm as described above, each node constructs in Step I) a total order over all its neighbors in G. In a variant of the algorithm a node u could apply a growing radius technique†starting with the best neighbor†to decide on a neighbor vâ„¢s inclusion in Nu or _ Nuâ€based on _vâ€immediately when identifying v as the next worse neighbor found so far. Applying such interleaving of steps I), II) and III), u could terminate earlier, that is, as soon as having found enough neighbors. Property 1 is symmetry of the resulting graph, often has to be enforced by topology control algorithms.
Project Modules:-
The various modules in the protocol are as follows
Module 1:-
Sending the data in the form of packet
Module 2:-
Using the XTC algorithm the ranking for each node is calculated.
Distance
Energy
Link Quality
Module 3:-
Nodes exchange rankings with neighbors.
Module 4:-
Each node locally goes through all neighbors in order of their ranking
If the candidate ranks any of your already processed neighbors higher than yourself, then you do not need to connect to the candidate.
System requirements:-
S/w requirements:-
Operating system : Red Hat Linux, version 7.1 and above, Windows
Kernel Version : Linux Kernel 2.2
Programming Language : J2SD1.4.1
H/w requirements:-
RAM : 128 MB
Hard Disk Drive : 10GB
Processor : Pentium iii and above
Monitor : 15
Data Flow Diagram:-
Flow Chart Analysis :