Ernesto García Davis
email: ernesto.garcia@entel.upc.edu

Anna Calveras Augé

Presence-based Architecture for Wireless Sensor Networks using Publish/Subscribe paradigm

Keywords: Distributed Architecture, Wireless Sensor Networks, Presence Service, Embedded Devices

Ubiquitous communication is a key component of Ambient Intelligence, enabling objects to communicate with each-other by means of a wireless ad-hoc network. A presence service allows knowing the availability or responsiveness status of elements in a communication (entities). Traditionally, only human use this service, however all smart devices or objects (with embedded wireless sensor nodes) could interact with each other thus a presence service could also enhance communication among them. To achieve this objective we look into existing protocols to propose the requirements needed to provide presence service on Wireless Sensor Networks (WSN). The main contribution of this paper is the discussion of requirements for presence services on WSN and the new proposed architecture to cope with presence services in WSN.

Introduction

Wireless Sensor Networks (WSN) consist of small distributed sensor nodes capable of communicate in a wireless network. WSN are providing tremendous benefits for a number of industries. In recent years, uses of WSN are moving from the mere monitoring of certain environmental variables towards its adoption for context aware systems. In this sense, WSN are able to capture a rich set of contextual information (e.g. spatial, physiological and environmental data) and to respond regarding to a situation without user interaction. In addition, context information could also contain another type of information called presence information. This information is related to user and communication conditions, capacity and preferences. Traditionally, presence information has been used by personal applications such as Instant Messaging (IM) in which human user can know the willingness or responsiveness of other human users to engage a communication. In a similar manner, presence information can also be used by other type of users such smart objects or devices in order to discover the status, conditions and capacity with the purpose of interacting with each other. In this paper, a "smart object or device" refers to anything that has specific functionality and that is able to compute and communicate on its own. For instance, an energy meter can be programmed in a specific way. When consumption reaches a threshold it should send a command to turn off all devices with less priority, so we can save energy. Without presence information (such as on/off/standby/consumption level, user preferences, etc) the energy meter would try to send this command to all devices complying this condition. However, the energy meter would not know which of them are turned off. Therefore, unnecessary packets will be transmitted into the network resulting in waste of resources (energy, processing and bandwidth) at each node along the path to reach the destination device.

Some use cases to apply presence services on WSN are related to smart grid or Internet of Things. Firstly, Home Area Network (HAN) devices are capable of receiving messages from the Utility (service provider) and adjusting its operational mode based on Consumer preferences (e.g., energy saving mode, delayed turn on/off, etc). In these scenarios, a presence service could enhance decisions interacting between HAN devices and Utility equipment. Each HAN device will publish its presence information to the Utility equipment. The Utility will check the state of HAN devices presence before transmitting a command. In this manner, only HAN devices with availability status will receive a command, thus the Utility only will transmit necessary messages to the network. Secondly, the Internet of Things will be an open network in which auto-organized or intelligent entities will be interoperable and able to act independently pursuing their own objectives or shared ones, depending on the context, circumstances or environments. In the cases aforementioned, each object or device could incorporate an embedded sensor able to capture, to process and to communicate presence information through wireless media to enhance system performance.

Our motivation for this research is based on the fact that an efficient communication among users is possible if we know its presence information. Nevertheless, the presence service as we know it in Internet cannot be directly applied to the devices based on WSN. That is because these types of networks have constrained resources on processing, energy and bandwidth. The requirements in its architecture must be defined in an efficient manner.

Presence services, in general, are based on Publish/Subscribe communication model [START_REF] Eugster | The many faces of publish/subscribe[END_REF] [START_REF] Tran | Publish/Subscribe Techniques for Sensor Networks[END_REF]. Also, this model has been integrated in several protocols specifically designed for WSN (e.g., service discovery protocols and middleware technologies). However, as far as we know there is not a protocol or mechanism which considers the whole requirements to provide presence services in WSNs.

In this paper, we present the requirements to provide a presence service on WSN and then we propose a presence-based architecture using the Publish/Subscribe communication model. The remainder of this paper is organized as follows. In section 2, we provide background information about Presence Service. Followed, section 3 presents related work for Publish/Subscribe Protocols on WSN. In Section 4 we discuss the requirements to provide presence service on WSN and a new presencebased architecture for WSN. Finally, conclusions and future work are discussed in section 5.

Presence information is a subset of context information. It expresses the determining factors around communication between users or devices (such as their availability, willingness, environment, preferences, etc). The presence service architecture [START_REF] Day | Presence and Instant Messaging Model (RFC2778)[END_REF] fits into publish/subscribe communication model. This architecture works as follows (Fig. 1): the presence entities, called presentities (devices or objects), provide their presence information to the presence service. The presence service accepts, stores, and distributes the presence information to everyone subscribed to get the notification about presence changes. The entities (devices or objects) receiving notification about presence information are called watchers. The presence information will improve the whole communication because watchers only will transmit messages to presentities taking into account their presence information. Therefore, we achieve an efficient communication on WSNs taking into account the constrained resources on this type of networks. Presentities and watchers communicate by exchanging presence events. Presentities are publishers in Publish/Subscribe Communication Model and watchers are subscribers that are interested in a presence event.

In the next section, we briefly present publish/subscribe protocols already known in the area of sensor networks. We focus on the issues they are addressing in their design.

3 Related Work of Publish/Subscribe on WSN Several authors [START_REF] Hunkeler | A publish/subscribe protocol for Wireless Sensor Networks[END_REF] [START_REF] Krishnamurthy | Providing Seamless Access to Sensor-based Services[END_REF] have proposed protocols making use of publish/subscribe communication model. In this section, we summarize these protocols focusing on relevant aspects for presence services on WSN.

Message Queuing Telemetry Transport for Sensor Networks

Message Queuing Telemetry Transport for Sensor Networks (MQTT-S) is an extension of Message Queuing Telemetry Transport (MQTT) [START_REF]MQTT[END_REF] originally developed for telemetry applications using constrained devices. It is based on a centralized architecture where a broker node is placed in the backbone network to provide publish/subscribe service to the nodes in this part of the network and in the WSN. MQTT-S allows subscribing to one topic and receiving information of several nodes by using the "wildcard" concept. Therefore we can reduce the number of transmitted messages to only one SUBSCRIBE message instead of sending one for each device. That results in energy saving for the subscriber nodes which is very relevant in large WSN. MQTT-S defines three QoS levels. Level 0 offers a best effort delivery service and no retransmission or acknowledgment is defined. Level 1 allows the retransmission of messages until they are acknowledged by the receivers. However, certain messages may arrive multiple times at the destination because of the retransmissions (duplicated). Finally, level 2 ensures not only the reception of the messages, but also that they are delivered only once to the destination. In addition, this protocol considers the message size to be no longer than 64 bytes of the payload of an 802.15.4 packet (127 bytes). That is because the remaining 64 bytes should be used by the overhead information required to support functions such as MAC layer, networking, security, etc.

Tiny Session Initiation Protocol

Tiny Session Initiation Protocol (TinySIP) is based on Session Initiation Protocol (SIP) protocol. It incorporates a messaging mechanism for accessing sensor-based services. It provides a communication abstraction which allows session signaling, publish/subscribe services and instant messaging features. Basically, this protocol is based on centralized architecture. A SIP-TinySIP Gateway(s) situated on the edge of WSN. All communication between clients on outsider networks and WSN nodes is through the SIP-TinySIP Gateway(s). In addition, TinySIP uses a more compact message size than MQTT-S. A TinySIP message can be transmitted within a small payload, such as the 29-byte of a regular TinyOS payload message.

Proposed Architecture

In this section, we firstly present the requirements for presence service. Next, we propose a new architecture based on publish/subscribe to cope with presence service on WSN.

Requirements for Presence Service on WSN

In general, presence services on Internet have certain limitations to be used on WSN. The most relevant are: ─ Limited vocabulary to express presence information: In the case of human users, the presence information was contained in PIDF [START_REF] Sugano | Presence Information Data Format[END_REF] format. It includes a simple status of presence information (e.g.: offline, busy, away), and this is not enough to convey a user's real situation and to decide how to establish a communication with an entity. Some authors have identified this insufficiency of basic information and responded with several extensions of presence information [START_REF] Schulzrinne | Rich Presence Extensions to the PIDF (RFC 4480[END_REF] [6] [START_REF] Peterson | GEOPRIV Location Object Format[END_REF] that are RPID, CPID and GEOPRIV respectively. However, to enable the integration with objects or devices, we need to define others extensions. Therefore, we can accommodate additional type of information provided by sensor nodes embedded on devices or objects. A first approach to extend the vocabulary is presented in [START_REF] El Barachi | A Presence-Based Architecture for the Integration of the Sensing Capabilities of WSN in IM Subsystem[END_REF] where authors propose the addition of two new attributes to the GEOPRIV. Nowadays, there is not yet consensus in the used data model to describe the presence information of objects or devices. ─ The presence status is generally updated manually by the user: There is not a way to deduce automatically presence status of a user. Some presence technologies can change presence information status to "away" assuming that there is not activity from the user in the device during some period of time. In the case of objects or devices acting as presentities, it should be necessary that they change their status without user interaction. That can be made by means of context information acquired by sensor nodes.

Moreover, there are other requirements we have to consider based on the specific characteristics of WSN such as: ─ Reduced size of MTU: the size of presence information messages used by traditional presence services is incompatible to fit into the data packets used in embedded devices with constrained resources, such as sensor nodes. It is needed an encoding/compressing mechanism to convey presence information on WSN. ─ Limited resources in terms of energy, computing and storage: The availability of these resources depends on the number of transmissions and the length of transmitted packets. Authors in [11] [12] do not provide a mechanism to manage resources in an efficient manner. In this case, we could apply data aggregation techniques [9] that allow, for example, concatenating individual data items into larger packets thus reducing network traffic load and saving energy. ─ Wireless communication: WSN are susceptible to loss packets due to transmission errors. If presence information cannot be delivered to watcher nodes, the communication among entities could be affected. Therefore, it is necessary to implement a reliable data delivery. In this case we could consider using Transmission Control Protocol (TCP). However, the header overhead, connection management, end-to-end flow and congestion control lead to TCP poor performance on wireless environment and resource constrained nodes, such as WSN [START_REF] Kuorilehto | Experimenting TCP/IP For Low-Power Wireless Sensor Networks[END_REF]. This issue is still opened and some authors [START_REF] Hunkeler | A publish/subscribe protocol for Wireless Sensor Networks[END_REF] suggest assign this functionality to the application layer.

General Description of the Proposed Architecture

Taking into account the relevant features of current publish/subscribe protocols and the requirements above mentioned, we propose a new approach for a presence-based architecture. There are three entities that interact in our architecture. The first is a publisher entity that is used to produce presence information and publish it when it is requested. Second, there is a subscriber which is the entity that makes a subscription in order to receive presence information for its interest. Finally, there is a broker entity responsible for distributing the published information from publishers to subscribers. Our architecture, contrary to centralized architecture such [START_REF] Hunkeler | A publish/subscribe protocol for Wireless Sensor Networks[END_REF], is based on distributed architecture.

In centralized architecture there is only one broker node located between WSN and the external network. So, the broker node makes the sink node functionality. Therefore, when many nodes are forwarding messages to the sink node at high rates, it could become a bottleneck leading to low network performance. In addition, this architecture is unsuitable for providing a presence service on WSN because these protocols consider the communication will only occur between sensor nodes and external users or vice versa. Thus, all the information is sent to the broker node (sink) located between WSN and external network. However, a presence service on WSN and new trends such as "Internet of Things" consider that objects can interact among them. Thus, publish/subscribe protocols should consider publisher nodes not always will send information to the sink node as the only destination. We propose a distributed architecture, where there are other broker nodes inside WSN aside from the broker node acting as sink node. We can see this distributed architecture in Fig. 2 where there are, as example, two broker nodes inside WSN, and another broker node at the edge of the network. This one is also acting as gateway to communicate with the external network. Thus, it allows distributing the load in the network by grouping publisher and subscriber nodes in different broker nodes. We call broker domain to the group of subscribers and publishers nodes managed by a broker node. The broker nodes will be the only responsible to exchange message between broker domains, as we can see in Fig. 3. When a potential publisher or subscriber node enters into the network, it sends a broadcast message to discovery a broker node in its domain. Once the publisher or subscriber node receives a reply, it will establish a connection with the broker node. Also, a broker node might play a publisher or subscriber role on behalf of its domain. Fig. 3 shows this situation. "Subscriber 1" and "Publisher 1" are placed in different broker domains. "Subscriber 1" on broker domain A wants to receive presence information from "Publisher 1" on broker domain B. So, "Subscriber 1" makes a subscription (1) in its respective broker node ("Broker A"). This one makes a subscription (2) in the broker node responsible for broker domain B ("Broker B"). When "Publisher 1" sends presence information (3) to its broker node, this one will forward it (4) to broker node of Broker Domain A, and this one; will transmit it (5) to the "Subscriber 1". In this way, nodes located in different Broker's domains will exchange messages through corresponding broker nodes. It should be noticed that a broker node learns the identities of brokers in other domains. That is because it receives a broadcast message of available topics to subscribe in each broker. Then, it will store this information to be available when a potential subscriber node wants to subscribe to a topic. On the other hand, publisher and subscriber nodes located in the same broker domain, will exchange messages through the broker node responsible for this domain. Thus, exchanged traffic is kept inside the broker domain. This situation is also depicted on Fig. 3, where "Subscriber 2" makes a subscription (6) through "Broker B" to receive presence information from "publisher 2" on the same broker domain B. When "Publisher 2" publishes presence information [START_REF] Peterson | GEOPRIV Location Object Format[END_REF] to its broker node, "Broker B" will forward it [START_REF] El Barachi | A Presence-Based Architecture for the Integration of the Sensing Capabilities of WSN in IM Subsystem[END_REF] to "Subscriber 2". In conclusion, the proposed architecture contributes to isolate the exchanged traffic in broker domains, and will exchange traffic between broker domains through corresponding broker nodes only when it is needed.

The proposed architecture not only improves scalability but also provides mechanisms for an efficient energy management. Moreover, it reduces the subscriber nodes spent time to receive the first publication. These mechanisms are explained in following sections.

Publication on Demand of Presence Information

Generally, publish/subscribe protocols allow a publisher to publish data regardless of the presence of a subscriber. This would result in extra power consumption at publisher node. Moreover, unnecessary network traffic increases the risk of network congestion. To overcome this situation, in our architecture, publisher nodes only send publications when there is a subscriber. So, the broker sends a notification message to the publisher the first time it receives a subscription. That is shown in Fig. 4. Also, similar notification message is sent to publisher when the last subscriber decides unsubscribe to presence information event (un-subscription). In this case, the publisher node stops events of presence information publication. This mechanism is referred as publication on demand of presence information. It should be noted that previously publishers communicate to the broker the events they are able to publish. This way, a broker knows about the publishers to send them the notification of subscription.

Data Aggregation

As we mentioned previously, data aggregation is a well known and essential technique to achieve energy efficiency when propagating data from WSN nodes. In our architecture, we make use of wildcards in similar way as MQTT-S [START_REF] Hunkeler | A publish/subscribe protocol for Wireless Sensor Networks[END_REF] does it. This allows that we can transmit only one SUBSCRIBE message to subscribe us to a topic related to several publishers. In addition, we propose two ways to perform data aggregation with the purpose to decrease the number of messages into the network. Data aggregation will be performed either in the publisher or in the broker node. ─ Data aggregation in publisher node: we propose the publisher nodes can aggregate packets in a "lossless way". That means that publisher will not transmit publications to the broker node until a timer expires. They will aggregate in a single message all publication events produced during the timer period. Then, they will create only one packet to transmit to the broker node. This technique results in reducing the number of transmissions and thus energy saving of network nodes. However, there is a trade-off between the number of transmissions and the delivery delay. The more the number of gathered data; the less is the number of transmissions. Nevertheless, waiting for more data increases the delivery delay. This issue is addressed by the new proposed architecture. Therefore, we recommend this technique only be applied in situations where network congestion is detected or an application parameter has been defined. We can see the algorithm in Fig. 5 where a publisher node detects a congestion indication (i.e. received from the broker or from MAC layer) or there is an application parameter defined. Then, the publisher node will activate a timer, we call "aggregation timer". During this period, publication events produced locally will be buffered and marked for "lossless" aggregation. The number of packets to be buffered will depend on memory resources. Also, the number of data that one packet can carry will depend on the packet size limit. For example, 127 bytes is the maximum size of PHY service data unit defined in IEEE 802.15.4 standard. When the "aggregation timer" expires, the publisher node performs the lossless aggregation, and transmits the packet to the broker node. In case of congestion network, this mechanism prevents the publisher nodes continue transmitting packets. Thus, it avoids the increment of network congestion. Furthermore, it contributes to save energy. That is because of, during congestion, the transmission of packet would result in packet loss, thus extra packet retransmission. ─ Data aggregation in broker node: The broker node aggregates publication of concerning publishers (i.e. by configurable function: average, min, max, status, etc). Then, it transmits only one packet to the subscriber nodes.

Advertisement of presence information to subscribers

Another important issue in presence services over WSN is that subscriber nodes receive presence information as soon as this has been published. The proposed architecture allows publisher nodes to include presence information (initial value) when they register the topics at the broker node as is showed in Fig. 6(a). This presence information will be stored in the broker node and will be available immediately in the subscriber. Let suppose node 1 is the first subscriber for the registered topic A. Now, let consider T w as the waiting time experimented by subscriber node 1 to receive the first publication. T pb is the time used by the broker node to process the subscription of topic A and transmit the publication message to subscriber node 1. Then,

T w = T pb (1)
Otherwise, if publisher node does not register topic with initial value as it is showed in Fig. 6(b), T w would be calculated by,

T w = T np + T ep + T pp + T pb (2)
Where T np is the time used by the broker node to send a notification message indication to publisher to initiate the publication for topic A; T ep is the time until the next event for topic A is produced; and T pp is the time used by publisher node to generate publication message and transmit it to the broker node.

Evaluation

A first glance to the mechanisms provided by the proposed architecture can indicate several valuable advantages. It reduces the traffic in the whole network by isolating it inside broker domains. That is an important issue in large WSN. Moreover, it addresses the energy efficiency applying data aggregation techniques. Also, the architecture contributes to reduce the spent time of subscriber nodes to receive publications. Simulations were carried out to make a preliminary evaluation of the proposed architecture. We use OMNet++ [START_REF]OMNet++ Simulator[END_REF] simulation environment to perform several experiments. The network topology consisted of one broker node, one subscriber node and up to 32 publisher nodes depending on test scenarios. Each node is provided by an 802.15.4 network interface working in 2.4 GHz frequency. We have analysed two main aspects. Firstly, we measured the spent time of subscriber nodes to receive publications. In this case, Fig. 7 shows that the mechanism described in section 4.2.3, where publisher node is able to include initial value when it registers a topic reduces the waiting time around 38% comparing if we don't use this. Secondly, we evaluated the relation between the impact of the amount of publication messages without subscription in the network traffic when we increase the number of publisher nodes and the energy consumption when we increase the publication rate. From Fig. 8 we can note a proportional direct relation between the number of publish messages transmitted without subscription and the number of publisher nodes. In the simulations, each publisher node has a publish rate equal to 10 messages per second with a regular inter-packet interval. As we mentioned previously, this way to work has a high impact on energy resource of nodes and also generates unnecessary traffic on the network. Therefore, the advertisement of presence information to subscribers has a great benefit. Fig. 9 shows that our approach described in section 4.2.1 results in an energy saving between 3.6% for the lower publication rate and 80% for the higher one. There is an important benefit of using publication on demand mechanism. In this paper, we analyse the implementation of presence service in WSN. We discuss its requirements and present a new architecture to provide presence services in WSN. The mechanisms provided by our architecture bring significant advantages with respect to other publish/subscribe protocols in WSN. The publication on demand mechanism prevents to transmit publication messages without related subscriber nodes. In addition, this architecture provides a mechanism to avoid that subscriber node waits for the next presence information produced by publisher node. It reduces waiting time of subscriber nodes. Preliminary results presented in this paper show that the proposed architecture is suitable for WSN. The implemented "lossless" data aggregation algorithm would result in energy saving for publisher nodes. Moreover, it would reduce the traffic load in situations of network congestion. At the present time, more results are being obtained by simulation to quantify how much energy can be saved if we apply "lossless" data aggregation. Also we intend to concentrate our efforts in building and testing a hardware/software prototype.

Fig. 1 .

 1 Fig. 1. General Presence Service Architecture

Fig. 2 .

 2 Fig. 2. Proposed Presence Service Architecture for WSN

Fig. 3 .

 3 Fig. 3. Broker roles and broker domain

Fig. 4 .

 4 Fig. 4. Publication on demand

Fig. 5 .

 5 Fig. 5. Lossless Aggregation Algorithm

Fig. 6 .

 6 Fig. 6. Spent Time in the first publication

Fig. 7 .

 7 Fig. 7. Spent Time until reception of the first publication by subscriber node

Fig. 8 .

 8 Fig. 8. Publish messages transmitted without subscription

Fig. 9 .

 9 Fig. 9. Energy Consumption of Publications on Demand

Acknowledgments. This research has been funded by The Professional Excellence Program IFARHU-SENACYT-Panama and Spanish Government CICYT-TEC2009-11453.


D C Dimitrova
email: dimitrova@iam.unibe.ch

G Heijenk

J L Van Den Berg

S Yankov

Scheduler-dependent inter-cell interference and its impact on LTE uplink performance at flow level

The Long Term Evolution (LTE) cellular technology is expected to extend the capacity and improve the performance of current 3G cellular networks. Among the key mechanisms in LTE responsible for traffic management is the packet scheduler, which handles the allocation of resources to active flows in both the frequency and time dimension. This paper investigates for various scheduling scheme how they affect the inter-cell interference characteristics and how the interference in turn affects the user's performance. A special focus in the analysis is on the impact of flow-level dynamics resulting from the random user behaviour. For this we use a hybrid analytical/simulation approach which enables fast evaluation of flow-level performance measures. Most interestingly, our findings show that the scheduling policy significantly affects the inter-cell interference pattern but that the scheduler specific pattern has little impact on the flow-level performance.

Introduction

A key feature of packet scheduling in LTE networks is the possibility to schedule not only in time (as in UMTS/EUL) but also in frequency. The latter is enabled by the orthogonality between sub-carriers in SC-FDMA (Single Carrier Frequency Division Multiple Access) -the radio access technology chosen in LTE uplink. The smallest scheduling unit is termed a resource block (RB), see [START_REF] Holma | LTE for UMTS: OFDMA and SC-FDMA based radio access[END_REF], and is the intersection between the frequency and time domain scheduling units. Due to the organisation of the spectrum into resource blocks and the various allocation approaches of these over the users, each resource block may experience different inter-cell interference. Hence, we can observe multiple inter-cell interference processes each of which behaves as a stochastic process.

Inter-cell interference for LTE networks has been widely researched. Interestingly most studies concentrate on performance evaluation of packet scheduling mechanisms with interference mitigation either based on inter-cell interference coordination, see [START_REF] Mao | Adaptive soft frequency reuse for inter-cell interference coordination in SC-FDMA based 3GPP LTE uplinks[END_REF][START_REF] Xiangning | An inter-cell interference coordination technique based on users' ratio and multi-level frequency allocations[END_REF][START_REF] Zhang | Uplink power allocation for interference coordination in multi-cell OFDM systems[END_REF], or based on pre-existing knowledge of the interference, see [START_REF] Bonald | Capacity gains of some frequency reuse schemes in OFDMA networks[END_REF][START_REF] Xiang | Simulation based performance evaluation of ICI mitigation schemes for broadband wireless access networks[END_REF][START_REF] Xie | Resource allocation and reuse for inter-cell interference mitigation in OFDMA based communication networks[END_REF]. Still, they do not provide insights on the inter-cell interference process itself. We argue however that such insights are valuable for the design of an optimal allocation strategy. Therefore, in this study we take a step back and build an understanding of the mutual interaction between scheduling and interference. This is done in the context of LTE uplink with special focus on flow-level behaviour.

Studies that are closely related to our research are [START_REF] Fodor | Performance analysis of the uplink of a CDMA cell supporting elastic services[END_REF] and [START_REF] Racz | On the impact of inter-cell interference in LTE[END_REF]. In [START_REF] Fodor | Performance analysis of the uplink of a CDMA cell supporting elastic services[END_REF] two allocation schemes for LTE downlink with distinct frequency allocation approaches are compared taking into account flow-level dynamics. Despite being very insightful the research does not provide information on how the inter-cell interference pattern is affected by the type of allocation. It also does not discuss flow-level performance in terms of throughput (only SINR is evaluated). The authors of [START_REF] Racz | On the impact of inter-cell interference in LTE[END_REF] provide a valuable study on basic scheduling schemes and their impact on inter-cell interference. Unfortunately, the study considers only averaged metrics to describe the flow-level performance. The research inspired us to study the inter-cell interference process in an LTE uplink in more detail, including both scheduler's specifics and user behaviour.

The novelty of our research lays in two aspects. On the one hand, in the context of LTE uplink, we determine the dependency of the inter-cell interference on the scheduling strategy and, in particular, on the various ways to order users for service. On the other hand, user performance is evaluated at flow level taking into account the continuously changing number of ongoing flows in a system. Previously, see [START_REF] Dimitrova | Scheduler dependent modelling of inter-cell interference in UMTS EUL[END_REF], we showed that flow-level evaluation reveals important performance trends in the context of UMTS/EUL. We expect this general observation to hold for an LTE network as well; however we expect different outcomes. On the one hand, additional complexity is introduced by the new freedom to schedule in the frequency domain. On the other hand, due to the orthogonality of sub-carriers in LTE intra-cell interference is no more an issue. In order to investigate that we applied a significantly extended version of the hybrid analysis approach developed in [START_REF] Dimitrova | Scheduler dependent modelling of inter-cell interference in UMTS EUL[END_REF]. The basic separation between packet level (to capture specifics of the scheduler and the radio environment) and flow level (to model the random user behaviour) is preserved. However, we introduce additional means at packet level to capture the changes in inter-cell interference in both time and frequency. Further, at flow level the generation and completion of finite-sized flows is modelled by Markov chains from whose steady-state distribution performance measures, e.g. mean flow transfer times, were derived. Detailed discussion of the current research can be found in [START_REF] Dimitrova | Analysing uplink scheduling in mobile networks[END_REF].

The paper continues with Section 2, which elaborates on the investigated scheduling aspects. The system model is presented in Section 3, while Section 4 discusses the applied analysis approach. The discussion on numerical results is split over Section 5 (a study on the inter-cell interference process) and Section 6 (discussion of performance results). Finally, we conclude with Section 7.

Interference-aware scheduling

In LTE we have the freedom to schedule in both time and frequency domain with the smallest scheduling unit being a resource block (RB). In particular, we denote by a resource block4 a unit of bandwidth of 180 kHz and duration of 1 ms. If we denote by M the total number of RBs within the available system bandwidth during a single TTI, the scheduler can distribute at most M resource blocks over the active users. The total bandwidth that can be allocated to a single MS depends on the resource availability, the radio link quality and the terminal's transmit power budget. Although intra-cell interference is hardly an issue due to the sub-carrier orthogonality in SC-OFDM, situations are still possible when transmissions of users (allocated the same resource blocks) in neighbouring cells interfere with each other.

The scheduling scheme studied in our analysis is a resource fair scheduling scheme, which assigns equal resource shares to all active users, independently of their respective channel conditions. We consider the case of single resource block allocation and thus, given a total of M RBs in the total LTE uplink bandwidth, there are at most M users that can be served in one TTI. As a consequence there are M inter-cell interference processes -one for each RB.

An aspect of the scheduling is the ordering policy. The ordering policy dictates in which sequence users are selected for service and in which order the RBs are allocated to the selected users. We base the user selection on the location of the user in the cell. This spatial aspect is important since users at different locations generate different inter-cell interference values at the base station of a neighbour cell. Users close to the base station tend to generate similar levels. On the contrary, the interference levels from users located towards the cell edge vary significantly depending on their relative position to a neighbour cell. A user close to the neighbour cell generates high interference while a user on the opposite end (farthest from the neighbour cell) generates low interference levels. We have defined five distinct ordering policies accounting for both the spatial and frequency aspect of ordering. The first policy, which is also our reference case, is termed random and as the name suggests the selection of users and the allocation of RBs is based on a random principle, i.e. independently of the user's location. The other four policies have a more 'structured' approach. The CE-begin policy starts allocating RBs from the low end of the used spectrum to users closest to the base station and proceeds with farther located ones, see Figure 1(a) solid arrow. The CE-end policy, presented also in Figure 1(a), but dashed arrow, adopts the same spatial order but starts assigning first RBs from the high end of the spectrum. The EC-begin (see Figure 1(b), solid arrow) and EC-end (see Figure 1(b), dashed arrow) policies both start serving first the users located farthest from the base station; the former starts assigning RBs from the beginning of the spectrum while the latter starts from the high end of the spectrum. Note that the CE-begin and EC-end policies in fact differ since not at all times the total spectrum is occupied.

Model

We consider a two cell system -one cell (neighbour cell NC), where the interference originates, and one cell (reference cell RC), where its effect on user performance is observed. Such model, see Figure 2, suffices to observe the impact of the scheduler on the inter-cell interference pattern. The reference cell is divided in K zones of equal area which allows us to distinguish in user's performance depending on its location in the cell, i.e. distance to the base station. Each zone is characterised by a distance d i to the base station, i = 1, ..., K, measured from the outer edge of the zone. Additionally, to model the effect of user location on interference, the neighbour cell is divided in S sectors of equal area. The intersection of a zone and a sector is termed a segment, which is characterised by a distance d i to the base station of the NC and a distance d ij to the base station of the RC, j = 1, ..., S. The number of users in a cell and their distribution is given by the system state n. Given the chosen cell model the RC is characterised by n ≡ (n 1 , n 2 ...n K ) and the NC by n ≡ (n 11 , n 12 , ..., n 1S , n 21 , n 22 , ..., n KS ). We assume that the NC depends independently and is does not experience interference from the RC.

Further, users are uniformly distributed over the cell(s) and initiate new flow transfers according to a Poisson arrival process with rate λ. Flow size is exponentially distributed with mean F . Given the equal size of zones and sectors we can define arrival rate per zone (for the RC) λ i = λ/K and arrival rate per segment (for the NC) λ ij = λ/(KS). The number of active users is limited to the maximum number of resource blocks M that fit in the LTE uplink bandwidth. This is a reasonable assumption, which significantly eases analysis without biasing results 5 . Note that the assumption holds only for the scheduling schemes that we study; for other schemes it might not be applicable. Users apply a maximum transmit power P tx max unless lower level suffice. The signal received at the base station is affected by path loss and inter-cell interference. We apply the COST 231 Hata propagation model, see [START_REF] Holma | LTE for UMTS: OFDMA and SC-FDMA based radio access[END_REF], giving the path loss in logarithmic scale as:

L(d i ) = L f ix + 10a log 10 (d i ), (1)
where L f ix is a system parameter and a is the path loss exponent.

Analysis

The analysis of the two-cell model described in Section 3 needs to account for three aspects -(i) the inter-cell interference from the neighbour cell, (ii) modelling the inter-cell interference in the reference cell and (iii) user performance at flow level in the reference cell. The proposed analysis approach to tackle these issues is described in Section 4.2. Before that Section 4.1 discusses the user behaviour within a single cell (NC or RC), which is the basis for the two-cell system modelling.

Individual cell analysis

Since a user applies a P tx max even if a lower power would be sufficient to achieve the highest possible data rate, we are looking at a worst-case interference scenario. Accounting for thermal noise N and inter-cell interference I oc , the signal-tointerference-plus-noise ratio (SINR) is given as:

SIN R i = P rx i N + I oc , (2)
where i indicates the zone number, i = 1, ..., K, and the received power P rx i is calculated according to P rx i = P tx i /L(d i ). Note that the I oc component depends on whether the reference or the neighbour cell is modelled. In the calculation of the SIN R we have considered an upper and lower bound set by the technically feasible modulation and coding schemes (MCSs) and the minimum required level for successful reception respectively.

The data rate realised by a user (from zone i) when it is scheduled is what we term instantaneous rate r i . It is determined by the SINR as derived above, the possible MCSs and the receiver characteristics related to that MCS. In our analysis we use the Shannon formula modified with a parameter σ to represent the limitations of implementation, see Annex A in [START_REF]LTE; Evolved Universal Terrestrial Radio Access (E-UTRA); Radio Frequency (RF) system scenarios[END_REF]. Hence, for the instantaneous rate we can write:

r i = (m • 180kHz)σ log 2 (1 + SIN R i ), (3)
where 180 kHz is the bandwidth of a single RB and m is the number of RBs allocated to a user (in our case one). Note that both SIN R i and r i are calculated over the same RB allocation. Flow dynamics, i.e. the changing number of active users over time, are incorporated in our analysis by means of a continuous time Markov chain. A state in the model corresponds to the state n and the transitions rates are determined as follows: the forward transition rates are taken from the Poisson arrival rate λ; the backward transition rates are derived from the instantaneous rate r i taking into account the mean flow size F resulting in r i /F . The form of the Markov chain of a single cell depends on the modelling, e.g. the Markov chain of the RC has K dimensions corresponding to the K zones while The Markov chain of the neighbour cell is K × S dimensional (due to the division in segments). From the steady-state distribution of the Markov chains performance metrics such as mean flow transfer times can be derived. Generally, the steady-state distribution can be found either analytically or, when necessary, by simulation. More elaborate description of the model can be found in [START_REF] Dimitrova | Analysing uplink scheduling in mobile networks[END_REF].

Two-cell system performance

Applying the analysis from Section 4.1 to both the RC and NC we are able to evaluate the performance of the two-cell model, see Section 3. The evaluation goes through three phases.

Phase 1 In phase one we study the inter-cell interference generated by the neighbour cell towards the reference cell as a stochastic process. We are particularly interested in the observed interference levels and their probability distribution, reflected by the cumulative distribution function and the entire interference process. Generally, each segment in the NC corresponds with a different interference level. This since the inter-cell interference is in fact the received power at the base station of the reference cell from a user in the neighbour cell. Hence, the inter-cell interference from a segment ij can be derived as:

I ij oc = P tx max L(d ij ) , i = 1, ..., K, j = 1, ..., S. (4)
The probability distribution is determined by how often each particular value exhibits for a specific observation period. Hence, it depends on the traffic load and on the chosen scheduling (and ordering) policy. By applying the single-cell analysis for the neighbour cell we can derive the probability of each I oc level.

Phase 2 At this phase we account for the inter-cell interference at the base station of the reference cell. This is easily done due to the assumption that there are at most M users in the system. As result, given a state n, a user is always assigned the same RB, i.e. in the RC each user always experiences the same inter-cell interference. The exact interference value per RB per state and the duration for which it exhibited (how long the NC stayed in each state) are taken from a trace file generated at phase one.

Phase 3 The third and last phase of the evaluation is determining the user performance in the reference cell at the flow level. For this again the singlecell analysis is used but applied to the RC. In building the Markov model we dynamically account for the inter-cell interference measured as described in phase two. By simulating the Markov chain of the reference cell we derive its steadystate distribution and subsequently the mean flow transfer time for each zone.

Numerical results -inter-cell interference

In this section we present a discussion on the inter-cell interference levels and probability distribution for each of the ordering policies described in Section 2. Before that we give the applied parameter settings.

Parameter Settings

An LTE system with 10 MHz bandwidth is studied, which, given that a RB has 180 kHz bandwidth, results in 50 RBs available per TTI (including control overhead). Cell radius is set to 1 km. Cell division in ten zones, i.e. K = 10, and ten sectors (for NC), i.e. S = 10, is applied 6 . For the path loss we have used P L f ix = 141.6 dB considering height of the mobile station 1.5 m, height of the eNodeB antenna 30 m and system frequency 2.6 GHz; and a path loss exponent of a = 3.53. The thermal noise per sub-carrier (180 kHz) is -121.45dBm and with a noise figure of 5 dB the effective noise level per resource block is N = -116.45 dBm. The attenuation of implementation σ is taken at 0.4 flows/sec, see [START_REF]LTE; Evolved Universal Terrestrial Radio Access (E-UTRA); Radio Frequency (RF) system scenarios[END_REF]. Mobile stations have a maximum transmit power P tx max = 0.2 Watt. The lower bound on the SIN R is -10 dB while the upper bound on performance is determined by a 16QAM modulation, which corresponds to a SIN R of 15 dB. The average file size F is 1 Mbit and the rate λ at which users become active changes depending on the discussed scenario.

Inter-cell interference process

We start with a discussion on the inter-cell interference values that a user in the neighbour cell generates at the base station of the reference cell. The results A cumulative distribution function (CDF), although hiding the chronological development of the inter-cell interference, can provide valuable insights. Note that for each ordering scheme there are 50 inter-cell interference processes, one for each RB, see Section 2. We present the CDFs of the processes observed at RBs numbers 1, 10, 20, 30, 40 and 50. In all figures the x-axis indicates the observed inter-cell interference levels, while the y-axes plots the CDF function for each of the selected RBs. The arrival rate λ per cell is 4 flows/sec, which is close to the maximum of what the system can support, i.e. λ = 4.8 flows/sec with zero inter-cell interference.

Figure 4 presents the CDF curves observed in the case of a random ordering policy. As we can see the plots coincide, which can be explained by the random manner in which users are selected for service and are assigned RBs. For example, while at one time instant on RB1 a user from the centre can be served at the next instant a user from the cell edge can be chosen. Hence, each possible inter-cell interference level has equal chance to exhibit at any RB. The steep initial part of the curves is determined by the many segments with similar low I oc levels, see Figure 3.

Let us now consider the policies with strictly defined order of service shown in Figure 5. We notice that the graphs of the CE-begin and the CE-end policies are mirror images, as well as the graphs of the EC-begin and EC-end policies. This is the result of the same spatial ordering of users that each set of policies applies but starting from the opposite ends of the spectrum. Focusing on the CE-begin policy, presented in Figure 5(a), we observe that the CDF curves for different RBs differ significantly. As we move towards the end of the spectrum, initially (from RB1 to RB30) the probability that high inter-cell interference values occur increases. Subsequently however low (including zero) interference values are more often observed, i.e. have higher probability towards the end of the allocated spectrum (e.g. for RB40 and RB50). This behaviour is the combined result of two factors. On the one hand, with the particular spatial ordering (centre to edge), edge users receive RBs towards the end of the spectrum. These users, when located close to the reference cell, have much higher interference levels than centre users, which explains the initial increase in the probability of high interference levels. On the other hand, RBs at the high end of the spectrum are occasionally left unused when n < M holds, resulting in zero interference. Due to the similarities in behaviour, as already mentioned, the same observations hold for the CE-end scheme but in reverse order, see Figure 5(b).

The CDF curves for the EC-begin ordering policy are shown in Figure 5(c). Immediately we notice that the CDF curves of RBs towards the end of the spectrum are characterised with decreasing probability of high inter-cell interference levels and increasing probability of zero interference. We reason that cell edge users (with potentially high I oc ) are served first at the beginning of the spectrum, e.g. at RB1. Subsequent resource blocks are assigned to users located steadily closer to the cell centre, which have (on the average) lower induced interference levels. Finally, RBs at the end of the spectrum, e.g. RB40 and RB50, additionally experience the effects of a non-full system. The observations made for the EC-begin policy also apply for the EC-end policy taking into account the 'reverse' order of RB allocation, see Figure 5(d).

In summary we can say that (i) in a random ordering the inter-cell interference does not depend on the part of spectrum where it exhibits; (ii) a centre to edge ordering results in intersecting CDFs of different RBs, making the final effect on performance difficult to predict; and (iii) policies with edge to centre spatial ordering show potential for interference mitigation. The latter is based on the assumption that neighbour cells apply opposite spectrum allocation, e.g. EC-begin and EC-end, such that the interference experienced by the opposite ends of the spectrum is minimised.

Numerical results -flow-level performance

In this section we address five evaluation scenarios. In each scenario the NC adopts one of the five ordering policies (CE-begin, CE-end, EC-begin, EC-end or random) while the RC always adopts a CE-begin policy; this provides us a common base for comparison. We have evaluated performance in terms of mean flow transfer times for lightly and highly loaded system.

The user performance for each of the evaluation scenarios is presented in Figure 6. Two situations are shown -a lightly (arrival rate λ = 0.7 flows/sec) and a heavily (arrival rate λ = 4 flows/sec) loaded system. In order to ease interpretation of the results, for each situation, we have also shown a zoom in view of the last zone for which the differences in performance are most articulated.

The general conclusion from Figure 6 is that the particular choice of ordering does not influence significantly the flow-level performance. This may be slightly surprising recalling the big difference in CDF's of the inter-cell interference. We explain this behaviour by the specific choice of scheduling policy, namely a single RB per user. Under this condition relatively many users (50 with total system bandwidth of 10 MHz) can be served during one TTI and thus increasing the arrival rate does not lead to drastic changes in performance. We should also account for the fact that under low load the scheme is inefficient in the resource use, i.e. artificially keeps data rates lower than the potentially possible.

Although performance is similar there is a clear change between a lightly and heavily loaded system. In a lightly loaded system ordering from the high end of the spectrum in the NC, e.g. CE-end or EC-end, delivers better results (Figure 6(a)). In a system with low load mainly the RBs close to the spectrum end, where allocation starts, are used; RBs from the middle of the spectrum and further are often not allocated. Hence, starting RB allocation in neighbour cells from the opposite ends of the spectrum leads to zero interference for the majority of RBs in the RC. Starting RB allocation in neighbour cells from the same end of the spectrum results in interfering transmissions. In a highly loaded system however, see Figure 6(b), the CE-begin and EC-begin policies perform better. Under high load the majority of RBs are allocated and inter-cell interference appears in the bigger part of the spectrum. Hence, applying ordering policies in neighbour cells that start from the opposite ends of the spectrum allows to exploit the few interference free RBs occasionally left out due to insufficient users.

We can conclude that (i) the type of ordering policy does not impact flow-level performance significantly, regardless of the system load, and (ii) some performance gains, mainly for low system load, can be achieved if the ordering policies in neighbour cells are carefully chosen. The former behaviour is explained by two factors -with a single RB allocation 50 users can be served in parallel in 10 MHz band and having 50 users in the system (even under high load) is rare. Hence, flow changes only cause minor redistribution in the inter-cell interference over the spectrum, suggesting mostly constant interference levels in the long run.

Conclusions

This paper discussed the mutual influence scheduling and inter-cell interference have on each other. On the one side, we showed that the inter-cell interference pattern depends on the particular service policy used by the scheduler. On the other side, the study examined the impact of the inter-cell interference on user performance at flow level. The investigations were done for an access-fair scheduling policy with five different approaches of service allocation. Flow-level evaluation was enabled by the use of a hybrid analytical/simulation approach which benefits from providing insights on the performance while supporting quick evaluation.

The results show that the type of the ordering policy significantly affects the inter-cell interference pattern but that this scheduler-specific pattern has little impact on the flow-level performance. By including flow-level behaviour in the analysis we were able to show that certain factors that exhibit strongly at packet level do not affect the eventual performance on a longer time scale (at flow level). This conclusion should be drawn with care since it holds for the particularly studied scheduling scheme. Other schemes may show other behaviour. Still, knowledge on scheduler-dependent inter-cell interference can be used when studying scheduling schemes with interference mitigation.

Fig. 1 .

 1 Fig. 1. User ordering policies for scheduling in LTE uplink. (a) CE-begin (solid arrow) and CE-end (dashed arrow) and (b) EC-begin (solid arrow) and EC-end (dashed arrow).

Fig. 2 .

 2 Fig. 2. System model -reference cell and neighbour cell.

Fig. 3 .

 3 Fig. 3. Inter-cell interference levels.

Fig. 4 .

 4 Fig. 4. CDF of inter-cell interference levels for the random ordering policy.

Fig. 5 .

 5 Fig. 5. CDFs of the inter-cell interference for the four pre-set ordering policies.

Fig. 6 .

 6 Fig. 6. Mean flow transfer times for lightly (arrival rate λ = 0.7 flows/sec) and heavily (arrival rate λ = 4 flows/sec) loaded system.

In standards a resource block refers to the intersection of 180 kHz and 0.5 ms.

Our observations show that situations with more than M users form 10% of all observations for very high load but are below 1% for medium and low loads.

Finer division increases the differentiation ability in interference values but also the complexity of the model and simulation time. Tests with finer granularity did not show a significant change in the results.


Kunqi Guo

Lixin Sun

Xiaoqun Zhao

Shilou Jia

Cognitive Radio Access Optimization Using Multiparameter Match Ability Estimation

Keywords: Cognitive radio, match ability, utility function, average waiting time

In this paper, we formulate the optimal channel access of secondary user system in cognitive radio networks as the total reward maximization by Partially Observable Markov Decision Processes (POMDPs). Match Ability is proposed that takes allowable channel transmission rate and bit-error-rate (BER) required by receiving end into account. A heuristic greedy algorithm for channel access is proposed that is based on the local maximum match ability. By combining the utility function of queuing delay with local match ability, we improve the global average delay fairness. It is demonstrated by simulation results that as the average arrival rate increases, the large stable region of low delay can be maintained by adjusting utility function of the average waiting time under the condition that all the control information time overhead is not considered in the centralized global fairness control.

Introduction

A novel solution to radio spectrum underutilization problems is to adopt cognitive spectrum access. It can be realized by first sensing frequency bands that are not used by the primary users and then accessing current idle frequency band. To achieve this goal in an autonomous manner, multiple user cognitive radio networks need to be adaptive to dynamic wireless network characteristics to use radio spectrum most efficiently. In general, the secondary user that is driven by service requirement starts to sense each channel of primary users at any given time, with probable sensing results of channels including (1) a idle (active) channel accurately sensed to be idle (active) and (2) a idle (active)Wrongly sensed to be active (idle). In case [START_REF] Zhao | Decentralized cognitive MAC for opportunistic spectrum access in Ad Hoc networks: a POMDP framework[END_REF], the channel usage efficiency can be decreased because the same channel may be simultaneously used by more than two users, or not be utilized by secondary users. In secondary user system, the access decision is determined only according to the result of channel sensing. It can be completed by detecting the signal in frequency bandwidth of primary users at physical layer. A great deal of effort has been made by considering spectrum detecting method, accessing strategy and traffic tail characteristics estimation in time domain respectively. In [START_REF] Zhao | A survey of dynamic spectrum access[END_REF] and [START_REF] Zhao | Decentralized cognitive MAC for opportunistic spectrum access in Ad Hoc networks: a POMDP framework[END_REF], a hierarchical cognitive network is considered for cognitive user transmission opportunities in multiple channel communication system. The queue tail distribution of cognitive users is estimated for the detection of channels of primary users in [START_REF] Laourine | Queuing analysis in multichannel cognitive spectrum access: a large deviation approach[END_REF], with closedform expressions under two primary users.

While there has been much investigation in channel usage in cognitive radio networks including opportunistic access [START_REF] Chang | Competitive analysis of opportunistic spectrum access strategies[END_REF][START_REF] Chen | Joint design and separation principle for opportunistic spectrum access in the presence of sensing errors[END_REF][START_REF] Huang | Opportunistic spectrum access in cognitive radio networks[END_REF][START_REF] Urgaonkar | Opportunistic scheduling with reliability guarantees in cognitive radio networks[END_REF], spectrum sharing [START_REF] Wu | Distributed power allocation algorithm for spectrum sharing cognitive radio networks with QoS guarantee[END_REF][START_REF] Hou | Optimal spectrum sharing for multi-hop software defined radio networks[END_REF] and stable and efficient access method [START_REF] Cao | Stable and efficient spectrum access in next generation dynamic spectrum networks[END_REF][START_REF] Geirhofer | Cognitive Medium Access: Constraining Interference Based on Experimental Models[END_REF], there is a lack of the efficient effort in spectrum access efficiency of secondary users system that both the efficiency and fairness of the available spectrum utilization are considered. It is a complex multiple variants optimization problem we will face in this paper. Using Partially Observable Markov Decision Processes (POMDPs), we investigate the optimization objective that is formulated as the total reward maximization. The optimization implementation based on POMDP is to obtain the expected total reward by taking a sequence of decision actions. In our objective optimization for channel access, each access decision is made based on the multi-parameter match estimation considering the channel condition, the queuing delay, and the average arrival rate. To address this, we propose a novel channel access scheme using multidimensional parameters match ability maximization. In this scheme, for each secondary user, the statistical relationship between context parameters and the quality of service is derived according to queue theory. For wireless packet scheduling, much of efforts is made to achieve efficient wireless packet scheduling in [START_REF] Lu | Fair scheduling in wireless packet networks[END_REF], [START_REF] Ng | Packet fair queueing algorithms for wireless networks with location-dependent errors[END_REF] and [START_REF] Cao | Scheduling algorithms in broad-band wireless networks[END_REF]. Proportionally fair (PF) scheduling is investigated in [START_REF] Viswanath | Opportunistic beamforming using dumb antennas[END_REF], [START_REF] Borst | User-level performance of channel-aware scheduling algorithms in wireless data networks[END_REF] in order to maximize the long-term throughput in terms of user average channel conditions. In cognitive radio network, the interference to primary users may be increased due to the transmission power enhanced by a secondary user using a worse idle channel. In addition, a secondary user will reduce the utilization efficiency of channels being in better condition because its current service queue length is shorter. Thus, the trade-off between channel efficiency and queue length should jointly be considered for optimizing spectrum utilization. It becomes more important for secondary user system in cognitive radio networks using the constrained opportunistic spectrum access for service data transmission. In this paper, we focus on this problem. To our knowledge, as yet, it is not investigated. Considering cognitive access characteristics, we propose a novel metric Match Ability for channel access in secondary user system. Match Ability is constructed according to the required bit-error-ratio (BER) and the achievable transmission rate while considering the interference caused to its neighboring primary users. For single secondary user, Match Ability (MA) performs mapping between channel selection and the achieved quality of service (QoS). By this mechanism, secondary user accesses each channel based on greedy Match Ability maximization (GMAM). However, when more than two secondary users have the requirement of using the same channel, we need to consider the fairness problem of the channel utilization. This motivates us to implement it by combining centralized management control with GMAM based local access. To adapt well to the trade-off between queue delay and channel efficiency, we use extended Match Ability called EMA that is based on the principle of the utility maximization. In this scheme, we combine queue delay with MA of each secondary user by the utility function of queue delay. In addition, one of advantages of our methods is that it allows us to use conventional Proportionally fair scheduling (PF) as centralized management control by only replacing the single parameters with the integrated parameter MA, which can adapt well to the channel efficiency maximization requirement.

System Description and Optimization Formulation

In this section, we give the system description for the shared channel usage and analyze the optimization objective by partially observable Markov decision processes (POMDPs).

System Description

We consider a multiple channels cognitive radio networks with M primary users and N secondary users (cognitive users). In primary user system, each primary user has a channel (frequency band) to exclusively and randomly use. In secondary user system, each secondary user (cognitive user) uses idles channel of primary user to transmit its data queue in dynamic opportunistic way. The same spectrum channel can be shared at the same time between secondary user and primary user. Under this the setting, when we concentrate on idle channel usage, one of key problems we must face is the co-channel interference caused by secondary users to primary users. It mainly is due to two reasons. The first is that secondary users wrongly detect busy channels of primary users as being idle. The second is from how to utilize channels rightly sensed by secondary users as being idle. We focus on the latter one in this paper. Thus, our objective is equivalent to optimizing the utilization of channels shared between primary users and secondary users. The co-channel interference can be avoided when the same channel is used only by a primary user in the prescribed time, however, the spectrum utilization efficiency will be lowered when the space distance between a primary user and a secondary user is long enough to simultaneously use the same frequency band. With the interference protection of primary users, the optimization objective becomes a constrained optimization problem. Two schemes are considered in our optimization objective implementation. The first one is the distributed spectrum access that the channel access in secondary user system is based on GMAM. With the GMAM based distributed way, each secondary user can take shorter time from sensing to accessing channel. However, the channel utilization optimization is subject to both the allowable transmission rate and service queue condition that jointly leads to the constrained optimization problem. The total optimization depends on the optimum match between the allowable channel transmission ability and the queue condition. This needs a centralized based trade-off control to allocate the same channels that are requested by two or more secondary users. By combining GMAM for channel sensing with the queue delay state, we propose the secondary scheme called GMAMC that considers trade-off between channel transmission efficiency and queue delay. By maximizing the utility function of the average waiting time, GMAMC has the global balance ability by controlling greedy maximization degree used in GMAM, The framework for channel access in secondary user system is shown in Fig. 1.

Fig. 1. Framework for Channel Access in Secondary User System

Optimization Formulation

A POMDP denotes an observation (estimation) and decision process taking a sequence of actions to maximize the reward value under uncertain estimated factors. Let S, A, and O, be a set of states, a set of actions and a set of observations (estimated parameters). If the system is currently in a state ∈ s S, after an action (decision) is taken, the system is driven into a new state s '

∑ ∈ ∈ A a S s a s R , ) , ( max . Let 1 ] [ = k S j and 0 ] [ = k S j
denote the idle and busy condition of the channel of primary user j in time slot k respectively. Taking channel usage efficiency as the system optimization goal, we represent the system state S by the vector ] ,.... , [

2 M i S S S
. ij I is the interference caused by secondary user i using channel j to primary user j. We by threshold I denote the maximum interference threshold that primary user can tolerate. For each secondary user, we consider two channel access schemes including the distributed access action and the centralized control. The set of access actions is expressed by A. Let

∈ ij a A } 1 , 0 { = . Let ) ( ij ij a r
be the required reliable transmission rate of secondary user i over channel j by accessing mode ij a . By choosing the appropriate access scheme, our objective is to maximize the total system reward in terms of transmission rate

∑∑ = = N i M j ij ij a r 1 1 ) ( max (1) s.t. threshold ij i I I ) 1 < ∑ ; ∈ ij a ) 2 A } 1 , 0 { = where threshold ij i I I < ∑
guarantees that the total interference caused by secondary user to each primary user is under the specified condition. However, the channel utilization efficiency can be reduced because the channel access is determined only according to two states, the busy and idle condition. Dynamic network environment makes it feasible to allocate the same channel at the same time to a secondary user and a primary user due to time-varying user location diversity. We consider secondary user system that time is divided into slots of fixed length s T and define

       ≥ + < + = ∑ ∑ ≠ ≠ i n threshold nj ij threshold i n nj ij ij I k I k I I k I k I k S ] [ ] [ if , 0 ] [ ] [ if , 1 ] [ (2) where
} ,..., 2 , 1 { , } ,..., 2 , 1 { , M j N n i ∈ ∈ . In (2), 1 ] [ = k S ij and 0 ] [ = k S ij
represent idle and busy condition of channel i in time slot k respectively. It means that a secondary user access a channel of primary user system by considering the interference already suffered by secondary user i and the interference to be caused by secondary user i due to using this channel.

Multidimensional Parameters

By the effective bandwidth theory [START_REF] Chang | Stability, queue length, and delay of of deterministic and stochastic queueing networks[END_REF], [START_REF] Courcoubetis | Effective bandwidth for stationary sources[END_REF], we can obtain the probability that the packet delay violates the delay requirements using

max } Pr{ max D i e D W θδ - ≈ > (3)
where max

D

is the delay requirement and θ is a positive constant referred to QoS exponent, δ is a constant jointly determined by the arrival process and service process. It means that a large θ implies that a stringent delay requirement can be guaranteed by the system while a small θ implies that a loose delay requirement can be guaranteed by the system. We express by ] [k q i and i λ the amount of bits of secondary user i waiting for service at time s kT and the average arrival bit rate respectively. According to Little's principle, we obtain the average waiting time for

secondary user i, i W by i λ q W i i = where N k q q N k i N i ∑ - = ∞ → = 1 0 ] [ lim
. By the time low-pass window with length w T , we obtain the average queue length of secondary user i over the time window,

] [k q i ] [ ] 1 [ ) 1 ( ] [ k q k q k q i w i w ρ ρ + - - = (4)
where

w s w T T = ρ
. Using this time window, the average waiting time for secondary

user i at time s kT , ] [k W i is estimated by ] [ q [k] i i i k W λ = . Let ] [k A i
be the amount of arrival bits of secondary user i during time k. We by

] 1 [ - k R i
denote the supportable transmission rate of secondary user i for its service during time slot 1

- k , then, its queue length at time s kT , ] [k q i is s i i i i T k R k A k q k q ] 1 [ ] 1 [ ] 1 [ ] [ - - - + - = (5)
Thus, the predicted average waiting time at end of time slot k

] [k W i
is the function of the service arrival rate, the average queue length, and the obtainable transmission rate

( ) ( ) i s i i s i w i w i T k R T k q k q k W λ λ ρ ρ + - - - + - - = ] 1 [ ] 1 [ ] 1 [ 1 ] [ (6)
Since s T and w ρ are known at end of time slot k,

] [k W i is the function in terms of i λ , ] 1 [ - k R i and ] 1 [ - k q i
, reflecting the joint effect of multiple parameters on the average waiting time.

Channel Access

In this section, we propose two schemes for channel access in secondary user system, MA-weight channel access and Combining queuing delay with MA-weight for channel access.

MA-Weight Channel Access (GMAM)

During time slot k, secondary user i can decide whether to access channel j based on the maximization of Match Ability (MA) adopting distributed self-decision. Secondary user i using the channel j can get Match Ability

j i MA ] [ ] [ ] [ k S k R k MA ij j i j i = (7)
where

] [k S ij
is given by ( 2) and ] [k R j i is the achievable transmission rate of secondary user i using channel j that can satisfy the required bit-error-rate

( i BER ) at receiving end. If QAM modulation is used, we can estimate ] [k R j i from ( )         - = i j i j i BER k k R 5 ln ] [ 5 . 1 1 log ] [ 2 γ (8) where ] [k j i γ
is the SINR of the transmission link of the secondary user i using channel

j during time slot k [19]. Let ] [k h ij and ] [k g ij
represent the pathloss power gain and the normalized composite of shadowing and fading random variable with unit mean of the transmission link from secondary user i to primary user j respectively. Let where ] [k P i be the transmitting power of secondary user i. If secondary user i complete one transmission during time slot t by ] [k R j i , then we can obtain the power of interference received at primary user

] [k I ij by ] [ ] [ ] [ ] [ k g k h k P k I ij ij i ij =
. Due to the location dependence of wireless link, the maximization of the total MA results in the high computation complexity of maximizing the total ] [k MA j i . To reduce complexity, we propose low complexity heuristic distributed algorithm based on greedy match ability maximization (GMAM) search that is formulated by

[ ] { } ] [ max arg k MA k SU j i = (9) where ]
[ ; ,..., 2 , 1 k D j N i i ∈ =
. By [START_REF] Hou | Optimal spectrum sharing for multi-hop software defined radio networks[END_REF], each secondary user at end of current time slot k, selects the channel with the local maximum match ability out of channels that can be sensed. Two factors, the link supportable transmission rate and the maximum interference power to be tolerated by the primary user are considered in [START_REF] Hou | Optimal spectrum sharing for multi-hop software defined radio networks[END_REF]. The best short term performance achieved by [START_REF] Hou | Optimal spectrum sharing for multi-hop software defined radio networks[END_REF] depends on the available optimal match between two factors during current time slot.

3.2

Combining Queue Delay with MA for Channel Access (GMAMC)

Trade off between resource efficiency and fairness can be realized by maximizing system utility function [START_REF] Song | Cross-Layer Optimization for OFDM Wireless. Networks-Part I: Theoretical Framework[END_REF]. Due to the balance ability of maximizing utility, we use the utility function to determine the access priority for secondary users having the requirement of using the same channel. The delay performance is subject to both allowable channel transmission ability and queue condition. Consider both the transmission efficiency and delay fairness, we use the utility function of the average waiting time to control the trade-off between maximum match ability based transmission efficiency and average queuing delay. The utility function for this purpose is ( )

N i k W k W U b i i i ,..., 2 , 1 ]; [ ] [ = = (10)
Let w ρ be small enough. Since

( )

] [k W U i ∆
corresponds to the utility addition that should be maximized during current time slot and

] 1 [ - k R i
is known before the end of current time slot k, when the arrival process is given, using a first-order approximation of the Taylor's expansion, we can formulate the utility maximization based optimization objective as

) ] [ ( max ] [ 1 i i k W W N i i i k R dW dU i i λ = = ∑ (11) Let ] [k EMA j i be the extended Match Ability at time slot k of secondary user i denoted by ] [ ] [ ] [ 1 k MA k W k EMA j i b i j i - =
. The total performance optimization is to achieve the optimal trade-off between queue delay and channel transmission efficiency that can be realized by maximizing the total extended MA

      ∑ = N i j i i k EMA 1 ] [ 1 max λ (12) Let ( ) ,..., 2 , 1 ] [ N i k MA M j i i = = and i b i i k W T λ ] [ 1 - =
be the match ability and the factor of service condition of secondary user i in time slot k respectively.

First, we need find the global optimal trade-off parameter opt G . It can be realized

{ } N i k M k W G i i b i opt ,.., 2 , 1 ; ) ] [ ] [ ( min 1 = - - λ
. By this method, the channel j is likely allocated to a secondary user that has

i i b i k M k W λ ] [ ] [
approximating to opt G . The service arrival rate, the queue delay and the allowable transmission rate are jointly considered to determine the current opt G . The complexity of the algorithm is low because of the computing overhead largely depending on in sorting-search for the global trade-off parameter opt G [START_REF] Kruse | Data Structures and Program Design in C++[END_REF].

Performance Evaluation

In our simulation, each channel used by secondary users is assumed to suffer slow fading. Let the BER required by the receiving end of each secondary user be 6 10 -. It is assumed for GMAM that each secondary user can know the interference of its neighboring primary users through its local spectrum sensing. An ON-OFF model is used to model the traffic streams of secondary user. The length of time slot is 2 ms. The ON period is modeled as Pareto distribution and an exponential distribution is used for OFF duration. The frequency bandwidth of each channel is 20 kHz. Four different rates respectively for the utility function [START_REF] Cao | Stable and efficient spectrum access in next generation dynamic spectrum networks[END_REF]. Figure 2 shows the obvious differences between GMAM and GMAMC in terms of queuing delay under the average arrival rate

Conclusion

Based on POMDP decision theory, we formulate the optimal channel access of secondary user system in cognitive networks as the total reward maximization. Two schemes for the optimization objective are proposed based on maximizing the short term spectrum efficiency and minimizing the long term delay fairness difference respectively. We demonstrate by simulation results that the large stable region of low the average delay can be maintained by the centralized global fairness control scheme. Combining the schemes proposed in this paper with efficient time window based traffic control is our future research.

  access and the centralized control scheme respectively for access channel j adopted by secondary

efficiently by binary search ( 1

 1 channel j to the secondary user i which can satisfy

  used for MA maximization based adaptation transmission in secondary user system (SUS). First, we consider a square area of size m 500 500 × in which 10 secondary users and 10 primary users are fixedly and randomly deployed

.

  Let SU denote the number of secondary users.

  Figure 3 and 4 show the average delay under different average arrival rates in SUS. Let the exponent of utility function b be 4 . The effect of the trade-off exponent b on the queuing delay is shown in Figure 5. It can be seen that the maximum lower delay stable region of about 7 ms is achieved by GMAMC when 5 = b that can allow the average arrival rate of 180 kbps in SUS. The better delay performances result from the adaptive trade-off between channel access efficiency and queue delay fairness that can be provided by maximizing the utility function of queue delay.

Fig. 2 .Fig. 3 .Fig. 4 .Fig. 5 .

 2345 Fig. 2. Delay violation probability difference between GMAMC and GMAM

  from s and as a result, a reward value

	R	, ( a s	)	is obtained. Due to uncertain predicted parameters, the end state s ' can
	be modeled as a conditional probability function	T	(	s	,	a	,	s	,	)	=	p	(	s	,	s	,	a	)	. The
	optimization objective is to maximize the total reward:

  Each secondary user can access one channel by one of two ways indicated by

	user i.
	Secondary	User
	S t
	Data Arrival Rate	Allowable Transmission Rate
	Data Queue	Spectrum Sensing	Interfere
	Queue Waiting	BER	MA
	Time
	GMAM	EMA	GMAM
	C	Channel Access
		Shared Radio Spectrum
		Primary	User