One document matched: draft-zhou-dceemr-00.txt
Network Working Group X.W.Zhou
INTERNET-DRAFT X.N.Miao
Intended status: Informational U.S.T.B
Expires: February 22, 2011 August 22, 2010
DCEEMR: A Delay-constrained Energy Efficient Multicast Routing
Algorithm in Cognitive Radio ad hoc Networks
draft-zhou-dceemr-00.txt
Abstract
In this paper, we discuss the delay-constrained energy efficient
multicast routing problem in cognitive radio ad hoc networks. A
cognitive radio ad hoc network is a wireless multi-hop network
established by secondary users on varying available spectrum bands.
The routing research is a hotspot in the field of cognitive radio
ad hoc networks. However, multicast routing algorithm study of
cognitive radio ad hoc networks is still in starting stage. In this
paper, we proposed a novel delay-constrained energy efficient
multicast routing algorithm (DCEEMR) in cognitive radio ad hoc
networks. The DCEEMR guarantees that the multicast tree can be found
if it exists, and the multicast tree satisfies the delay bound and
has low energy consuming. The algorithm uses delay-energy function
to construct the multicast tree based on the spectrum selection.
Through an example with randomly network topology, we demonstrate
that our algorithm is better in terms of energy cost of multicast
tree as compared to the existing algorithm QoS Dependent Multicast
Routing (QDMR). Moreover, the algorithm does not suffer from high
complexity common to the algorithm QDMR. Experiment results by NS-2
show that the delay and tree cost are lower than well-known
Multicast ad- hoc On-demand Distance Vector (MAODV) protocol.
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with
the provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on February 22, 2011.
Zhou&Miao Expires - February 22, 2011 [Page 1]
Internet-Draft Link State Update Mechanism August 2010
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the BSD License.
This document may contain material from IETF Documents or IETF
Contributions published or made publicly available before November
10, 2008. The person(s) controlling the copyright in some of this
material may not have granted the IETF Trust the right to allow
modifications of such material outside the IETF Standards Process.
Without obtaining an adequate license from the person(s) controlling
the copyright in such materials, this document may not be modified
outside the IETF Standards Process, and derivative works of it may
not be created outside the IETF Standards Process, except to format
it for publication as an RFC or to translate it into languages other
than English.
Zhou&Miao Expires - February 22, 2011 [Page 2]
Internet-Draft Link State Update Mechanism August 2010
Table of Contents
1. Terminology....................................................4
2. Introduction...................................................4
3. Network Model and Problem Specification........................7
4. DCEEMR algorithm...............................................9
4.1 Spectrum selection in multicast tree.......................9
4.2 Formulas in DCEEMR algorithm...............................10
4.3 Algorithm Implements.......................................12
5. Security Considerations........................................14
6. IANA Considerations............................................15
7. References.....................................................15
Author's Addresses................................................16
Zhou&Miao Expires - February 22, 2011 [Page 3]
Internet-Draft Link State Update Mechanism August 2010
1. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].
This document uses terms from [RFC3261][1].
2. Introduction
Recent technological advances have resulted in the development of
wireless ad hoc networks composed of devices that are self-organizing
and can be deployed without infrastructure support. These devices
generally have small form factors, and have embedded storage,
processing and communication ability [1]. With the growing
proliferation of wireless devices, these bands are increasingly
getting congested.
The licensing of the wireless spectrum is currently undertaken on
a long-term basis over vast geographical regions. In order to
address the critical problem of spectrum scarcity, the FCC has
recently approved the use of unlicensed devices in licensed bands.
Consequently, dynamic spectrum access techniques are proposed to
solve these current spectrum inefficiency problems. This new area
of research foresees the development of cognitive radio networks
to further improve spectrum efficiency. The basic idea of cognitive
radio networks is that the unlicensed devices (also called cognitive
radio users or secondary users) need to vacate the band once the
licensed device (also known as a primary user) is detected. The
emerging field of cognitive radio networks is geared to address the
increasing congestion in the unlicensed band by opportunistically
using vacant spectrum, such as, frequencies licensed for television
broadcast, public service, among others [2]. Cognitive radios are
highly agile wireless platforms capable of autonomously choosing
device parameters based on prevailing operating conditions [3].
Cognitive radio networks, however, impose unique challenges due to
the high fluctuation in the available spectrum as well as diverse
quality of service (QoS) requirements [4].
Cognitive radio ad hoc networks can be defined as follows [5]:
Cognitive radio ad hoc network is considered for realizing the
cognitive radio by using multi-hop communication networks without
giving the large interference toward the primary system. In [1],
the authors give the differences between Cognitive radio ad hoc
networks and classical ad hoc networks:
(1) Choice of transmission spectrum: In Cognitive radio ad hoc
networks, the available spectrum bands are distributed over a wide
frequency range, which vary over time and space. Thus, each user
shows different spectrum availability according to the primary user
activity. As opposed to this, classical ad hoc networks generally
operate on a pre-decided channel that remains unchanged with time.
For the ad hoc networks with multi-channel support, all channels are
continuously available for transmission, though nodes may select few
of the latter from this set based on self-interference constraints.
A key distinguishing factor is the primary consideration of
protecting the primary user transmission, which is entirely missing
in classical ad hoc networks.
Zhou&Miao Expires - February 22, 2011 [Page 4]
Internet-Draft Link State Update Mechanism August 2010
(2) Topology control: In classical ad hoc networks, this is easily
accomplished by periodic beacon messages on the channel. However,
in Cognitive radio ad hoc networks, as the licensed spectrum
opportunity exists over large range of frequencies, sending beacons
over all the possible channels is not feasible. Thus, cognitive
radio ad hoc networks are highly probable to have incomplete
topology information, which leads in an increase in collisions among
cognitive radio users as well as interference to the primary users.
(3) Multi-hop/multi-spectrum transmission: The end-to-end route in
the cognitive radio ad hoc networks consists of multiple hops having
different channels according to the spectrum availability. Thus,
cognitive radio ad hoc networks require collaboration between
routing and spectrum allocation in establishing these routes.
Moreover, the spectrum switches on the links are frequent based on
primary user arrivals. As opposed to classical ad hoc networks,
maintaining end-to-end QoS involves.
(4) Distinguishing mobility from primary user activity: In classical
ad hoc networks, routes formed over multiple hops may periodically
experience disconnections caused by node mobility. These cases may
be detected when the next hop node in the path does not reply to
messages and the retry limit is exceeded at the link layer. However,
in Cognitive radio ad hoc networks, a node may not be able to
transmit immediately if it detects the presence of a primary user on
the spectrum, even in the absence of mobility. Thus, correctly
inferring mobility condition and initiating the appropriate recovery
mechanism in cognitive radio ad hoc networks necessitate a different
approach from the classical ad hoc networks.
Based on the above, the existing routing algorithms and routing
protocols in classical ad hoc networks are not suitable for
cognitive radio ad hoc networks and are unaware of the changing
spectrum opportunity. In cognitive radio ad hoc networks, routes
must be constructed to avoid the regions affected by active primary
users and must also adapt themselves to subsequent changes induced
by new primary user arrivals. We discuss the delay-constrained
energy efficient multicast routing algorithm based on this principle.
The most significant challenges in cognitive radio ad hoc network
routing are to maximize secondary users' throughput and minimize
their consumed energy, while not interfering with the primary users.
Energy efficiency is a critical issue in cognitive radio ad hoc
network routing algorithms due to lack of infrastructure supporting.
Furthermore increasing real-time applications are required to be
satisfied QoS constraints, such as delay, jitter, data packets
lossing, etc. For the sake of guarantee the behalf of primary user,
such application requires consideration of spectrum selection and
spectrum switching.
Zhou&Miao Expires - February 22, 2011 [Page 5]
Internet-Draft Link State Update Mechanism August 2010
In the paper, we address the problem of multicast routing in
cognitive radio ad hoc networks, and first propose the delay-bounded
energy efficient multicast routing algorithm in cognitive radio ad
hoc networks. Multicast is communication from a single source node
to a group of multicast. A fundamental issue in multicast
communication is route selection, usually based on trees. So our
multicast routing algorithm makes great efforts to find a multicast
tree, which is rooted from the source and spans all multicast nodes
and have lowest energy cost of tree. In cognitive radio ad hoc
networks, nodes communicate with each other by radio signals, which
are broadcast in nature. The algorithm uses the local cost
information, which makes it can be easily actualized in a
distributed manner.
Routing algorithm is a hotspot issue in the field of cognitive
network. In cognitive radio ad hoc networks, its routing research
requires consideration of selection spectrum and routing path [6,7].
However, numerous works focused multicast routing on classical
wireless ad hoc networks [8]. Though there are some routing
protocols on supporting spectrum decision in cognitive radio
networks [9,10], most of the existing works focuses on unicast
routing. As far as multicast routing algorithm in cognitive radio
ad hoc networks, the research is still in starting stage.
In a classical ad hoc network, each node has a limited energy
resource (battery), and operates in an unattended manner.
Consequently, energy efficiency is an important design consideration
for these networks. Most recent work [11-15] has been proposed for
the problems of minimizing the energy consumption for multicasting
in classical wireless ad hoc networks, addressed as Minimum-Energy
Multicast (MEM) [6,11], respectively. Since the MEM problem have
recently been shown to be NP-hard [16,17].They proved the energy
efficient multicast routing problem is unlikely has an approximation
algorithm with a constant performance ratio of the number of nodes
in the networks. Efficient heuristic algorithm design has received
much more attention. Deying Li et al [6] proposed a steiner tree
based algorithm with a guaranteed approximation performance ratio
and two efficient heuristic algorithms for the energy efficient
multicast problem in ad hoc networks. And they first prove the
problem is NP-hard.
For the MEM problem, a straight greedy approach is the use of
multicast trees that consist of the best unicast paths to each
individual destination from the source node. In [11], Multicast
Incremental Power (MIP) method is based on a broadcast tree
construction algorithm with pruning the redundant branches of the
broadcast tree to obtain a multicast tree in wireless networks. For
supporting real-time applications, there have been many
delay-constrained multicast routing algorithms [12-14]. In [12],
Kou, Markowsky and Berman proposed a heuristic algorithm KMB with
named the abbreviation of their names for the steiner tree problem.
In [13], Kompella, Pasquale and Polyzos designed an algorithm named
KPP (the abbreviation of the authors), the algorithm extends KMB
algorithm to construct delay-constrained multicast tree.
Zhou&Miao Expires - February 22, 2011 [Page 6]
Internet-Draft Link State Update Mechanism August 2010
KPP algorithm assumes that the delay bound and link delays are all
integers. Guo and Matta proposed QDMR algorithm in [14], which
modified Destination-Driven Multicast Routing (DDMC) algorithm,
where DDMC is an unconstrained Steiner tree heuristic algorithm[15].
QDMR dynamic adjusts its indicator function according to ratio
between end-to-end delay (from source node to multicast node) and
the delay bound. But the two algorithms are not designed for
cognitive radio ad hoc network. Cheng G.and Liu W. et al [9]
proposed the method to evaluate cumulative delay in cognitive radio
ad hoc network. In their protocol, the cumulative delay was regarded
as routing metric, which was based on ad-hoc on-demand distance
vector (AODV) [18].
Our multicast routing algorithm arises from the observation that
DDMC algorithm to give priority to multicast nodes and QDMR
algorithm to choose the new adding node with lower end-to-end delay
in constructing multicast tree as soon as possible. But it is quite
different from these algorithms: at first, our multicast routing
algorithm adapts to cognitive radio ad hoc network environment
based on spectrum selection mechanism. The algorithm can construct
an energy efficient multicast tree with satisfying the delay bound.
Spectrum selection is based on our energy-delay function. Secondly,
our algorithm considers the average cost consuming of candidate node
covering multicast node in constructing multicast tree, so it is
more efficient than existing algorithms. We detail our algorithm in
Section 3. In the numerical results, we demonstrate that our
algorithm is better in terms of energy cost as compared to the
existing algorithm QDMP through an example. Experiment results by
NS-2 show that the delay and energy cost are lower than well-known
MAODV protocol [19].
In the remainder of this paper, in Section 2, we give the network
model and the problem definition. We detail our algorithm DCEEMR in
Section 3. In Section 4, we present the simulation results. We give
some conclusion in Section 5.
3. Network Model and Problem Specification
A cognitive radio ad hoc network can be modeled as a directed graph G
which has two variants V and E.The V is the union set of Vc and Vp,
which represents total network nodes. Vc represents cognitive nodes
(secondary users), Vp represents primary nodes (primary users). E is
the set of links representing logical connectivity between all
cognitive nodes. There is no link among primary nodes and between
primary nodes and cognitive nodes. If a link exists between cognitive
nodes vi and vj, that means vi and vj can connect directly while not
interfering with any primary node. We assume that vi belongs to Vc
which is a cognitive node and Ni is the set of neighbor nodes of vi.
Let prec(vi) be the predecessor node of vi and e(vi,vj) is the
energy cost of link (vi,vj). In this paper, we will construct an
energy efficient multicast tree T, where T belonging to G is a
sub-network of the cognitive ad hoc network. Our aim to find a
multicast tree T so that the sum of energy cost e(vi,vj),i and j
belong to T in multicast tree T is lower as soon as possible.
Zhou&Miao Expires - February 22, 2011 [Page 7]
Internet-Draft Link State Update Mechanism August 2010
In addition, based on spectrum availability and node mobility of
cognitive radio ad hoc networks, end-to-end delay should be
considered during the process of designing algorithm. We assume
that there are K channels in link(vi,vj) and d(vi,vj) is the delay
of link(vi,vj) from node vi to vj through channel k which belongs
to K.and b is the delay bound, where vi and vj belong to Vc. In
cognitive radio ad hoc networks, the end-to-end delay not only
denotes path latency from source node to a multicast node, but also
includes the time of switching channel owing to the factor of
primary user activity. Here, let P(s,vi) denote a path (or routing)
from source node s to vi. Similar to [2] and [9], we assume that the
channel switching time ts is fixed at vm that belongs to P(s,vi) and
path latency tp is delay sum of all links from source node to
multicast node vi belonging to M. If there is not primary user
activity in a routing, then we have ts=0. In our algorithm, we will
optimize the two objectives: energy consumption and end-to-end
delay. But the energy efficient is considered first, i.e., if we
find newly adding node which satisfy energy efficient, then we check
that whether the network satisfy delay requirement. We will describe
concretely our problem as follows.
Given a multicast request (s,M), where s is a source node and M is a
set of multicast nodes, let T be a multicast tree rooted at source
node s. Leaf nodes in T only receive message, do not need to
transmit them. We assume receiving messages do not consume any
energy, that means only transmitting message could incur energy
cost. Let Ct(e) be the energy cost of the links in T. We assume that
D(vi) is the sum of ts and tp and is the end-to-end delay of the
path from source node s to the multicast node vi and b is a delay
bound which means that the maximum tolerance of network if
end-to-end delay less than b. For every nodevi that belongs to M,
the delay bound from s to vi must be satisfied. That means: the
minimum value of the sum of Ct(e),and D(vi) less than b,vi
belonging to M.
If setting the delay bound to be infinity, the delay-constrained
MEM problem simplifies to the unconstrained MEM problem in cognitive
radio ad hoc network. Cognitive nodes in cognitive radio ad hoc
network can be regarded as the nodes in classical ad hoc network
without consideration to the interfering with primary users, and the
problem can be seen as the special case of unconstrained MEM
problem, which has been proved to be NP-hard. Our problem is how to,
given a multicast request (s,M) and energy cost Ct(e) for each link
e, find a multicast tree rooted at s and spanning all nodes in M
such that total energy cost is minimized. In this paper, we present
a heuristic algorithm to resolve this problem.
Zhou&Miao Expires - February 22, 2011 [Page 8]
Internet-Draft Link State Update Mechanism August 2010
4. DCEEMR algorithm
In this section, we shall describe the algorithm in three parts:
(1) the spectrum selection in multicast tree and the (2) algorithm
description, and at last (3) we give an example of DCEEMR algorithm.
Through an example, we demonstrate that our algorithm is better in
terms of energy cost of multicast tree as compared to the existing
algorithm QDMR.
4.1 Spectrum selection in multicast tree
In cognitive radio ad hoc networks, routing algorithm not only
considers path selection but also faces spectrum decisions. Many
routing protocols of cognitive radio ad hoc networks are based on
basically routing protocols of classical ad hoc networks, e.g., the
routing selecting in [20] and [9] is based on unicast routing
protocol AODV and in [2] is based on geographic routing protocol
greedy perimeter stateless routing (GPSR) [21]. The best routing
paths are fist identified and then the preferred spectrums among
the path are chosen in [3], here, the AODV routing protocol is
modified to include the list of preferred spectrums by a given node
as the route request (RREQ) is forwarded. Once the RREQ is received,
the destination is aware of spectrums that may be used to transmit
at each hop and finds the optimal combination such that channel
switching is minimized. These routing protocols are not applicable
in delay-constrained energy efficient multicast routing problem,
because it can not guarantee the delay from source node to multicast
nodes all satisfy the delay bound. But our spectrum selection
mechanism is similar to these spectrum opportunities (SOP)
methods [9]. Intuitively, a channel can be considered as an
opportunity if it is not currently used by primary users [22].
Consider a pair of secondary users (AandB) aiming to communicate in
the presence of primary users. A channel is an opportunity to A and
B if they can communicate successfully over this channel while
limiting the interference to primary users below a prescribed level
determined by the regulatory policy. A common control channel is
then formed by those traditional interfaces, such that all
nodes' SOP can be shared among network. The key message is that SOP
must be defined jointly at the transmitter and the receiver. It is
a function of (1) the transmission powers of both primary and
secondary nodes, (2) the geographical locations of these nodes,
and (3) the interference constraint. From this definition, we arrive
at the following properties of spectrum opportunity.
P1. Spectrum opportunity depends on both transmitting and receiving
activities of primary users.
P2. Spectrum opportunity is, in general, asymmetric: a channel that
is an opportunity when A is the transmitter and B the receiver may
not be an opportunity when B is the transmitter and A the receiver.
Zhou&Miao Expires - February 22, 2011 [Page 9]
Internet-Draft Link State Update Mechanism August 2010
In [9] and [21], end-to-end delay consists of channel switching time
and path latency which is delay sum of all links from source node
to multicast node vi from M. Based on that D(vi) is the sum of ts
and tp, we can get the end-to-end delay from the source node to the
nodes in multicast tree T. Similar with [2] and [9], we select
appropriate spectrum based on the delay for every nodes. Thus our
work focus on selecting appropriate nodes as tree nodes to
construct a delay-bounded energy efficient multicast tree, we
consider spectrum decision based on the delay in multicast tree in
cognitive radio ad hoc network.
At first, a RREQ packet with piggyback (SOP s) information which
is available spectrum band is transmitted by the source node on
each channel that is not affected by the primary user activity. For
example, in figure 1, the RREQ packet carries (SOP s) of node
transmit to node H, node I and node J. If SOP information of
receiving nodes exist intersection with sending node, this means
that receiving node can use same spectrum with sending node and
does not interfere with nearby primary node, then the receiving
node adds its own SOP information to the packet then forward the
message.
(1) Handling RREQ packet: After receiving RREQ packet, as forwarding
nodes, node H and node I add their own SOP information to the packet
and then forward the different RREQ packet (bring their (SOP s, H)
and (SOP s, I) information respectively) to their next hop nodes if
their SOP information exist intersection with (SOP s), and
otherwise drop RREQ . But as destination nodes, nodes J, K , F and
G chooses available spectrum band from intersection of (SOP s) and
then encapsulate spectrum choice into route reply (RREP) and sent
back to predecessor node or source node.
(2)Handling RREP packet: After receiving RREP packet, as forwarding
nodes, node H and I assign an appropriate spectrum band to the next
hop or source node respectively based on our delay-energy function
in DCEEMR algorithm, which will be described concretely in next
subsection. But as source node S , it starts data packet transfer.
4.2 Formulas in DCEEMR algorithm
Given a multicast request (s,M), we first define three sets.
Firstly, let V(T) be the set of nodes in multicast tree T, including
only source node at the beginning of constructing the tree. We aim
to find the delay bounded efficient energy multicast tree including
all multicast nodes in V(T). Let NT be the set of neighbor nodes of
the multicast tree T, i.e., it contains the neighbor nodes of
candidate nodes. Meanwhile, let U be the set of the uncovered
multicast nodes. An uncovered multicast node means a node belongs
to neither V(T) nor NT. We assume that vi from Vc is a cognitive
node and Ni is the set of neighbor nodes of vi.Let prec(vi) be the
predecessor node of vi and e(vi,vj) is the cost of link(vi,vj).
Zhou&Miao Expires - February 22,2011 [page 10]
Internet-Draft Link State Update Mechanism August 2010
This heuristic grows the multicast tree from s. At the beginning,
V(T) only contains source node s, NT contains the neighbor nodes of
s, and U contains all multicast node s. After running the algorithm
to end, U becomes null, that means V(T) contains all multicast
nodes. For selecting appropriate forwarding nodes to minimize the
total cost in formula (1) and to satisfy the delay-bound b, we
define a delay-energy function to evaluate each candidate node vi
from NT.
The function can be described as follows.First we define a function
f(vi).We get a result of b minus D(vj),then we get a sum of the
results of each vj from Ni.We make it the denominator,and the
intersection of Ni and U the numerator.We define this function as X.
The second,we get a sum of e(vi,vj) of evey value from Nj.We use
this result to multiply X,then plus e(prec(vi),vj) makes f(vi).The
last, we use D(vi) to multiply e(prec(vi),vj) as numerator and the
b as the denominator.So we get g(vi).
Wheree (prec(vi),vj) denote link cost the between of tree node
prec(vi) and the candidate node vi, and the result of sum of
e(vi,vj) divided by the intersection of Ni and U denotes the average
energy cost of the candidate node vi from NT covering a multicast
node. The X denotes the average residual delay from the source node
to a multicast node covered by the candidate node vi, where D(vi)
is the end-to-end delay from the source node to the multicast node
vj. The nodes with lower energy cost and delay are chosen to add to
the tree in our algorithm.
If the candidate node vi subject to the intersection of Ni and U
that is null, choose the node with lower f(vi) to add to the tree.
If he candidate nodevi from NT subject to intersection of Ni and U
that is null, we use the function mentioned above to evaluate every
candidate node.
Now, we discuss our energy-delay function. In KPP algorithm, the
choice function only adds the cost link which ensures the ratio of
the cost between two multicast nodes and residual delay in completed
graph to be lowest. But it does not fit for cognitive radio ad hoc
network. Instead, we first calculate the average cost of the
candidate node covering multicast nodes, and then use the sum of
the average cost and the communication cost between the candidate
node and its father node as numerator. This sum value is more fair
and proper to the delay-constrained energy efficient multicast
routing problem in cognitive network. While the value of f(vi) is
lower, the cost consuming of candidate node covering multicast node
is more efficient, and at the same time, the end-to-end delay is
less than delay bound b.
In DDMC algorithm, the algorithm gives priority to multicast nodes.
The cost of a new node v via a node u to add to the multicast tree
is Cost(v). We use I(u) to multiply Cost(u) then make the result
plus c(u,v) to get Cost(v).Where the indicator function I(u) is
defined as follows: If u belongs to M, I(u) is 0,otherwise, I(u)
is 1.
Zhou&Miao Expires - February 22, 2011 [page 11]
Internet-Draft Link State Update Mechanism August 2010
Where M is the set of multicast nodes. If node u is a multicast
node, the cost of the new node v is only the cost of the link from
node u to v. It made the path to a new node via a multicast node is
more likely to add to the tree. This information is used to give
"preference" to multicast nodes. But the constructed tree is easy
to have some very long branches like a chain of multicast nodes,
which lead some multicast nodes violate delay bound. Guo and Matta
proposed QDMR algorithm in [14], which modified DDMC algorithm.
It modified the indicator function, let it can adjust according to
how far a multicast node is from the delay bound. The indicator
function is: If u belongs to M, we make Delay(u) divided by b to
get I(u).Otherwise , I(u) is 1.
Where Delay(u) is the delay sum of all links from source node to
multicast node u and b is the delay bound. If the delay of the
source node to a multicast node is closer to delay bound, the
multicast nodes is given less priority to be a parent node of the
newly added node.
In our algorithm, the formula above is based on the indicator
function of QDMR algorithm. But our D(vi) and e(prec(vi),vj) is
quite different with QDMR as mentioned.D(vi) is the end-to-end
delay from the source node to node vi which is the neighbor node
of the tree. In QDMR algorithm, Delay(u) in its indicator function
means the delay from the source node to the multicast node u in
tree. And the cost of a newly added node v need add the cost of the
node which it via in the tree. Our algorithm does not need to give
priority to multicast nodes, and the cost of a new node v is not
related with the parent tree node in the algorithm. Instead, we
evaluate the cost of a new node by its delay and the energy cost
between the tree and it.
When select the next hop node, if the intersection of Ni and U isn't
null, choose the node with lower f(vi) to add to the tree. If nodes
has same f(vi) or the intersection of Ni and U is null (that means
the set of neighbor nodes of candidate nodes has no any multicast
node), choose the node with g(vi) lower to add to the tree.
4.3 Algorithm Implements
Input: network graph G, a source node s, the set of multicast nodes
M;
Output: a delay-bounded energy efficient multicast tree T.
Step 1. Initialization: let V(T) equals s , U equals M, NT equals
Ns.
Step 2. Based on the spectrum section mechanism in section 3.1,
source node s and candidate nodes select available spectrums to
neighbor nodes of NT.
Step 3. If U isn't null,
Zhou&Miao Expires - February 22, 2011 [Page 12]
Internet-Draft Link State Update Mechanism August 2010
If exists vi from NT, subject to the intersection of Ni and U that
is not null, select an appropriate vi from NT to minimize f(vi)
in formula above.
If has no node vi from NT, subject to the intersection of Ni and U
that is not null, select a appropriate vi from NT to minimize g(vi)
in formula above.
When choose the node to add to the tree, let V(T) a union set of
V(T), vi and the intersection of Ni and U,U equals M minus the
intersection of M and Ni, and update NT.
Step 4. If U isn't null, the algorithm stops.
Otherwise go to step 2.
Zhou&Miao Expires - February 22, 2011 [Page 13]
Internet-Draft Link State Update Mechanism August 2010
5. Security Considerations
The presence of the Reason header in a response does not affect the
treatment of the response.
Including such a header by an untrusted entity could adulterate the
reactions of the originating entities. E.G. sending back a cause
value "87" can cause an announcement within the PSTN/ISDN saying that
the call was rejected due to the Closed User Group service.
Therefore it is RECOMMENDED to include the Reason header information
in Responses only by trusted entities as it is described within
[RFC3325][7].
Zhou&Miao Expires - February 22, 2011 [Page 14]
Internet-Draft Link State Update Mechanism August 2010
6. IANA Considerations
This document does not have any implications for IANA.
7.References
[1] Ian, F., Won-Yeol L., Kaushik, R.C.:'CRAHN: Cognitive radio ad
hoc networks. Ad Hoc Networks', 2009, 7(5), pp.810-836.
[2] Chowdhury, K. R., Felice, M. D.:'Search: A routing protocol for
mobile cognitive radio ad-hoc networks', Computer Communications,
2009, 32, pp. 1983-1997.
[3] Haykin, S.:'Cognitive radio: brain-empowered wireless
communications', IEEE Journal on Selected Areas in Communications,
2005, 23, pp. 201-220.
[4] Akyildiz, I., Lee, W. Y., Vuran, M. C. and Mohanty, S.:'Next
generation dynamic spectrum access cognitive radio wireless
networks: A survey', Computer Networks, 2006, 50 (13), pp.2127-2159.
[5] Fujii, T., Karniya, Y., Suzuki Y.: 'Multi-band ad-hoc cognitive
radio for reducing inter system interference', 2006 IEEE 17th
International Symposium on Personal, Indoor and Mobile Radio
Communications, Piscataway, NJ, USA, 2006.
[6] Deying, L., Qin, L., Xiaodong H., Xiaohua J.:'Energy efficient
multicast routing in ad hoc wireless networks', Computer
Communications, 2007, 30 (18), pp. 3746-3756.
[7] Fujii, T.: 'Multi-band routing for ad-hoc cognitive radio
networks', Proceeding of the SDR 06 Technical Conference and
Product Exposition, 2006.
[8] Guo, S., Yang, O.: 'Energy-Aware Multicasting in Wireless
Ad Hoc Networks: A Survey and Discussion', Elsevier Computer
Communications, 2007, 30, pp. 2129-2148.
[9] Cheng, G., Liu, W., Li, Y., Cheng, W.: 'Joint on-demand
routing and spectrum assignment in cognitive radio network',
2007 IEEE International Conference on Communications, ICC'07,
Glasgow, Scotland, 2007, pp. 6499-6503.
[10] Xin, C., Ma, L., Shen, C. C.: 'A path-centric channel
assignment framework for cognitive radio wireless networks',
Mobile Networks Applications(Kluwer), 2008,13(5), pp .463-476.
[11] Wieselthier, J. E., Nguyen, G. D. and Ephremides, A.:'On the
Construction of Energy-Efficient Broadcast and Multicast Trees in
Wireless Networks', Proceedings of the IEEE INFOCOM, New York,
2000, 2, pp. 585-594.
[12] Kou, L., Markowsky, G. and Berman, L.:'A Fast Algorithm for
Steiner Trees', Acta Informatica, 1981, 15(2), pp. 141-145.
Zhou&Miao Expires - February 22, 2011 [Page 15]
Internet-Draft Link State Update Mechanism August 2010
Authors' Addresses
Xianwei Zhou
University of Science and Technology Beijing
NO.30 XueYuan Road, HaiDian, Beijing 100083
P.R China
Email: xwzhouli@sina.com
Zhou&Miao Expires - February 22, 2011 [Page 16]
Internet-Draft Link State Update Mechanism August 2010
| PAFTECH AB 2003-2026 | 2026-04-24 02:49:38 |