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