MIXED INTEGER PROGRAMMING BASED TECHNIQUES FOR RESOURCE ALLOCATION IN UNDERLAY COGNITIVE RADIO NETWORK

By Kadiri Kamoru Oluwatoyin, Kehinde Olalekan Samson, Federal Polytechnic Offa, Kwara State, Nigeria, Department of Electrical/Electronic Engineering
Corresponding email: samopascal@yahoo.com

ABSTRACT
In this work, the underlay cognitive radio network (CNR) and methods of improving its resource allocation algorithm was duly considered. Also, the mixed integer programming techniques was proposed in order to enhance the traditional method of sharing/allocation of resources in this type of network.
Keyword: Cognitive Radio Network; Resource Allocation; Mixed Integer; Secondary Users; Spectrum Utilization.

INTRODUCTION
The fast growing wireless technology is expected to create a great demand on spectral resources in the generation wireless systems to come. Hence one of the most important research goals in designing wireless communication system is to achieve high spectrum utilization. In view of this, the interest in developing efficient methods for spectrum management and sharing is ever increasing. A new paradigm in wireless communications to improve the utilization of limited spectrum resources is the Cognitive Radio (CR) [1]. Cognitive radio (CR) is a new emerging technology to improve the radio spectrum utilization effectively [2]. The primary task of CR is that the secondary users (SUs) senses the spectrum dynamically and allocate the unused radio spectrum to SU when the primary users (PUs) are idle [3, 4].

Within the secondary users in cognitive radio network (CRN), the resource should be allocated dynamically with respect to sense radio atmospheres for improvement of effective utilization of radio spectrum [5].

There are three main cognitive radio network paradigms: underlay, overlay, and interweave [6]. The underlay paradigm allows secondary users to operate if the interference they cause to primary users is below a given threshold or meets a given bound on primary user performance degradation. In overlay systems the secondary users overhear the transmissions of the primary users, and then use this information along with sophisticated signal processing and coding techniques to maintain or improve the performance of primary users, while also obtaining some additional bandwidth for their own communication. Under ideal conditions, sophisticated encoding and decoding strategies allow both the secondary and primary users to remove either all or part of the interference caused by other users. In interweave systems the secondary users detect the absence of primary user signals in space, time, or frequency, and opportunistically communicate during these absences. For all three paradigms, if there are multiple secondary users then these users must share bandwidth amongst themselves as well as with the primary users, subject to their given cognitive paradigm [7].

In the underlay paradigm, the concurrent primary and secondary transmissions may occur only if the interference introduced by the secondary transmitters at the primary receivers goes below some acceptable threshold. Rather than concentrating on the exact interference it causes, a secondary user can spread its signal over a very wide bandwidth in a manner that the interference power spectral density is below the noise floor at any primary user location. These spread signals are then dispread at each of their intended secondary receivers. This spreading technique is the basis of both spread spectrum and ultra-wideband (UWB) communications. Alternatively, the secondary transmitter can be very conservative in its output power to ensure that its signal remains below the prescribed interference threshold. In this case, since the interference constraints in underlay systems are typically quite restrictive, this limits the secondary users to short range communications. Both spreading and severe restriction of transmit power avoid exact calculation of secondary user interference at primary receivers, instead using a conservative design whereby the collective interference of all secondary transmissions is small everywhere.

Determining the exact interference a secondary transmitter causes to a primary receiver is one of the biggest challenges in underlay systems. The secondary user can determine this interference at a given primary receiver by overhearing a transmission from that primary user if the link between them is reciprocal. For MIMO systems, a secondary user only interferes with a primary user in their overlapping spatial dimensions. If the secondary user occupies only the null space of the MIMO primary receiver, no interference is caused, and hence this falls within the interweave paradigm discussed below, whereby the primary and secondary users occupy orthogonal spatial dimensions. The underlay paradigm is most common in the licensed spectrum, where the primary users are the licensees, but it can also be used in unlicensed bands to provide different classes of service to different users.

The rest of this paper is organized as follows: in Section 2 we give an overview of relevant research in the area of cognitive radio networks. In Section 3, we discuss mixed integer programming, followed by system model in Section 4. Finally, in Section 5, we present our conclusions.

RELATED WORK
There are series of papers that has been published on optimizing resource allocation on underlay cognitive radio network. One of these papers is [5] “Dynamic Resource Allocation for Heterogeneous Services in Cognitive Radio Networks with Imperfect Channel Sensing”.

In this work, a cognitive radio system including a primary network and a secondary network which is operated in the form of time slotted manner was considered. There is a secondary base station and Knot SUs with heterogeneous services requesting in the secondary network. It was assumed that the primary network and secondary network take the orthogonal frequency-division multiple access (OFDMA) technology. There are M channels owned by the primary base station in the primary network. In each time slot, the secondary network can sense the M channels and opportunistically utilize the idle channels for heterogeneous services. The time slot for the secondary network consists of three parts: sensing time, resource allocation time and data transmission time.

In the sensing time, the secondary network senses the M channels licensed to the primary network and determines the available idle channels. However the limitation of this work is that it does not consider how to do joint access control and resource allocation to maximize the total system capacity and minimize the interference to PUs when there are sensing errors in the secondary network.

In [8] “Multiuser Resource Allocation Optimization Using Bandwidth-Power Product in Cognitive Radio Networks”, the problem of resource allocation optimization is studied for a single-cell multiuser cognitive radio network in the presence of primary user networks. The spectral access of the cognitive radio network is based on Orthogonal Frequency Division Multiple Access (OFDMA). A joint bandwidth and power allocation is performed so that users’ rate requirements are satisfied, and the integrity of primary user communication is preserved. In this work, two unique challenges are addressed.

Another work is [9] “MIMO-OFDM based Cognitive Radio Networks Capacity analysis with Water Filling Techniques”, water filling algorithm was discussed which has been used for allocating the power to the MIMO channels in cognitive radio network so as to enhance the capacity of the network. Here we present a theoretical framework for allocating the power considering a 4×4 MIMO system and the system is assumed to be MIMO-OFDM based cognitive network and the channel to be flat as under this the convolution integral becomes a simple multiplication operator. Also, the comparison of various systems with and without the proposed water filling algorithm for the available power budget was considered. It can be observed from the graphs that the efficiency of the system is enhanced with the proposed water filling algorithm and also it is observed that the outage probability shows constant value as compared to the outage observed in the systems without the water filling algorithm.

Even though the above papers and many more have done well in efforts to optimize resource allocation in cognitive radio network, yet none of them, to the best of the research made were able to focus interest on the optimization of the underlay paradigm, especially by using a very effective optimization technique such as the mixed integer programming.
Mixed Integer Programming
Mixed-integer optimization represents a powerful framework for many mathematically modelling optimization problems that involve discrete and continuous variables. During the last five years there has been noticeable increase in the development of these models in process systems engineering [10]. For more than twenty years, mixed-integer linear programming (MILP) methods and codes have been available and applied to many practical problems; for instance, see [11].

The most common method is the LP-based branch and bound method which has been implemented in powerful codes such as OSL, CPLEX and XPRESS. Recent trends in MILP include the development of branch-and-cut methods such as the lift-and-project method by [12] in which cutting planes are generated as part of the branch and bound enumeration.

It is not until recently that several new methods and codes are becoming available for mixed-integer nonlinear problems (MINLP) [13]. In this paper we provide a review the various methods emphasizing a unified treatment for their derivation. As will be shown, the different methods can be derived from three basic NLP sub-problems and from one cutting plane MILP problem, which essentially correspond to the basic sub-problems of the Outer-Approximation method. Properties of the algorithms are first considered for the case when the nonlinear functions are convex in the discrete and continuous variables. Extensions are then presented for handling nonlinear equations and non-convexities. Finally, the paper considers properties and algorithms of the recent logic-based representations for discrete/continuous optimization that are known as generalized disjunctive programs. Numerical results on a small example are presented comparing the various algorithms.

System Model
Modelling non-convex functions has been a central topic of MIP formulations since its early developments. Consider the mathematical programming problem given by

Where : [0, u] → Q are univariate piecewise linear functions of the form

for given breakpoints 0 = < < · · · < < = u, slopes {}k i=1 ⊆ Q, and constants {}k i=1 ⊆ Q. We assume that the slopes and constants are such that the functions are continuous, but not convex. For instance, one of these functions could be

Because the functions we consider are non-convex, we cannot transform into an equivalent LP problem. However, we can transform it into an MIP problem as follows. The first step in the transformation is to identify a set or a constraint that we want to model as an MIP problem. In the case of a piecewise linear function f, an appropriate set to model is the graph of f given by gr(f) := {(x, z) ∈ Q × Q : f(x) = z}. Indeed, we can reformulate by explicitly including gr() to obtain the equivalent problem given by

In applying the above MLP technique to the underlay cognitive radio network, connections existing between each of the secondary users can be represented mathematically in a linear equation in form of matrix as shown above while represents the minimum connectivity path for allocating resources for connected secondary users [17].

CONCLUSION
This paper has been able to explain in details the cognitive radio network and also considered the various approaches that have been implored in improving the resource allocation protocol/algorithm involve in the CRN. It has also proposed the mixed integer based technique for the allocation of resources.

REFERENCES
[1] Bo, G., & Yifeng, H. (n.d.). Optimal Resource Allocation for Video Streaming over Cognitive Radio Networks. 1.
[2] Xie, R., Richard, F., & Ji, Y. H. (n.d.). Dynamic Resource Allocation for Heterogeneous Services in Cognitive Radio Networks with Imperfect Channel Sensing. 1.
[3] Haykin, S. (2005). Cognitive radio: Brain-empowered wireless communications. IEEE J. Sel. Areas Commun. , 23 (2), 201–220.
[4] Yu, F., Huang, M., & Tang, H. (2010). Biologically inspired consensusbased spectrum sensing in mobile ad hoc networks with cognitive radios. IEEE Networks , 26–30.
[5] Tamilarasan, S., & Kuma, P. (2016). Dynamic Resource Allocation with Imperfect Channel Sensing –Heterogeneous Services in Cognitive Radio Network. International Journal of Engineering Technology, Management and Applied Sciences , 4 (7), 1.
[6] Blasco-Serrano, R., Lv, J., Thobaben, R., Jorswieck, E., Kliks, A., & Skoglund, a. M. (n.d.). Comparison of Underlay and Overlay Spectrum Sharing Strategies in MISO Cognitive Channels. 1
[7] Goldsmith, A., & Mari´c, I. (2009). Capacity of Cognitive Radio Networks. Proc. IEE, 894–914.
[8] Tachwali, Y., Lo, B. F., Lo, B. F., & Agust´, R. ( 2013). Multiuser Resource Allocation Optimization Using Bandwidth-Power Product in Cognitive Radio Networks. IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS , 451.
[9] Ngangbam, R., Anandan, R., & Ngangbam, C. (n.d.). MIMO-OFDM based Cognitive Radio Networks Capacity analysis with Water Filling Techniques. International Journal of Computer Science & Communication Networks, 160.
[10] Biegler, L., Grossmann, I., & Westerberg, A. (1997). Systematic Methods for Chemical Process Design. Prentice-Hall.+
[11] Nemhauser, G. L., & Wolsey, L. A. (1988). Integer and Combinatorial Optimization. New York: Wiley-Interscience.
[12] Balas, E., Ceria, S., & Cornuejols, G. A. (1993). Lift-and-Project Cutting Plane Algorithm for Mixed 0-1 Programs. Mathematical Programming, 295-324.
[13] Borchers, B., & Mitchell, J. (1994). An Improved Branch and Bound Algorithm for Mixed Integer Nonlinear Programming. Computers and Operations Research , pp. 359-367.
[14] Gupta, O. K., & Ravindran. (1985). Branch and Bound Experiments in Convex Nonlinear Integer Programming. Management Science , 1533- 1546.
[15] Nabar, S., & Schrage, L. (1991). Modeling and Solving Nonlinear Integer Programming Problems. Presented at Annual AIChE Meeting. Chicago.
[16] Grossmann, I., & Kravanja, Z. (1997). Mixed-integer Nonlinear Programming: A Survey of Algorithms and Applications. The IMA Volumes in Mathematics and its Applications (93), 73-100.

[17] Juan Pablo Vielma (2015). Mixed Integer Linear Programming Formulation Techniques. Society for Industrial and Applied Mathematics, SIAM REVIEW Vol. 57, no.1, pp. 3-57.

LEAVE A REPLY

Please enter your comment!
Please enter your name here