Amir Darehshoorzadeh

Llorenç Cerdà-Alabern
email: llorenc@ac.upc.edu

A New Multicast Opportunistic Routing Protocol for Wireless Mesh Networks

Keywords: Opportunistic routing, Multicast, Wireless

Opportunistic Routing (OR) has been proposed to improve the efficiency of unicast protocols in wireless networks. In contrast to traditional routing, instead of preselecting a single specific node to be the next-hop forwarder, an ordered set of nodes (referred to as candidates) is selected as the next-hop potential forwarders. In this paper, we propose a new multicast routing protocol based on OR for wireless mesh networks, named Multicast OR Protocol (MORP). We compare our proposal with the well known ODMRP Multicast protocol. Our results show that Multicast-OR outperforms ODMRP, reducing the number of transmissions and increasing the packet delivery ratio.

Introduction

Opportunistic Routing (OR) has been investigated in recent years as a way to increase the performance of unicast in multi-hop wireless networks. In OR, in contrast to traditional routing, instead of preselecting a single specific node to be the next-hop forwarder, an ordered set of nodes (referred to as candidates) is selected as the next-hop potential forwarders. More specifically, when the current node transmits a packet, all the candidates that receive the packet successfully will coordinate with each other to determine which one would actually forward the packet according to some criteria, while the other nodes will simply discard the packet. Previous research of OR mainly focused on developing various types of OR algorithms for unicast protocol and evaluating their performance. Multicast OR has received relatively few attention.

In this paper we propose a new multicast routing protocol based on OR. We will refer to our proposal as Multicast Opportunistic Routing Protocol, MORP. It opportunistically employs a set of forwarders to send a packet toward all destinations. The basic ideal of MORP is to form a candidates set to reach the destinations and based on the candidates which successfully receive the packet, selects a set of candidates as the forwarders to reach all destinations. Each forwarder is responsible for sending the packet to a subset of destinations. Indeed, based on the candidates that successfully receive the packet in each transmission, MORP builds a multicast tree on the fly using OR and forwards the packet through the tree.

The mesh based protocols in multicast routing are more reliable than the tree based protocols. We have compared our new multicast opportunistic routing protocol (MORP) with the well known ODMRP multicast mesh protocol [START_REF] Lee | On-demand multicast routing protocol[END_REF]. Our results show that Multicast-OR outperforms ODMRP, reducing the number of transmissions and increasing the packet delivery ratio.

The rest of the paper is organized as follows. Section 2 surveys the related work. In section 3 we describe ODMRP. Our proposal is described in section 4. In section 5 we show how our protocol works using an example. In section 6 both protocols are compared, and concluding remarks are given in section 7.

Related work

The majority of previous studies in opportunistic routing do not use it for multicast routing, and most of them are devoted to the selection of the candidates, the way of acknowledging packet reception and how to prevent, or at least reduce, duplicate transmissions.

Biswas and Morris proposed ExOR [START_REF] Biswas | Opportunistic routing in multi-hop wireless networks[END_REF][START_REF] Biswas | ExOR: opportunistic multi-hop routing for wireless networks[END_REF], one of the first and most referenced OR protocols. In [START_REF] Zhong | On selection of candidates for opportunistic anypath forwarding[END_REF][START_REF] Zhong | On the efficacy of opportunistic routing[END_REF] Zhong et al. proposed a new metric -expected any-path transmission (EAX)-that generalizes the single-path metric ETX [START_REF] De Couto | A high-throughput path metric for multi-hop wireless routing[END_REF] to an OR framework. They proposed a candidate selection and a prioritization rule based on it. They analyzed the efficacy of OR by using this metric and did a comparison using the link-level measurement trace of the Roofnet project [START_REF]MIT roofnet[END_REF]. In [START_REF] Dubois-Ferriére | Least-cost opportunistic routing[END_REF][START_REF] Dubois-Ferriére | Valuable detours: Least-cost anypath routing[END_REF] a distributed algorithm for computing minimum cost opportunistic routes, which is a generalization of the well-known Bellman-Ford algorithm, is presented. In [START_REF] Li | Optimal forwarder list selection in opportunistic routing[END_REF] the key problem of how to optimally select the forwarder list is addressed, and an optimal algorithm (MTS) that minimizes the expected total number of transmissions is developed. In previous works we have proposed a discrete time Markov chain to analyze the performance that may be achieved using opportunistic routing [START_REF] Cerdà-Alabern | On the performance modeling of opportunistic routing[END_REF], and in [START_REF] Cerdà-Alabern | On the maximum performance in opportunistic routing[END_REF] we have studied the maximum performance that may be achieved using OR.

There are few works about using OR in multicast. MORE [START_REF] Chachulski | Trading structure for randomness in wireless opportunistic routing[END_REF] is a MAC independent protocol that used both the idea of OR and network coding. It avoids duplicates transmission by randomly mixing packets before forwarding. It provides both unicast and multicast traffic. In [START_REF] Koutsonikolas | Pacifier: High-throughput, reliable multicast without "crying babies" in wireless mesh networks[END_REF] the source first creates the shortest path tree to reach all destinations based on the ETX of each link. Then the nodes not only receive packets from their father in the tree, but also can overhear packets from its sibling nodes. It uses random linear network coding to improve multicast efficiency and simplify node coordination. In [START_REF] Le | Opportunistic overlay multicast in wireless networks[END_REF] it is proposed an overlay multicast to adapt OR in wireless network.

ODMRP mechanism

The On Demand Multicast Routing Protocol (ODMRP) is a mesh based multicast protocol that establishes the routes and updates them by the source on-demand [START_REF] Lee | On-demand multicast routing protocol[END_REF][START_REF] Naderan-Tahan | Odmrp-lr: Odmrp with link failure detection and local recovery mechanism[END_REF]. While a source has data packets to send, it periodically broadcasts a Join-Query packet to the entire network. When a node receives a non-duplicate Join-Query, it stores the upstream node ID and rebroadcasts the packet. When the Join-Query reaches a multicast destination, the destination creates or updates the source entry in its Member-Table . While valid entries exist in the Member-Table, Join-Tables are broadcasted periodically to its neighbors.

When a node receives a Join-Table , it checks if its ID matches with the ID of the next node of one of the entries in the Join-Table . If it does, the node realizes that it is on the path to the source and thus is part of forwarding group. It then sets the FG-Flag and broadcasts its own Join-Table . The Join-Table is propagated by each forwarding group member until it reaches the multicast source. The forwarding group is a set of nodes in charge of forwarding multicast packets. A multicast receiver can also be a forwarding group node if it is on the path between a multicast source and another destination.

A multicast source can transmit packets to the destinations via the forwarding groups. When a node receives a data packet, it forwards the packet only if it is not duplicated and the FG-Flag for the multicast group of this node has not expired.

Multicast Opportunistic Routing Protocol

In this section we propose a new multicast routing protocol that we call Multicast Opportunistic Routing Protocol, MORP. Assume a network with N nodes and a multicast group M consisting of one source S and a set of destinations

D = {D 1 , D 2 , • • • , D n }. Denote C j,Di = {c 1 , c 2 , • • • , c n }
as the candidates set of node j to reach destination D i (c 1 the highest priority, and c n the least one), and C j,D as the multicast candidates set of node j to reach the destinations in D.

Before a transmission starts, each node in the network must compute C j,Di for each D i ∈ D, and store them in a Candidate-Table . This would be done using one of the candidates selection algorithms of the unicast opportunistic protocols that have been proposed in the literature (like ExOR [START_REF] Biswas | Opportunistic routing in multi-hop wireless networks[END_REF]). Each time the source S wants to transmit a packet, the following three-way-handshaking is carried out: First the source inserts its multicast candidates set (C S,D ), which is the union of all the candidates sets to reach D: Di∈D C S,Di , in the data packet and transmits it. Each candidate which successfully receives the packet sends back an acknowledgment (ACK). After a period of time (T Ack ) the source checks if it received ACKs from enough candidates to reach all destinations. If no enough ACKs were received, it retransmits the packet. This is done up to a maximum number of retransmissions (M AX ReT x ). Then the source selects the candidates responsible to forward the packet (forwarding set), and chooses to which destinations each of them must care. This process is explained in section 4.1. We will refer to the set of destinations chosen for each forwarder c j as its Bind-Destinations, and denote it as D cj . Note that the Bind-Destinations for the source node is the multicast destinations set: D S = D.

The source creates a set F with the IDs of the forwarding set and their Bind-Destinations. Then the source puts the set F in a control packet, that we will refer to as ForwardingPacket, and broadcasts it. Each candidate c j that receives the ForwardingPacket and its ID is included in it, would forward the packet following the same rules as the source, except that its Bind-Destinations (D cj ) will be used instead of D. This process is continued until the packet reaches the destinations.

Candidate Coordination

Upon transmitting a packet, the node collects the received ACKs in an Ack-Table . When T Ack expires, the forwarding set is computed as follows. If node j receives an ACK from one of the candidates in set C j,Di (D i ∈ D j ), it assumes that the packet can reach D i , and the candidate with the highest priority to reach D i which sent ACK is chosen as responsible to forward the packet toward D i . Recall that the highest priority candidate is the candidate which has the least expected number of transmission to the destination. On the other hand, if j does not receive any ACK from candidates in C j,Di (D i ∈ D j ), it assumes that the packet can not reach D i and retransmits the data packet. The node retransmits the data packet for at most M AX ReT x times or until receiving ACKs from enough candidates to reach all destinations.

If j finds that it is possible to reach all destinations in D j , then it sends the ForwardingPacket announcement. In ForwardingPacket, j determines which candidates would actually forward the packet, and to which destinations (Bind-Destinations). Note that for each destination only one candidate would be chosen to forward the packet, and the same candidate can be chosen to forward the packet to more than one destination. If the number of retransmissions of a data packet reaches M AX ReT x and there are not enough ACKs to reach all destinations, then the ForwardingPacket for the reachable destinations would be sent. The multicast candidates set for the source S to reach its Bind-Destinations set (D S ) is C S,D S = {B, D 2 , A}. When S wants to send a packet, it puts its multicast candidates set (C S,D S ) in the data packet and sends it. It sets the timer T ACK and waits for the ACKs from the candidates that have received the packet successfully. Assume that only the candidates A and B receive the data. Since this packet is not duplicated for A and B and also their IDs are included in it, they will send back an ACK to the source.

An Example of MORP

0.79 0.55 Cands Dest {D 1 } D 1 D 2 {A,S} D 3 {A,S} Dest D 1 D 2 D 3 Cands {B,S} {D 2 ,D 3 } {D 3 } D 1 A D 3
D 2 D 3 Cands {B} {D 2 ,A} {A,D 2 } Dest D 1 CandaiteTable (B) CandaiteTable (A) CandaiteTable (s)
Fig. 1: Example of MORP.

When S receives ACKs from A and B, it stores their ID in its ACK-Table. When the T ACK timer in the source expires, it uses the algorithm which has been described in section 4.1 to select and coordinate the forwarders. Since A and B sent ACK, S knows that for each at least one candidate received the data packet. Then S finds the best candidates that should forward the packet. The best candidates to reach D 1 , D 2 and D 3 are B, A and A, respectively. Thus, S creates the ForwardingPacket with A and B as the forwarders and, {D 2 , D 3 } and {D 1 } as the Bind-Destinations for A and B, respectively. Then S broadcasts the ForwardingPacket.

Upon receiving the ForwardingPacket, A and B know that they must forward the packet to {D 2 , D 3 } and {D 1 }, respectively. Let continue with node A. Node A creates its multicast candidates set for its Bind-Destinations ({D 2 , D 3 }), inserts the new multicast candidates set (C A,D A = {D 2 , D 3 }) in the data packet, starts the T ACK timer and forwards the packet. Note that when this timer expires, A just checks the ACKs from the candidates for the destinations in D A (I.e. D 2 and D 3 ). Node B does the same for the destination D 1 . Remark that one destination can act as a forwarder, if it is the best candidate for an other destination which sent ACK.

Note that when the data packets approach the destinations, the size of Bind-Destinations will decrease or remain unchanged. Thus, it is like MORP builds a tree on the fly, depending on the candidates that successfully receive the packet in each transmission.

Performance Evaluation

The simulation code has been implemented within the Global Mobile Simulation (GloMoSim) library [START_REF] Zeng | GloMoSim: A Library for Parallel Simulation of Large-Scale Wireless Networks[END_REF]. In the simulation we have modeled a network with different number of nodes (20 ≤ N ≤ 100) placed randomly within a square with diagonal equal to 500 m. Each simulation runs for 300 seconds of simulation time. The IEEE 802.11 Distributed Coordination Function was used as the medium access control protocol and the channel capacity was 2 Mbps. Each point in the plots was obtained averaging over 20 runs with different random node positions. The traffic generated by the source is Constant Bit Rate with 1 packet per second and 512 bytes of payload.

The number of multicast groups and sources is set to one in all scenarios. Destination nodes are chosen randomly. We have used different number of destinations (2 ≤ N umDest ≤ 10). Members join the multicast group at the start of the simulation and remain throughout the simulation. We have used ExOR as the candidate selection algorithm, fixing the maximum number of candidates ncand = 2 (see [START_REF] Darehshoorzadeh | Candidate selection algorithms in opportunistic routing[END_REF] for details).

For a more realistic simulation, we have used the shadowing propagation model with parameters β = 2.7 and σ dB = 6 dBs. With these parameters the the link delivery probability is approximately 40 % at the distance of 150 m (see our previous works [START_REF] Cerdà-Alabern | On the performance modeling of opportunistic routing[END_REF][START_REF] Cerdà-Alabern | On the maximum performance in opportunistic routing[END_REF][START_REF] Darehshoorzadeh | Candidate selection algorithms in opportunistic routing[END_REF] for details).

To evaluate the performance of MORP, we compare it with ODMRP. We have changed the way that ODMRP creates the routes to adapt it with the shadowing propagation model. We have evaluated both protocols as a function of number of nodes and number of destinations. The measures of interest are:

-Data Delivery Ratio: The ratio of data packets received by destinations to the number of data packets sent by the source. -Forwarding overhead: Total number of data packets transmitted over the total number of received packets. -Control Packets overhead: The ratio of total number of control packets transmitted to the total data packets delivered. -End-to-End delay: Average end-to-end delay of all data packets received by the destinations. We can see that using MORP with any number of M AX ReT x outperforms ODMRP. Even if MORP does not retransmit any data packet (MORP-ExOR(1)), it achieves about 70% packet delivery ratio, while for ODMRP the delivery ratio is about 60%. This can be explained because the construction of the routes in ODMRP are subject to the random losses that may have the Join-Query packets. On the other hand, routes in MORP depends on the selection of the candidates sets, which is done taking into account the delivery probability of the links.

Data Delivery Ratio

It is obvious that the more retransmissions are allowed in MORP, the higher will be the delivery ratio of the data packets. We can see that the differences Figures 3 and4 have been obtained respectively with a total number of nodes equal to N = 20 and N = 100, representing a low and high density network, and varying the number of destinations: N umDest = 2, 3, ..., 10.

Figure 4 shows that the delivery ratio of MORP-ExOR(1) for 8, 9 and 10 destinations is a bit less than ODMRP (about 2%, 3% and 5%, respectively). This comes from the fact that the more destinations are, the larger are the forwarding groups in ODMRP. Therefore the packet delivery ratio in ODMRP increases by increasing the number of destinations, however, at the cost of increasing too the forwarding overhead. Nevertheless, increasing M AX ReT x in MORP to 2 and 3, increases the delivery ratio to 82% and 88%, respectively, which outperforms the 72% obtained with ODMRP.

Forwarding Overhead

In this section we compare the forwarding overhead of MORP and ODMRP. Recall that we define the forwarding overhead as the total number of data packet transmissions by any node, over the total number of packets received by any destination.

Figure 5 shows the forwarding overhead varying the number of nodes in the case of 5 destinations. ODMRP periodically floods a data packet together with a Join-Query packet. I.e., it piggybacks the Join-Query information on the data packet periodically to update the membership information. For this reason the forwarding overhead of ODMRP is dominated by the flooding packets. Therefore, the higher is the node density of the network, the higher is the ODMRP forwarding overhead. On the other hand, the forwarding overhead of MORP is rather insensitive to the network density. This is because using opportunistic routing, as in MORP, only some useful nodes are selected as candidates to forward the packets, and thus, the number of forwarders is limited. Obviously, the higher is the number of retransmissions of data packets allowed in MORP, the higher will be the forwarding overhead. Nevertheless, figure 5 shows that in all cases the forwarding overhead of MORP is less than in ODMRP.

Figures 6 and7 show more results of the forwarding overhead, varying the number of destinations for a low and high dense network. These two figures depict that in a dense network MORP is less sensitive to the number of destination. This is because having more nodes in the network, allows the candidates selection algorithm to better choose candidates. On the other hand, as mentioned before, the forwarding overhead in ODMRP is closely related to the network density.

Note that in figure 6 the forwarding overhead for ODMRP with 10 destinations is about 1.27 and for MORP-ExOR(2) is about 1.16. Although these two values are close to each other, figure 3 shows that the delivery ratio of ODMRP for 10 destinations is about 60% while for MORP-ExOR(2) is about 81%, so, MORP outperforms ODMRP.

On the other hand, figure 7 shows that the forwarding overhead of ODMRP with 10 destinations is about 4.04, while in MORP-ExOR(1) it is about 0.90. As we have mentioned in section 6.1, in this case the delivery ratio in ODMRP was slightly larger than in MORP (see figure 4). We see now that this is at cost of having a forwarding overhead about 4.4 times larger than in MORP-ExOR(1).

Control Packets Overhead

In this section we compare the signaling overhead of MORP and ODMRP. To do so, we count as control packets for ODMRP the Join-Query, Join-Table and ACK packets, and for MORP the ForwardingPacket and ACK packets.

Figures 8 and9 show the control overhead varying the number of destinations for low and high density networks, respectively. As the number of destinations increases, the control overhead decreases in both protocols. In MORP, the higher is the maximum number of retransmissions (M AX ReT x ), the higher is the number of ACKs and ForwardingPackets. However, in figure 8 the control overhead of MORP in the case of M AX ReT x = 2 or 3 is only a bit higher than in ODMRP.

On the other hand, its packet delivery ratio is much better than in ODMRP (see figure 3). Additionally, figures 8 and 9 show that the control overhead of MORP with any number of retransmissions is much less sensitive to the number of destinations than in ODMRP. Recall that in MORP there is a three-way-handshaking each time a node transmits a data packet. Thus, as expected, the end-to-end delay in MORP is higher than in ODMRP. Comparing figures 10 and 11 we can see that end-to-end delay decreases in a dense network for ODMRP and MORP-ExOR(1). This is because in a dense network both protocols can find better routes. For MORP-ExOR(2) and MORP-ExOR(3), delays increase with the number of destinations. This comes from the fact that candidates set may be different to reach different destinations. Thus, more retransmissions are required until all necessary candidates receive the data packets.

End-To-End Delay

Conclusion

In this paper we propose a new multicast protocol based on opportunistic routing that we call Multicast Opportunistic Routing Protocol, MORP. MORP uses a three-way-handshaking, where the node sending the data packet chooses the forwarders and a subset of destinations to which they have to send the data packets.

We have compared our protocol with the well known mesh-based multicast routing protocol called ODMRP. In our simulations we have measured the packet delivery ratio, forwarding overhead, control overhead and end-to-end delay of both protocols.

Simulations results show that MORP outperforms ODMRP in terms of packet delivery ratio and forwarding overhead. The end-to-end delay of MORP is higher than in ODMRP, but still acceptable for real time applications. We conclude that MORP, and opportunistic routing in general, is a convenient technique to be used in multicast protocols for wireless mesh networks. This work was supported by the Spanish government and Generalitat de Catalunya through projects TIN2010-21378-C02-01 and 2009-SGR-1167, respectively, and by the European Commission through the NoE EuroNF.

Figure 1

 1 Figure 1 shows an example of MORP. The destinations set is D = {D 1 , D2 , D 3 } and the source of this multicast group is S. The table under each node represents its Candidate-Table to reach the destinations.The multicast candidates set for the source S to reach its Bind-Destinations set (D S ) is C S,D S = {B, D 2 , A}. When S wants to send a packet, it puts its

Figure 2

 2 Figure 2 shows the packet delivery ratio varying the number of nodes, but maintaining the diagonal of the area of the network equal to D = 500 m. For each point in the figure we have added error bars at 95% confidence interval. In this figure the number of destinations have been set to 5 (N umDest = 5). The results are shown varying the maximum number of retransmission (M AX ReT x ) of MORP. The legend MORP-ExOR(n) in figure 2 refers to MORP with M AX ReT x = n.We can see that using MORP with any number of M AX ReT x outperforms ODMRP. Even if MORP does not retransmit any data packet (MORP-ExOR(1)), it achieves about 70% packet delivery ratio, while for ODMRP the delivery ratio is about 60%. This can be explained because the construction of the routes in ODMRP are subject to the random losses that may have the Join-Query packets. On the other hand, routes in MORP depends on the selection of the candidates sets, which is done taking into account the delivery probability of the links.It is obvious that the more retransmissions are allowed in MORP, the higher will be the delivery ratio of the data packets. We can see that the differences

Fig. 3 :Fig. 4 :Fig. 5 :

 345 Fig. 2: Delivery ratio for 5 destinations

Fig. 6 :

 6 Fig. 6: Forwarding overhead varying the number of destinations. N=20.

Fig. 7 :

 7 Fig. 7: Forwarding overhead varying the number of destinations. N=100.

Fig. 8 :

 8 Fig. 8: Control overhead varying the number of destinations. N=20.

Fig. 9 :

 9 Fig. 9: Control overhead varying the number of destinations. N=100.

Figures 10 and 11

 11 Figures 10 and 11 show the average end-to-end delay for different number of destinations with N = 20 and N = 100 nodes, respectively.Recall that in MORP there is a three-way-handshaking each time a node transmits a data packet. Thus, as expected, the end-to-end delay in MORP is higher than in ODMRP. Comparing figures 10 and 11 we can see that end-to-end delay decreases in a dense network for ODMRP and MORP-ExOR(1). This is because in a dense network both protocols can find better routes. For MORP-ExOR(2) and MORP-ExOR(3), delays increase with the number of destinations.

Fig. 10 :

 10 Fig. 10: End-To-End delay varying the number of destinations. N=20.

Fig. 11 :

 11 Fig. 11: End-To-End delay varying the number of destinations. N=100.

  2 , D 3 } and the source of this multicast group is S. The table under each node represents its Candidate-Table to reach the destinations.


Liang Yan
email: yanliangtju@gmail.com

Hongbo Guo
email: hongbog@ece.ubc.ca

Min Chen
email: minchen@ieee.org

Chunming Rong
email: chunming.rong@uis.no

Victor Leung
email: vleung@ece.ubc.ca

Mobile Agent Code Updating and Authentication Protocol for Code-centric RFID System

Keywords: RFID, Code-centric, Code updating and authentication

Traditional identification-centric RFID system (IRS) is designed to provide services of object identification/tracing/locating, but it has some shortcomings when encountering a dynamic environment in which the status of the systems and the service requirements of users/objects may change continuously. Very recently a new Code-centric RFID system (CRS), which is far different from the traditional IRS, is proposed to provide on-demand fashion code re-writing and to suit for more flexible user-centric applications. However, at the current stage the there is no secure and efficient scheme to manage the mobile code updating and authentication process in CRS. In this paper, a new scheme is proposed to provide efficient and dynamic mobile agent code updating management. In addition, to prevent the CRS system form possible attacks from malicious users, an IDPKC-based digital signature generation and authentication protocol is proposed.

Introduction

Radio frequency identification (RFID) is a wireless communication technology for automatic object identification, and it has been receiving more and more attention [START_REF] Nath | RFID Technology and Applications[END_REF]9]. In general, an RFID network consists of some readers and many low-cost tags. Each reader is connected with a certain data base that storages the information of the objects. Each RFID tag is programmed with a unique identification (ID). The ID is the information of some object, and the tag is attached to the object. The ID points to some storage of the database. The reader communicates with the tag in a wireless way and collecting its ID. Then the object is recognized by the reader checking the data base that the reader is connected with. RFID tags can be categorized into passive, active, and semi-active (or hybrid) tags, depending on whether they require batteries for operation. On the other hand, RFID tags can also be distinguished depending on their data storage capability: read-only tags or read-and-write tags.

The current RFID system, referred as traditional identification-centric RFID system (IRS) is designed to provide such services as object identification, tracking or locating. In a dynamic scenario, IRS presents apparent limits. To deal with such dynamic circumstances, very recently a Code-centric RFID system (CRS) [START_REF] Chen | Code-Centric RFID System Based on Software Agent Intelligence[END_REF] is proposed to provide a smart on-demand action for different objects in different situations. As a new concept and new system, the current CRS need some new secure and efficient scheme to manage its mobile codes updating and to provide mobile codes authentication.

The rest of this paper is organized as follows. In Section II the code-centric RFID system (CRS) is reviewed and compared with the traditional IRS RFID system, where particularly the current mobile agent code updating process in CRS is discussed. In Section III the proposed new mobile agent code updating scheme is introduced. In Section IV we discuss how to use an IDPKC-based digital signature generation and verification method to protect the system from security. Section VI concludes this work.

Agent based Code-centric RFID system

This section first describes the current CRS system, and then demonstrates possible security threats onto CRS.

Introduction of Code-centric RFID System (CRS)

The existing RFID system can be summarized as identification-centric (IRS) RFID system. Generally, it utilizes passive information about the object, i.e., the ID information stored in the tag. Then the corresponding action decision is made upon a pre-established database. In IRS RFID system, the applications mainly help answer "where" and "what" questions, such as "where is the object (e.g., a person)" and "who is the person (e.g., the tag serves as electronic passport, and the person's age or marriage status is recorded in the tag memory)". However, the static database cannot be updated in a real-time way for new object types. When information changes, an object database synchronization problem occurs. Thus, the object's profile database must be setup to allow for interactions between a RFID tag and a profile database before the tag is manufactured. If an emergent situation appears and the network access from the reader to the database is blocked, the object identification function of RFID will be also blocked. As a solution for such problems existing in IRS, CRS [START_REF] Chen | Code-Centric RFID System Based on Software Agent Intelligence[END_REF] incorporates code information that is dynamically stored in the RFID tag. It facilitates on-demand actions for different objects in different situations. It is the mobile agent codes that are encoded in the RFID tags, while not simply the static ID. Mobile agent specifies up-to-date services. Furthermore, a high-level language for coding mobile agents is stored in the RFID tags, and the agents will be interpreted by a corresponding middleware layer in the RFID reader. By using this mobile agent-based RFID tag, an object indicates the system to intelligently execute actions in response to the occurrence of specific situations. When the service requirements are put into an RFID tag in one location, the target would be realized in another location through code-centric processing. Fig. 1 shows CRS concept, where CRS extends RFID message format for the tag. In addition to the traditional tag data (identification information or ID), a mobile agent (code) is stored in the tag. The mobile code will be changed or re-written in an on-demand fashion so as to provide on-demand quality of service. Usually, the goal of the updating action is some operation or adjusting according to the changing surrounding environment. Particularly when the tag is attached onto a non-human object, this object will have no intelligence to update code by itself. As a result, some other malicious devices or attackers get opportunities in the updating, and the security problem emerges in the updating stage. To sum up, a security mechanism for the updating process of the CRS agent based tag is a critical issue.

Problems about Mobile agent code updating

One of the most important characteristics of CRS system is that the memory of each tag in this system consists of two parts: original fields and extension fields as shown in Fig. 1. Original fields include identification information and description information, which will not be changed. Extension fields that include code priority and mobile agent can be re-written in an on-demand fashion to provide on-demand quality of service.

There are three kinds of code updating modes: passive mode, active mode, and hybrid mode.

(1) Passive Mode: In RFID systems, the tag can be generally attached to human and non-human objects (e.g., product, animal, etc.). Non-human objects are not intelligent enough to update agent codes by themselves. (2) Active Mode: If the object is a human being, then he/she may have specific requirements on service types and qualities. These users can update the codes actively by themselves through portable RFID readers. (3) Hybrid Mode: This is the combination of both passive mode and active mode. In current CRS system,there is no security scheme to manage this codes updating procedure. As a result, there exist some possible security threats in CRS system.

(1) Denial of service attack Because RFID tag has limited memory and there are no efficient schemes to manage mobile codes updating, malicious users can launch denial of service attack by writing a large amount of mobile codes into tag memory. If the memory is full, new updating codes from tag user cannot be written into tag memory anymore.. (2) Unauthorized access attack In a CRS system, updating mobile codes may come from different readers. The system must ensure that readers do not update and modify the mobile code if they have no authorization to access to the mobile codes. Otherwise, malicious attackers are able to use a reader to write malicious codes into tag memory or modify the original code. Malicious codes like a virus may cause system failure, whereas modified codes with wrong information may bring loss or inconvenience for tag owners.

Mobile agent code updating scheme

In this part, a modified tag data structure and a proposed mobile agent code updating procedure is proposed to solve the problems in the current CRS system.

Modified tag data structure

In order to manage mobile agent code updating procedure, a new RFID tag data structure is proposed. In this new tag data structure, a code update time and a digital signature are added for each mobile agent code as shown in Fig. 2. Digital signature will be generated from this mobile agent code by tag owner. The detail of digital signature generation will be introduced in part IV.

Mobile Agent code updating procedure

When a new mobile agent code comes if the tag has enough free memory for this code, this code will be written into tag's memory. On the other hand if there is not enough free memory, the code may be discarded, not written into tag memory, and not sent to the code information manager. In this section, we propose a new scheme to manage this mobile agent code updating process as shown in figure 3. Given that tags are usually low-cost and without enough computation resource to perform digital signature verification, the proposed mobile agent code updating management scheme are designed to be performed by RFID reader.

(1) The Reader reads all the tag information from tag memory, which includes both the original fields and extension fields. (2) The Reader checks if there is enough free memory for the new coming code. If yes, reader will write this code into memory of this tag. (3) If there is not enough free memory for this new code, the reader will check the codes stored in the memory one by one and erase the codes that are not from this tag's owner. Here the code checking process is a code authentication process, which recognizes whether this code is from owner of this tag. An IDPKC-based digital signature generation and verification scheme is used. (4) If there is still not enough free memory for the new code, reader will compare the processing priority and update time of all codes to make sure that codes with higher processing priority and new update time will be stored in the tag memory. By comprehending this new mobile agent code updating procedure into the current CRS system, the code from the right tag owner will be kept in tag's memory with high processing priority and new update time. From Fig. 4, we see that when a reader reads the tag memory, the identification and description data will be sent to the passive information manager. The mobile agent code is forwarded to the code information manager, which will deliver the agent to the middleware layer for interpreting. By way of this agent code updating protocol, the new code from the tag owner is appropriately updated. But it cannot make sure that all codes are from the tag owner. In order to avoid this, each code should be authenticated when it is read. A fundamental technique for demonstrating the authenticity and integrity of a mobile code is to use a signing code. Typically, mobile code signing involves a public key cryptography. In a Public Key Infrastructure (PKI) system, the public keys are made publicly available by using of certificates. To sign a code, the code should first pass through a hash function to generate a code digest, and then the digital signature is generated by encrypting this code digest with the singer's private key. Because both the private key and the code digest are unique, this digital signature authenticates not only the origin of the code but also the code integrity. In a CRS system, each mobile code has a digital signature and this digital signature will be generated by the owner of the tag and be written into the tag memory together with this mobile code. Although this traditional PKI system is widely used in some mobile agent systems [START_REF] Gray | Agent Tcl: A Flexible and Secure Mobile-Agent System[END_REF][START_REF] Karjoth | A Security Model For Aglets[END_REF][START_REF] Foster | Security in Mobile Agent Systems[END_REF][START_REF] Tardo | Mobile Agent Security and Telescript[END_REF], it has some drawbacks in certificates and public key management and is not suitable for this CRS system. In this paper, an Identity-based Public Key Cryptography (IDPKC) is adopted to provide digital signature generation and verification service in CRS system.

IDPKC-based digital signature and verification

IDPKC-based digital signature and verification

In a CRS system, a digital signature scheme is adopted to authenticate the integrity of a mobile agent code and to verify whether a mobile agent code is from the tag owner. Normally, a digital signature scheme typically employs a type of public key cryptography and consists of three parts. Each part is described by an algorithm: (1) Key generation algorithm that generates a private key and a corresponding public key for the user. (2) Signing algorithm that generates a digital signature from a digital message with user's private key. (3) Signature verifying algorithm that authenticates the received message with message, user's public key and digital signature. In [START_REF] Shamir | Identity-based cryptosystems and signature schemes[END_REF], an IDPKC-based signature generation and verification scheme is introduced. The key generation center uses sender's identity to generate a signature generation key and pass this key to sender. Digital signature will be generated using this signature generation key and this message. This digital signature can be verified with the signature verification key that is generated from sender's identity.

Identity-based digital signature and verification in CRS

In a CRS system, an IDPKC-based digital signature generation and verification scheme is used for the reader to authenticate the integrity of a mobile agent code and if a mobile agent code is from the right tag owner or not. The process of this IDPKCbased digital generation and verification is shown in Fig. 5. Compared with traditional PKI system, the advantages of using IDPKC-based digital signature generation and verification scheme in a CRS system are:

(1) One important advantage of IDPKC system is that if there is only finite users in the system, the private key generator can be destroyed after all users have been issued with their private keys. (2) Scalability becomes a significant concern with a growing number of RFID tags whose associated information needs to be stored in the database. Failures in the database and/or networking infrastructure may render the system unusable. Therefore, in a CRS system, in order to realize the system decentralization, the mobile code processing is performed locally by an interpreter attached to the RFID reader and the RFID reader does not need to be connected with the backend database. (3) One inherent disadvantage with PKI is the management of the certificate and associated key. Fortunately IDPKC can overcome this problem because it allows a user to generate the public key of any user without having to search a directory or request a copy of its key from the user..

(4) Another advantage of using IDPKC for digital signature verification is the system can develop more lightweight implementations at the reader. This is because the reader need not store separate certification, identification and keying information to generate the verification key. (5) IDPKC offers a useful feature by adding additional information to the tag identity. For example, a tag user can specify a code expiration data and use this timestamp and tag identity to generate the private key and public key.

Conclusion

In this paper, we first reviewed the traditional identification-centric RFID system (IRS), some disadvantages of IRS in dynamic environments, and a recently emerged code-centric RFID system (CRS). Based on the review, we analyzed some mobile updating modes and their problems with current mobile code updating procedure in a CRS system. To solve these problems, a new mobile code updating protocol is proposed. By way of this proposed protocol, CRS guarantees that the mobile codes from the right tag owner or from the tag owner with higher processing priority not be discarded, especially when free tag memory is not enough for a new coming mobile code. In order to prevent the system from being attacked by malicious users and protect the tag owner's rights and interests, we propose the code authentication adopts singed code. In the IDPKC-based digital signature generation and authentication scheme, any RFID reader can generate the verification key from the tag identity and it is more suitable for our CRS system compared with traditional PKI based approach.

Fig. 1 .

 1 Fig.1. Extended RFID message in CRS

Fig. 2 .

 2 Fig.2. Modified RFID tag data structure in CRS

Fig. 3 .

 3 Fig.3. Mobile Agent code updating procedure

Fig. 4 .

 4 Fig.4. Functional components of CRS

Fig. 5 .

 5 Fig. 5. IDPKC-based digital signature generation and verification in CRS system (1) PKG generates a master-key and public Params and sends public Params to the readers. (2) Tag owner sends the tag identity (TagID) to PKG. (3) PKG generates a private key for this TagID and it to the tag owner. (4) Tag owner hash mobile agent code to generate a hash code. (5) Tag owner uses the private key to encrypt the hash code and gets a digital signature for this mobile agent code. (6) Tag owner sends this mobile agent code together with its digital signature to a RFID reader. (7) Reader writes this mobile agent code and its digital signature into the memory of the tag. (8) Reader reads the TagID and signed code from tag memory. (9) Reader uses TagID and Public Params to generate the public key of this tag and uses this public key to verify the digital signature.


Attahiru S Alfa

Vicent Pla

Jorge Martinez-Bauset

Vicente Casares-Giner

Discrete time analysis of cognitive radio networks with saturated source of secondary users

The strategy used for sensing in a cognitive radio network affects the white space that secondary users (SUs) perceive and hence their throughput. For example, let the average time interval between consecutive sensing be fixed as τ . There are several possible ways to achieve this mean value. The SU may sense the channel at equal intervals of length τ or sense it at randomly spaced intervals with mean value τ and guided by, for example, geometric distribution, uniform distribution, etc. In the end the strategy selected does affect the available white space and throughput as well as the resources spent on sensing. In this paper we present a discrete time Markov chain model for cognitive radio network and use it to obtain the efficiency of sensing strategies. The system studied is one in which we have a saturated source of secondary users. and the system give preemptive priority to primary users. These assumptions do not in any ways affect our results.

Introduction

Cognitive radio (CR) has been proposed as one approach to deal with the limited unlicensed spectrum availability. Most of the licensed spectrum are not fully utilized most of the time. Capturing the unused time slots, which are known as spectrum holes, on these available spectrum and using them efficiently is what CR is about. The FCC has approved the use of these licensed spectrum by unlicensed users when there is a spectrum hole, subject to a limited interference to the licensed users [2]. This spectrum hole we refer to as white space. The key to success for CR consists of effective and efficient sensing of the channels by the secondary users (SU), the unlicensed users, to detect white spaces when they occur. A decision making process then follows the sensing, based on the outcome of the sensing exercise.

Each time an SU senses the channels, it expends some resources. A lot of resources are wasted if too many sensing episodes result in unsuccessful capture of a white space. On the other hand, infrequent sensing could lead to the inability to detect available white space to transmit messages, resulting in long delays. In the end a very good balance regarding the sensing strategy is critical in order to detect white space early enough in the sensing period with minimum sensing frequency. Despite advance research in the area of CR, little is known about theoretically founded method for determining the optimal sensing strategy. In this paper we develop a sensing strategy based on a discrete time Markov chain.

If we observe a PU channel, it is either busy or idle. The idle periods are the holes referred to as white space. The busy and idle periods form an alternating sequence of events which may be correlated. An SU sensing this channel at some time points either finds the channel busy or idle. When a sensing occurs during the idle time of a PU then the SU is able to effectively utilize the remaining idle time, which we call the effective white space. The ideal sensing strategy is one that results in the SU capturing most of the white space when it finds the channel to be idle, i.e. the one that can minimize the difference between the lengths of the white space and the effective white space, while keeping resource utilization to a minimum. As pointed out by Yücek and Arslan [9], selection of sensing parameters result in trade off between sensing frequency, reliability and the actual characteristics of the PU channel usage. So the aim in CR networks is to plan the sensing in order to utilize high proportion of the white space.

The sensing strategy affects the length of the effective white space and hence determines the efficiency of the strategy. The often made assumption is that sensing should be done periodically and the issue is determining the interval between the sensing times [START_REF] Ghasemi | Spectrum sensing in cognitive radio networks: requirements, challenges and design trade-offs[END_REF]. However, there are no documented analytically based studies supporting the idea of using constant interval between sensing times as the optimal strategy. In addition, most models that have been developed for studying cognitive radio networks usually assume that the durations of both the busy and idle times are governed by the exponential distributions, see for example Lee and Akyilidz [6]. Geirhofer et al [START_REF] Geirhofer | Dynamic spectrum access in the time domain: Modeling and exploiting white space[END_REF] were among the earlier researchers to show from measurements that the idle time duration was more of a lognormal distribution. This was further confirmed by Wellens et al [8] who showed that the idle time duration has lognormal distribution for long durations and geometric distribution for the short ones. Most of the previous works also ignored the possible correlation between the busy and idle times, even though logically one would expect some correlation to exist between the two intervals. Hoang et al [5] did consider such correlation by introducing a two-state Markov chain to capture this aspect. Our aim in this paper is to determine how to arrive at optimal sensing strategy under any cognitive radio network conditions, using representative mathematical models. We do this by representing the PU busy and idle periods as alternating Markov phase renewal process [START_REF] Alfa | Queueing Theory for Telecommunications: Discrete Time Modelling of a Single Node System[END_REF] and develop a model to determine effective white space under different sensing strategies. This Markov phase renewal process allows the busy and idle times durations to assume a wide variety of distributions and also captures a much broader correla-tion aspects of the two intervals. By sensing strategies we imply using different statistical distributions of intervals between sensing time points for a fixed mean sensing interval. From this we obtain the sensing efficiency which is practically the ratio of the lengths of the effective white space to that of the white space. The model presented in this paper is used as a base work for studying a cognitive radio network in detail in our future work.

The rest of the paper is organized as follows. Section 2 introduces the model of the channel as seen by the SU, i.e., the pattern of channel busy periods and white spaces. The behavior of the CR system is described in Section 3. Then a Markov chain model of the system is developed and some performance measures are derived. In Section 4 we present a numerical study that evaluates the efficiency of different sensing strategies and the adjustment of their parameters. Finally, the paper is concluded in Section 5.

Characteristics of the channel

We observe our system in discrete time points 0, 1, 2, • • • . Consider a single communication channel used by a primary user, PU. Here the PU refers to the whole set of PUs which might use the channel under consideration. This channel is either in use (busy) or not in use (idle). Consider a discrete time Markov chain (DTMC) with state space {1, 2,

• • • , n b , n b + 1, • • • , n b + n i },
D i 1 + d ib 1 = 1,
where 1 is a column vector of ones. Based on this, the channel is either busy or idle according to the following transition matrix

D = D b d bi d ib D i . (1)
Let π = [π b , π i , ] be the stationary distribution, where π = πD and π1 = 1. This is a realistic representation of the channel behavior under general conditions.

The behavior of the PU can be seen as an alternating sequence of busy and idle periods (white spaces). The duration of a white space follows a phase type distribution (ω, W ) [START_REF] Alfa | Queueing Theory for Telecommunications: Discrete Time Modelling of a Single Node System[END_REF], where ω = (π b d bi 1) -1 π b d bi and W = D i . Therefore, σ k , the probability that the duration of uninterrupted white space is at least k time slots, is given as

σ k = 1 π b d bi 1 π b d bi D k-1 i 1 , k ≥ 1,
and, L w , the average duration of this white space is

L w = ∞ k=1 σ k = 1 π b d bi 1 π b d bi (I -D i ) -1 1 .

Model of the Cognitive Radio System

In this section we consider the actions of the SUs and how they interact and/or co-exist with the PUs. As in the primary system, by SU we refer here to the whole set of SUs which might use the channel under consideration. Moreover we assume that all those SUs are coordinated. The SU can be in one of the following three situations: sleeping, sensing or transmitting.

Sleeping The duration of the sleeping state is represented by the phase type distribution (δ, L) of order n . After waking up the SU proceeds to the sensing cycle. Sensing In the sensing cycle the SU takes a series of measurements of the channel state in consecutive time slots. The maximum number of such measurements in a sensing cycle is described by the phase type distribution (β, S), of order n s . If the outcome of any of the measurements is busy the sensing cycle is aborted and the SU goes back to sleep. Otherwise, if all measurements in the series find the channel idle, the SU proceeds to transmit. Transmitting The SU will transmit for a maximum number of slots represented by the phase type distribution (α, T ) of order n t . Depending on the sensing characteristics and capabilities of the SU, it may, or may not, be able to detect the arrival of a PU during the transmitting state. In this study we assume that the SU interrupts immediately the transmission upon the arrival of a PU.

Let the source of SUs be saturated, i.e. there is always an SU looking for white space. We can easily consider the case of a non-saturated system. We also assume that the system gives preemptive priority to PUs over the SUs. In a separate paper later on we consider the case where we allow the system to keep track of the phase at which the SU was interrupted, and also relax the assumption about the source of SUs being saturated.

The time necessary to obtain a sensing measurement cannot be neglected compared to the transmission time of a data unit. The duration of a slot represents the length of time required to obtain a sensing measurement. The outcome of the sensing measurement performed during a slot is known at the end of the slot. In setting the result of the measurement we adopt a conservative approach: if any PU activity occurred during the slot the channel state will be deemed as busy, in other words the measurement undertaken during the time slot [n, n + 1) will yield idle as the result only if the PU was idle at both t = n and t = n + 1.

Despite the fact that now the sensing time cannot be neglected, it is assumed that sensing is carried out while the SU is transmitting. It could account for those situations where the SUs are equipped with required hardware to transmit and sense simultaneously or collaborative sensing is carried out and the gathered information is shared instantaneously among SUs. If we let the states of this system be classified as [(PU busy, SU sleeping), (PU busy, SU sensing), (PU idle, SU sleeping), (PU idle, SU sensing), and (PU idle, SU transmitting)], then we have the following discrete time Markov chain (DTMC),

P =       D b ⊗ L D b ⊗ l d bi ⊗ L d bi ⊗ (lβ) 0 D b ⊗ δ 0 d bi ⊗ δ 0 0 d ib ⊗ L d ib ⊗ l D i ⊗ L D i ⊗ (lβ) 0 d ib ⊗ ((S1 + s)δ) 0 0 D i ⊗ S D i ⊗ (sα) d ib ⊗ (1δ) 0 0 0 D i ⊗ (T + tα)      
, where ⊗ denotes the Kronecker product[1, page 30] and l, s and t are the absorption probability vectors associated with sleeping, sensing and transmitting phases, respectively. This transition matrix captures the full behavior of this saturated system with preemptive discipline. Specifically, the throughput of the SUs can be extracted from this matrix after minor algebraic manipulations.

Performance Measures

We can now write the transition matrix as

P =      
P 11 P 12 P 13 P 14 0 P 21 0 P 23 0 0 P 31 P 32 P 33 P 34 0 P 41 0 0 P 44 P 45 P 51 0 0 0

P 55      
, where the block elements P ij are as defined in the detailed matrix P .

Provided the Markov chain described by the matrix P is irreducible then it has a stationary distribution π given as π = πP , π1 = 1, where π = [π 1 , π 2 , π 3 , π 4 , π 5 ].

Effective white space exceeds K. Our interest here is in the state set 5. We are interested in the probability that when the SU is finally able to transmit it has at least K uninterrupted units of time slots for transmission without interfering with the PU. Let us further group the states as A = {1, 2, 3, 4} and B = {5}, and write the matrix P as

P = P A,A P A,B P B,A P B,B ,
where P B,B = P 55 , and π B = π 5 and the rest of the matrices and vectors are easily inferred from these two. Then, p K , the probability that the length of an effective white space is at least K time slots can be written as

p K = 1 π A P A,B 1 π A P A,B P K-1 B,B 1 . ( 2
)
Mean effective white space. From (2) it readily follows that, L e w , the mean effective white space is given as

L e w = ∞ k=1 p k = 1 π A P A,B 1 π A P A,B (I -P B,B ) -1 1 .
Efficiency of the sensing strategy. We asses the efficiency of the sensing strategy from two different viewpoints:

-The effectiveness in using available white spaces for transmission; we represent this by η t and it is given as

η t = π 5 1 π 3 1 + π 4 1 + π 5 1 ,
which represents the fraction of slots available for SU transmission where it effectively transmits. -The effectiveness in saving unnecessary measurements by remaining in the sleeping state while the PU is busy; we represent this by η s and it is given as

η s = π 1 1 π 1 1 + π 2 1 ,
which represents the fraction of slots the SU is in sleeping state while the PU is busy. Saving as much measurements as possible, i.e. a high value of η s , is a desirable characteristic of the sensing strategies as it means saving energy or being able to use the radio to sense other channels.

Obviously, we have that 0 ≤ η t , η s ≤ 1. Besides, there is trade-off between these two efficiency measures. Short sleeping periods leads to high values of η t and low value of η s , and vice versa. We summarize both measures into an overall efficiency factor, η, as

η = αη t + (1 -α)η s ,
where 0 ≤ α ≤ 1. Note that η ≤ α max(η t , η s )+(1-α) max(η t , η s ) = max(η t , η s ), and analogously η ≥ min(η t , η s ). Hence, 0 < min(η t , η s ) ≤ η ≤ max(η t , η s ) < 1.

Experimental Results and Discussion

In this section we use the model to assess different types of sensing strategies. By sensing strategies we imply that, given a fixed mean sleeping interval, we want to design rules for sleeping that can achieve this selected mean interval.

We then assess which one of them performs the best. Specifically, we consider the following: deterministic, uniform, geometric and negative binomial (or Pascal). All these distributions can be represented by discrete phase type distributions [START_REF] Alfa | Queueing Theory for Telecommunications: Discrete Time Modelling of a Single Node System[END_REF]. For the channel occupancy we use the model proposed in [7], which is shown to exhibit a self-similar behavior over a finite but wide enough range of timescales. Thus the block-matrices in (1) are given as The SU is in the transmitting phase for a maximum number of slots that follows a geometric distribution with mean value equal to 10. The maximum duration of a sensing cycle is deterministically set to 2 slots. In what follows we study the impact on the efficiency of varying the distribution type and the mean value for the duration of the sleeping phase.

D =         1 - n-1 k=0 1 a k 1 a 1 a 2 • • • 1 a n-1 b a 1 -b a b a 2 1 -b a 2 . . . . . . b a n-1 1 -b a n-1         , (3)
The impacts of the sensing strategy on both η t and η s are shown in Fig. 1. As expected by spending longer intervals in the sleeping state η t decreases and η s increases. Note however that η s increases abruptly at first, reaches rather high values and then levels off. Comparatively, the counter decline in η t occurs more gradually. The observed trends suggest that weighted efficiency (η) will attain a peak for short durations of the sleep period, as it is confirmed in Fig. 2. We also observe that as the channel gets more loaded the value of the optimal efficiency decreases and, more importantly, the proper adjustment of the sleep duration becomes a more sensitive issue.

In the comparison of different distributions for the sleep duration (keeping constant the mean value) it was observed that lower variability results in better efficiency -in all our experiments the deterministic distribution yield the highest overall efficiency-although differences are very small. The efficiency trade-off is also explored in Fig. 3 where η s and η t are displayed one versus the other. There are three bundles of curves that correspond to different channel utilizations (high, ρ P U = 0.8; moderate, ρ P U = 0.5; low, ρ P U = 0.2). The four curves in each bundle correspond to the four distributions of the sleep time, and along each curve the mean sleep time is varied. For a given value of the mean sleep time the value of η s is approximately the same independently of the channel load. However, as the load increases the curves stretch on the horizontal dimension, which means that a higher cost in terms of η t has to be paid to achieve a high value of η s .

The impact of the sensing strategy on the distribution of the duration of an effective white space is shown in Fig. 4. Other experiments -not shown here due to the lack of space-shown that differences across distributions were not noticeable for this type of representation. Thus on Fig. 4 we only represented the results for the deterministic distribution of sleep length. For each channel load two different lengths are represented: the one at which the weighted efficiency peaks in Fig. 2 and another one which is four times larger.

Conclusion

In this paper we have established, through an analytical model, that constant interval sensing is more effective than all the other strategies tested. This is as expected. The model used is designed for general application for studying the behavior of cognitive radio networks. In the next stage of our work we plan to use this model to study the waiting time for an SU to obtain a particular length of white space and several other performance measures.

  wit the transition matrix representing this DTMC given as D. Let the PU busy (b) and idle (i) conditions be represented by the sets of states {1, 2, • • • , n b } and {n b +1, • • • , n b +n i }, respectively. Further define the substochastic matrices D b and D i , to represent the transitions within the busy and idle periods, respectively, and d bi to represent transitions from busy to idle and d ib from idle to busy. The D b and D i are substochastic matrices of orders n b and n i , respectively. By these definitions we have D b 1 + d bi 1 = 1 and

Fig. 1 .

 1 Fig. 1. Efficiency of different sensing strategies. Lightly loaded channel, ρP U = 0.2.

  where n, a and b are the parameters of the model. The value of n determines the range of time-scales where the process can be considered as self-similar. Once the value of n is set the values of a and b are obtained so as to fit the utilization factor of the channel ρ P U = (1-1/b)/(1-1/b n ), and the average number of consecutive slots that the channel is busy (avg. burst length) E[B] = n-1 k=0 a -k -1 . In all the numerical results shown here we set n = 8 and E[B] = 20.

Fig. 2 .

 2 Fig.2. Overall efficiency of different sensing strategies. Lightly loaded channel, ρP U = 0.2; moderately loaded channel, ρP U = 0.5.

Fig. 3 .

 3 Fig. 3. Trade-off between ηt and ηs. The numbers next to the points denote the average sleep length for the nearby set of points.

Fig. 4 .

 4 Fig. 4. Complementary CDF of the duration of an effective white space. Deterministic sleep duration

The research of this author was supported in part by the Spanish government through grant SAB2009-0132. The research of these authors was supported by the Spanish government through the projects TIN2008-06739-C04-02 and TIN2010-21378-C02-02, and by Universitat Politècnica de València through PAID-06-09.


Lei Jiao

Frank Y Li
email: frank.li@uia.no.

Vicent Pla
email: vpla@dcom.upv.es.

Greedy versus Dynamic Channel Aggregation Strategy in CRNs: Markov Models and Performance Evaluation

Keywords: Cognitive radio networks, channel aggregation strategy, continuous time Markov chain models, performance evaluation

In cognitive radio networks, channel aggregation techniques which aggregate several channels together as one channel have been proposed in many MAC protocols. In this paper, we consider elastic data traffic and spectrum adaptation for channel aggregation, and propose two new strategies named as Greedy and Dynamic respectively. The performance of channel aggregation represented by these strategies is evaluated using continuous time Markov chain models. Moreover, simulation results based on various traffic distributions are utilized in order to evaluate the validity and preciseness of the mathematical models.

Introduction

In Cognitive Radio Networks (CRNs) [START_REF] Akyildiz | CRAHNs: Cognitive Radio Ad Hoc Networks[END_REF], when multiple channels are available, Secondary Users (SUs) can decide to aggregate them together as one channel to support services with higher data rate or still to treat them as individual channels. The former alternative, channel aggregation, has been proposed in many Media Access Control (MAC) protocols [START_REF] Khalona | Channel Aggregation Summary[END_REF][START_REF] Jia | HC-MAC: A Hardware-Constrained Cognitive MAC for Efficient Spectrum Management[END_REF][START_REF] Salameh | MAC Protocol for Opportunistic Cognitive Radio Networks with Soft Guarantees[END_REF] in CRNs.

The research work on spectrum access in CRNs can be categorized into two phases. The first phase is MAC protocol design itself, which aims at proposing feasible schemes to make CRNs access spectrum more efficiently [START_REF] Khalona | Channel Aggregation Summary[END_REF][START_REF] Jia | HC-MAC: A Hardware-Constrained Cognitive MAC for Efficient Spectrum Management[END_REF][START_REF] Salameh | MAC Protocol for Opportunistic Cognitive Radio Networks with Soft Guarantees[END_REF]. The second phase is to build analytical models in order to help us better understand the dynamics behind these schemes and evaluate the performance of different strategies [START_REF] Zhu | Analysis of Cognitive Radio Spectrum Access with Optimal Channel Reservation[END_REF][START_REF] Martinez-Bauset | Comments on 'Analysis of Cognitive Radio Spectrum Access with Optimal Channel Reservation[END_REF][START_REF] Wong | Analysis of Cognitive Radio Spectrum Access with Finite User Population[END_REF][START_REF] Jiao | Analysis on Channel Bonding/Aggregation for Multi-channel Cognitive Radio Network[END_REF][START_REF] Lee | Analysis of Cognitive Radio Networks with Channel Aggregation[END_REF]. In this study, we mainly focus on the second phase and analyze the performance of channel aggregation represented by two new strategies, i.e., the Greedy strategy and the Dynamic strategy, when spectrum adaptation is enabled. This work is motivated by the observation that the performance of SU networks with various channel aggregation strategies is not thoroughly analyzed through mathematical models. For example, in [START_REF] Zhu | Analysis of Cognitive Radio Spectrum Access with Optimal Channel Reservation[END_REF][START_REF] Martinez-Bauset | Comments on 'Analysis of Cognitive Radio Spectrum Access with Optimal Channel Reservation[END_REF][START_REF] Wong | Analysis of Cognitive Radio Spectrum Access with Finite User Population[END_REF], the performance of an SU network when a channel for Primary Users (PUs) can be divided into several channels for SUs is analyzed based on a Continuous Time Markov Chain (CTMC) model. In [START_REF] Jiao | Analysis on Channel Bonding/Aggregation for Multi-channel Cognitive Radio Network[END_REF][START_REF] Lee | Analysis of Cognitive Radio Networks with Channel Aggregation[END_REF], the performance of several channel aggregation strategies when spectrum adaptation is not enabled is studied through CTMC models. However, none of them analyze channel aggregation with spectrum adaptation systematically through mathematical modeling.

The meaning of spectrum adaptation is twofold. On the one hand, it is inherited from spectrum handover, allowing SUs to switch an ongoing SU service to a channel that is not occupied by PUs or SUs, when PUs appear on the current channel. On the other hand, it is meant that an ongoing SU service can adjust the number of aggregated channels according to the availability of channels as well as other SUs' activities. Since spectrum adaptation is potentially more appropriate for CRNs, we propose two channel aggregation strategies with spectrum adaptation in which SUs greedily or dynamically aggregate a number of available channels. Based on the proposed strategies, we present CTMC models to analyze their performance. Then, numerical results obtained from mathematical models and simulations are analyzed and compared. Finally, the results under various traffic distributions are examined by simulations and compared with the analytical results.

The rest of this paper is organized as follows. The system model and channel aggregation strategies are described in Sec. 2. In Sec. 3, CTMC models are built in order to analyze the performance of these strategies. Numerical results and corresponding discussions are presented in Sec. 4. Finally, the paper is concluded in Sec. 5.

System Model and Channel Aggregation Strategies

System Model and Assumptions

Two types of radios, PUs and SUs, operate in the same spectrum band consisting of M channels for PUs. The channels are allocated to PUs, and can be utilized by SUs when they are not occupied. SUs must release the channel upon a PU appearance. Each PU service occupies only one channel while SUs may aggregate multiple channels, N (N ≤ M ), for a service (a packet, flow or session) transmission. The aggregated channels can be either adjacent or separated in the spectrum domain.

We assume that there is a protocol with ignorable overhead working behind to support channel aggregation and spectrum adaptation, and SUs can sense PUs activities precisely. It is further assumed that the sensing and spectrum adaptation latency is much shorter than the duration between service events. We thus assume that the arrival or departure of services will not happen during the sensing and spectrum adaptation period. In the following analyses, we focus on the performance of the secondary network.

Channel Aggregation Strategies

In what follows, the Greedy and the Dynamic strategies are proposed. In the strategy descriptions, two parameters, W , V are utilized to indicate the lower bound and the upper bound of the number of aggregated channels respectively. Let N denote the number of channels that an SU service aggregates. This number can vary from one SU service to another and even vary along time for a single SU service.

Greedy W ≤ N ≤ V : In this strategy, an SU is to aggregate up to V channels at the time when it tries to access channels if the number of idle channels is larger than or equal to W . During an SU service period, if any channels become idle, ongoing SU services with fewer than V channels will greedily aggregate those newly available ones up to V . Moreover, if there is no idle channel upon a PU arrival, ongoing SU services will adjust downwards the number of channels, as long as its remaining number is still not fewer than W . If a PU takes any one of these channels that is in use by an ongoing SU service with exactly W channels when no idle channel exists currently, the service is forced to terminate. Upon the arrival of a new SU service request, if there are fewer than W idle channels, the request will be blocked.

In the presence of multiple ongoing SU services that can utilize newly vacant channels, the one that currently has the minimum number of aggregated channels will occupy them first. If the SU service with the minimum number reaches the upper bound V after adjusting and there are still vacant channels, other SU services will occupy the remaining ones according to the same principle, until all those newly vacant channels are utilized or all of the ongoing SU services aggregate V channels. For example, assume that four channels become idle while there are two ongoing SU services occupying one and two channels respectively, in Greedy 1 ≤ N ≤ 4. The ongoing SU service with one channel will then acquire three of the four idle channels and reach the upper bound. Since there is still one idle channel left, the other ongoing SU service with two channels will use this one.

Dynamic W ≤ N ≤ V : In this strategy, SU services react in the same way as in the Greedy strategy when PU services arrive and when PU or SU services depart. However, upon an SU arrival, if there are not enough idle channels, instead of blocking it, ongoing SU services will share their occupied channels to the newcomer, as long as they can still keep at least W channels and the number of channels is sufficient for the new SU service to commence after sharing.

With this strategy, when a new SU service needs the channels shared by ongoing SU services to commence and there are several ongoing SU services, the one that occupies the maximum number will release its channels first. If the one with maximum number cannot provide enough channels by itself, the one with the second maximum number will share its channels then, and so on. The new SU service will aggregate W channels initially if it needs the channels shared by ongoing SU services to join the network. If the number of idle channels together with the number of channels that can be released by all ongoing SU services is still lower than W , the request is blocked.

In summary, ongoing SU services are given higher priority to finish their transmission first in the Greedy strategy while the access opportunities are more fairly shared among SUs in the Dynamic strategy. A special case of these strategies is W = V = 1, i.e., without channel aggregation. We denote it as No aggregation in our numerical results presented later.

CTMC Models for the Channel Aggregation Strategies

To model different strategies, we develop CTMCs by assuming that the service arrivals of SUs and PUs to these channels are Poisson processes with arrival rates λ S and λ P respectively. Correspondingly, the service times are exponentially distributed with service rates µ S and µ P in one channel. The newly arrived PU services will access channels that are not occupied by PU services with the same probability. Elastic traffic is considered, which means that the service time will be reduced if more channels are utilized for the same service. Assume further that all the channels are homogeneous. Therefore, the service rate of N aggregated channels is N µ S . The unit for these parameters can be service/time unit. Given concrete values to these parameters, the results can be expressed, e.g., in Mbps. For this reason, the unit of capacity is not explicitly expressed in our analysis.

For both of the Greedy and Dynamic strategies, the states of the CTMC models can be represented by x = (i, j W , ..., j k , ..., j V ), where i is the total number of PU services while j k is the number of SU services that aggregate k channels in the system. We denote by b(x) the total number of used channels at state x as b(x) = i + V k=W kj k .

CTMC Analysis for the Greedy W ≤ N ≤ V Strategy

Given concrete values of M , V and W , the feasible states of the CTMC model for the Greedy strategy can be expressed as a combination of two categories. The first category refers to the states with vacant channels, i.e., when b(x) < M . The second category follows b(x) = M . Denote the set of states in the second category by C, the feasible states of this strategy, S, can be expressed as S := {(i, 0, ..., 0, j V )|b(x) < M } ∪ C. Since the state set C is not obvious, we propose an algorithm to construct it in an iterative manner, as illustrated in Alg. 1. The state transitions can be found in Table 1. Based on the balance and the normalization equations, the state probability, π(x), can be calculated and the following performance parameters can be further obtained. The blocking probability of SU services, P b , is given by

Algorithm 1 : To acquire state set C C := {x |b(x) = M, jV = (M -i) V , j k = 1, k = M -i-V jV },
P b = x∈S,M -b(x)<W π(x). (1)
The capacity of the secondary network, ρ, is the average number of SU service completions per time unit [START_REF] Zhu | Analysis of Cognitive Radio Spectrum Access with Optimal Channel Reservation[END_REF], as follows,

ρ = x∈S V k=W kj k µ S π(x).
(2)

(i -1, jW , . . . , j k -1, j k+1 +1, . . . , jV ) iµP j k > 0, k = min{r|jr > 0, W ≤ r ≤ V -1}; i > 0; V > 1.
PU departs, and SUs cannot use the vacant channel

(i -1, jW , . . . , j k , . . . , jV ) iµP j k = 0, ∀k < V ; i > 0.
SU with k channel(s) departs. Other SU services, if exist, cannot use the vacant channel(s)

(i, jW , . . . , j k -1, . . . , jV ) kj k µS j k = 1, k < V ; jm = 0, ∀m < V and m = k. Or j k > 0, k = V ; jm = 0, ∀m < V .
SU with k channel(s) departs. An SU service with minimum number of aggregated channels, h, uses all the vacant channel(s)

(i, jW , . . . , j h -1, . . . , j k -1, . . . , j l + 1, . . . , jV ) kj k µS j k > 1; h = min{r|jr > 0, W ≤ r ≤ V -1}; l = k + h ≤ V ; V > 1. Or j k = 1; h = min{r|jr > 0, r ∈ {W, . . . , k -1, k + 1, . . . , V -1}}; l = k + h ≤ V ; V > 1. . . . . . . . . . . . . SU with k channel(s) de-
All rest SU services with fewer than V channels use the vacant channel(s) and achieve the upper bound V .

(i, 0, . . . , 0, . . . , 0, . . . , jV + q)

kj k µS q = V -1 m=W jm -1; k ≥ V -1 m=W (V -m)jm-(V -k); V > 1.
PU arrives when a vacant channel exists

(i + 1, jW , . . . , j k , . . . , jV ) λP b(x) < M .
PU arrives. An SU service with k channels reduces its aggregated channels

(i + 1, jW , . . . , j k-1 +1, j k -1, . . . , jV ) kj k M -i λP b(x) = M ; j k > 0, k > W ; V > 1.
PU arrives and an SU service is terminated. No spectrum adaptation is needed

(i + 1, jW -1, . . . , j k , . . . , jV ) W jW M -i λP jW = 1; j k = 0, W +1 ≤ k ≤ V -1; b(x) = M ; W > 1. Or jW ≥ 1; b(x) = M ; W = 1. Or jW ≥ 1; b(x) = M ; W = V .
PU arrives. An SU service is terminated and provides vacant channel(s). The SU service with minimum number of aggregated channels, h, could use the vacant channel(s)

(i + 1, jW -1, . . . , j h -1, . . . , j l + 1, . . . , jV ) W jW M -i λP jW > 1; h = W ; l = h + W -1 ≤ V ; W > 1; b(x) = M ; V > 1. Or jW = 1; h = min{r|jr > 0, W + 1 ≤ r ≤ V -1}; l = h+W -1 ≤ V ; W > 1; b(x) = M ; V > 1.
.

) W jW M -i λP b(x) = M ; q = V -1 m=W jm-1; W - 1 ≥ V -1 m=W (V -m)jm -(V -W ); W > 1; V > 1.

SU arrives

(i, jW , . . . ,

j k + 1,. . . , jV ) λS k = min{M -b(x), V } ≥ W .
The average service rate per commenced SU service, µ ps , is defined as the capacity divided by the average number of commenced SU services,

µ ps = ρ/ x∈S V k=W j k π(x). (3)
The forced termination probability, P f , which represents the fraction of the forced terminations over those commenced SU services, is given by

P f = R f /λ * S = x∈S,b(x)=M, jW >0,i<M λ P W j W (M -i)λ * S π(x), (4)
where R f is the forced termination rate and λ * S = (1 -P b )λ S .

CTMC Analysis for the Dynamic W ≤ N ≤ V Strategy

Let S be the set of feasible states of this strategy, as S := {(i, 0, ..., 0, j V )|i + V j V < M } ∪ {x |b(x) = M }. For a generic state (i, j W , ..., j k , ..., j V ) in this strategy, transitions corresponding to PU arrivals, PU and SU departures are exactly the same as those in the Greedy strategy, which are specified in Table 1. The difference is that the Dynamic strategy has various destination states when an SU service arrives. Therefore, we only show in Table 2 the corresponding transitions when an SU service arrives for Dynamic W ≤ N ≤ V , where the arrival rate is λ S . Again, based on the above analysis, the state probability of π(x) can be obtained and then ρ, µ ps , and P f can be computed by Eqs. ( 2), ( 3) and ( 4) respectively, while the blocking probability becomes,

P b = x∈S, M -b(x)+ V k=W +1 (k-W )j k <W π(x). ( 5
)
Table 2. Transitions from a generic state x = (i, jW , . . . , j k , . . . , jV ) of Dynamic W ≤ N ≤ V , ≤ k ≤ V when an SU service arrives.

Activity

Dest. state Conditions SU arrives when enough idle channels exist (i, jW , . . . ,

j k + 1, . . . , jV ) k = min{M -b(x), V } ≥ W .
SU arrives. The ongoing SU service with the maximum number of channels, m, gives channel(s) to the newcomer

(i, jW + 1, . . . , jn + 1, . . . , jm -1, . . . , jV ) m = max{r|jr > 0, W + 1 ≤ r ≤ V }; n = m -[W -(M -b(x))], W ≤ n < m; V > 1.
. . . . . . . . . SU arrives. All ongoing SU services that aggregate more than W channels give to the newcomer (i, jW + q, 0, . . . , 0, jn +1, 0, . . . , 0)

q = V m=W +1 jm; n = V m=W +1 (m-W )jm +M -b(x), W ≤ n < min{r|jr > 0, W + 1 ≤ r ≤ V }; V > 1.

Numerical Results and Discussions

In this section, the obtained numerical results for these strategies are presented. In the first part, ρ, P b , µ ps , and P f are examined and mathematical results are verified by simulations. In the second part, the results under various traffic distributions are illustrated.

Performance Comparison among Different Strategies

Numerical results for ρ, P b , P f , and µ ps as a function of λ P are illustrated in Fig. 1 and Fig. 2, given M = 6, λ S = 1.5, µ S = 0.82, and µ P = 0.5. To compare the impact of different threshold values, we plot two groups of results for each strategy, i.e., 1 ≤ N ≤ 3 and 3 ≤ N ≤ 6. The results of No aggregation are also shown for comparison.

Model Verification and System Capacity

To verify the CTMC models, the simulation together with the analytical results of the capacity in the secondary network are plotted in Fig. 1 (a). More specifically, the solid lines are the analytical results while the marks are simulation results. The stochastic process is simulated by generating both PU and SU services according to the assumed distributions. From this figure, we can conclude that the simulation results precisely coincide with the analytical ones. In figures shown later, the analytical results have also been verified by simulations.

As shown in Fig. 1 (a), the system capacity of the secondary network decreases for all strategies as λ P increases. Furthermore, only the Dynamic strategy with a small value of W , i.e., Dynamic 1 ≤ N ≤ 3, can provide higher capacity than No aggregation does and both of them can achieve capacity close to the offered load, i.e., λ S = 1.5, when λ P is small. Note that the system capacity of Greedy 1 ≤ N ≤ 3 becomes higher than that of the No aggregation when λ P ≥ 2. However, this benefit is not of great significance since the corresponding blocking and forced termination probability is relatively high, which can be observed in Fig. 1 (b) and Fig. 2 (a). Among different strategies, Dynamic strategies achieve higher capacity than the corresponding Greedy strategies.

Comparing two groups of 1 ≤ N ≤ 3 and 3 ≤ N ≤ 6 in the same strategy, the results in the former group for each strategy have higher capacity. The reason is that in the latter group, the strategies require at least three vacant channels out of a total number of six channels, leading to wasted spectrum opportunities in comparison with the group of 1 ≤ N ≤ 3.

Blocking Probability Fig. 1 (b) depicts the blocking probability of SU services. One can observe that Dynamic 1 ≤ N ≤ 3 has the lowest blocking probability since it needs only one channel for initiating an SU service and can adjust the number of aggregated channels when both PU and SU services are present. Similarly, No aggregation has the second lowest blocking probability among all strategies. Since the newly arrived SU service will be blocked while the ongoing ones will utilize as many available channels as possible in the Greedy strategies, they have higher blocking probability. Again, comparing the group 1 ≤ N ≤ 3 with 3 ≤ N ≤ 6, the blocking probability is generally higher in the latter one. The reason is straightforward since more channels are required in the latter case before a service request can be accepted.

Forced Termination Probability

To examine the forced termination probability of commenced SU services, we plot P f in Fig. 2 (a). As expected, P f becomes higher for all strategies as λ P increases since PUs become more active. Comparing these strategies, the Greedy ones have the lowest P f while the Dynamic strategies enjoy a lower P f than No aggregation. The main reason that the Greedy strategies yield lower P f than their Dynamic counterparts do is that the new SU requests will be simply blocked in the Greedy case when the number of idle channels is not sufficient for a newly arrived SU service. In contrast, in Dynamic ones, a new SU service can commence by utilizing channels donated by ongoing SU services. Therefore, the number of parallel SU services in the Greedy strategies is smaller. With the ability of reducing the number of channels for ongoing SU services in both cases, the Greedy strategies enjoy lower P f than the Dynamic ones.

Average Service Rate per Commenced Service Fig. 2 (b) illustrates the average service rate of the commenced SU services. As illustrated in this figure, the larger number of channels it aggregates, the higher average service rate a strategy can achieve. For No aggregation, the average service rate does not change with different λ P since each SU service uses only one channel all the time, i.e., µ ps = µ S , while this rate in other strategies declines with an increasing λ P . Comparing No aggregation with Dynamic 1 ≤ N ≤ 3, SU services in the Dynamic strategy are dispatched more quickly than in No aggregation since more channels are used, even when they have similar capacity which is close to the offered load with a small λ P . In the Greedy strategies, since ongoing SU services will not share channels with new coming SU services, higher average service rate is achieved than in the Dynamic cases.

Traffic Pattern with Various Distributions

For the results presented above, Poisson arrivals and exponential distributed service time are assumed. In real life, traffic patterns might be different from those ones, making the analytical treatment infeasible. However, the performance of these strategies can still be evaluated by simulations for various traffic types. Figure 3 illustrates the system capacity of two example strategies, No aggregation and Dynamic 1 ≤ N ≤ 6 as a function of λ S , under two traffic models based on real-life traffic observations [START_REF] Willkomm | Primary Users Behavior in Cellular Networks and Implications for Dynamic Spectrum Access[END_REF][START_REF] Barford | Generating Representative Web Workloads for Network and Server Performance Evaluation[END_REF]. For traffic pattern one, Poisson arrivals and log normal distributed service time for both PUs and SUs are utilized. Within this traffic type, we consider further two cases. The first case is that both the mean value and the variance of log normal distributions equal to those of the corresponding original exponential distributions, labeled as Lognormal . The other case, labeled as Lognormal * , is that the variance values of log normal distributions are larger than those of the original exponential distributions, i.e., the Squared Coefficient of Variation (SCV) equals to 4.618 [START_REF] Barford | Generating Representative Web Workloads for Network and Server Performance Evaluation[END_REF] (SCV= variance/mean 2 ) while the mean values are kept the same. For traffic pattern two, a random walk model for PUs [START_REF] Willkomm | Primary Users Behavior in Cellular Networks and Implications for Dynamic Spectrum Access[END_REF], and a Poisson arrival and log normal distributed service time for SUs are adopted, labeled as Random walk , where the average time interval between events in the random walk model is 1.0683 time unit. For the log normal distribution of SU service time used in this case, we make the mean value and variance equal to that of the original exponential distribution. The results from the mathematical analysis are also plotted as a reference, labeled as Original , with M = 6, µ S = 0.5, λ P = 0.5 and µ P = 0.15601.

From this figure, we can observe that the results under different traffic models are still quite close to the ones obtained under Poisson arrivals and exponential service time distributions. This observation indicates that although different traffic models exist, the mathematical analysis presented in this paper can be used as a good approximation for analyzing the performance of those channel aggregation strategies in CRNs.

Conclusions

In this paper, two channel aggregation strategies in CRNs with spectrum adaptation are proposed and investigated, and their performance is evaluated and compared through both mathematical analyses and simulations. Numerical results demonstrate that the Dynamic strategy with a small value of the lower bound of the number of aggregated channels can achieve higher capacity and lower blocking probability than No aggregation and its Greedy counterparts do. From an individual SU service's perspective, however, a commenced SU service in the Greedy strategies can enjoy a higher service rate as well as lower forced termination probability, at the cost of lower system capacity and higher blocking probability.

F

  := {(i + 1, jW , . . . , jp + 1, jp+1 -1, . . . , jV ) | ∀(i, jW , . . . , jp, jp+1, . . . , jV ) ∈ C, p ∈ {W, . . . , V -1}, jp+1 > 0}, Do := F -F ∩ C, C := C ∪ Do, while Do = ∅ do F := {(i + 1, jW , . . . , jp + 1, jp+1 -1, . . . , jV ) | ∀(i, jW , . . . , jp, jp+1, . . . , jV ) ∈ Do, p ∈ {W, . . . , V -1}, jp+1 > 0}, D := F -F ∩ C, C := C ∪ D, Do := D. end while

Fig. 1 .

 1 Fig. 1. System capacity and blocking probability as a function of λP .

6 (

 6 a) Forced termination probability.

≤ 6 (

 6 b) Average service rate.

Fig. 2 .

 2 Fig. 2. Forced termination probability and average service rate as a function of λP .

Table 1 .

 1 Transitions from a generic state x = (i, jW , . . . , j k , . . . , jV) of Greedy W ≤ N ≤ V , W ≤ k ≤ V .

	Activity	Dest. state	Trans. rate Conditions
	PU departs, and an SU ser-
	vice with k channel(s) uses
	the vacant channel