ABSTRACT

The increasing interest for wireless communication services and scarcity of radio spectrum resources have created the need for a more flexible and efficient usage of the radio frequency bands. Cognitive Radio (CR) emerges as an important trend for a solution to this problem. Spectrum sensing is a crucial function in a CR system. Cooperative spectrum sensing can overcome fading and shadowing effects, and hence increase the reliability of primary user detection. In this paper we consider a system model of a dedicated detect-and- forward wireless sensor network (DetF WSN) for cooperative spectrum sensing with k-out-of-n decision fusion in the presence of reporting channels errors. Using this model we consider the design of a spatial reuse media access control (MAC) protocol based on TDMA/OFDMA to resolve conflicts and conserve resources for intra-WSN communication. The influence of the MAC protocol on spectrum sensing performance of the WSN is a key consideration. Two design approaches, using greedy and adaptive simulated annealing (ASA) algorithms, are considered in detail. Performance results assuming a grid network in a Rician fading environment are presented for the two design approaches.

Keywords:

Cooperative Spectrum Sensing, Wireless Sensor Network, Media Access, Spatial Reuse

1. Introduction

With the rapid development of wireless technology and the growing number of innovative telecommunication services, the scarcity of radio spectrum resources has become a critical issue. Static allocation within the conventional spectrum management framework causes a bottleneck for efficient utilization of radio spectrum [1] . Relying on dynamic and opportunistic spectrum access technolo- gies, Cognitive Radio (CR) systems offer a promissing solution to spectrum shortage [2] . A typical example is the opportunistic use of the unused spectrum in TV broadcasting bands by IEEE 802.22 WRAN [3] systems. Another example is the concurrent operation of LTE and Wi-Fi in unlicensed bands via dynamic spectrum access techniques [4] [5] .

An important function in CR systems, that makes possible the discovery of free channels for opportunistic use, is spectrum sensing. Single user sensing performance is often compromised by multipath fading, shadowing, and uncer- tainty of background noise [6] . Sensing performance, however, can be improved by using Cooperative Spectrum Sensing [7] [8] . In such a scheme local spectrum measurement are performed at each sensing node, and a final decision is made after fusing the information from all cooperating sensors. Cooperative spectrum sensing provides better spatial coverage as well as multi-user diversity gains that improves the detection reliability, and helps to reduce the sensitivity require- ments of single detectors [9] .

A common realization method of cooperative spectrum sensing integrates the sensing function into secondary user (SU) terminals. However, a sufficient number of adequately located SUs is required to obtain accurate detection results. Furthermore, the SU cannot transmit data during the sensing period [10] [11] , reducing the user information transport efficiency, while still consuming baterry power. An alternative approach is External Sensing, which relies on a dedicated wireless sensor network (WSN) for spectrum sensing. A dedicated WSN can be deployed and controlled by the cognitive service provider, and can aid an SU to access the licensed spectrum. Such a scheme can cope with the hidden primary user problem, and guarantees robustness against model uncerta- inty induced by fading and path loss [12] . Moreover, in such a scheme sensors neither need to be mobile nor battery-powered, and the cost, complexity and power consumption of SU terminals can be reduced.

In this paper, we consider a Detect-and-Forward (DetF) distributed WSN for cooperative spectrum sensing. The operation of this scheme does not rely on centralized control requiring a separate decision fusion center. Hence better flexibility and scalability can be provided by such an approach [13] . However, a proper media access control (MAC) protocol is required to coordinate trans- missions between sensors in order to efficiently use resources and resolve contention. In an WSN, the most significant design constraint is usually the limited energy budget of a sensor node together with the requirement of net- work longevity [14] [15] . However, in our DetF WSN sensors are assumed to be fixed in the deployment region and do not depend on limited battery power. Thus, spectrum efficiency and interference, instead of energy efficiency, become the primary issues. Another special part of our MAC design for this DetF WSN is its performance as a cooperative spectrum sensing system.

More specifically, the contributions of this paper are three fold: 1) We propose a spatial reuse MAC protocol based on TDMA/OFDMA for exchanging sensing results that avoids primary conflicts and saves bandwidth resources. As design approaches, we consider a greedy algorithm as well as an adaptive simulated annealing (ASA) technique. 2) We analyze the degradation introduced by reporting channel errors on cooperative spectrum sensing performance with the k-out-of-n decision fusion rule. 3) For illustrative purposes we present numeri- cal results, in terms of Receiver Operating Characteristics (ROC) curves, that demonstrate the spectrum sensing performance of such DetF WSN with the spatial reuse MAC protocol in a grid network. However, the proposed spatial reuse MAC protocol is not limited to a grid network only, and can be employed in any network structure with an associated cooperating partner selection scheme. The rest of this paper is organized as follows. Section 2 presents the system model and analyzes the performance of cooperative spectrum sensing using k-out-of-n decision fusion with imperfect reporting channels. The designs of the MAC protocol by using the greedy algorithm and the ASA technique are presented in Section 3. Numerical performance results for a grid network are presented in Section 4, and the conclusions are drawn in Section 5.

2. System Model and Preliminaries of Cooperative Spectrum Sensing

(A) Network architecture

Consider a distributed DetF WSN illustrated in Figure 1, where the nods have spectrum sensing as well as communication capabilities. The operation of this WSN can be divided into two stages: 1) Intra-WSN Sensing and 2) WSN-SU Handshaking. The first stage is summarized as follows:

a) Measurement Phase: A sensor measures the received signal over the channel of interest.

b) Local Decision Phase: A sensor makes a hard decision based on its measurement via a local spectrum sensing scheme [16] .

c) Communication Phase: Sensor exchange their local decisions through dedicated reporting channels. The cooperation between sensors is determined by a partner selection scheme specified by an adjacency matrix. When then this indicates that there is cooperation from the partner to recipient. Otherwise,.

d) Final Decision Phase: A final decision is made by each sensor through combining the decisions gathered (including its own), according to a decision fusion rule.

e) The four phases above are repeated for another channel of interest.

In the second stage the sensing results are made available to SUs, which is a topic beyond the scope of this paper that focusses on spectrum sensing.

(B) Channel model

All wireless channels in the system, including the reporting as well as the detecting channels, are modeled as time-invariant small-scale fading including path loss and additive interference.

Path loss model

We use the simplified model of ( [17] , p. 47) to characterize the variation in the received signal power with distance:

(1)

where the path loss is defined as the ratio of the transmit power over the received power, is a constant which depends on the antenna cha- racteristics and the average channel attenuation, is the distance between the transmitter and receiver, and is the path loss exponent.

Small scale fading model

We assume small scale Rician fading for each communication link ( [18] , p. 23), with probability density function (PDF) of the instantaneous signal-to-noise ratio (SNR) given by

(2)

where, is the Rician fading parameter, is the average received SNR, and is the 0th order modified Bessel function of the first kind. When combining the effects of path loss and fading, the received SNR ( [17] , p.77) is, where represents the transmit SNR. Our analysis can be applied also to other fading models, when (2) is replaced by the corresponding PDF. In addition, we ignore the impact of shadowing in this paper since the sensing nodes can be placed such that reporting channels are not impaired by this phenomenon. As far as the sensing channels are concerned, we assume that if a sensing node is shadowed, then it is disregarded.

Interference model

We assume an additive interference model, in which a link treats all the other on-going transmissions on the same channel as noise [19] . Let be the channel gain, the transmit power of, and the thermal noise power (where the transmission bandwidth is). The received Signal to Interference plus Noise Ratio (SINR) at is

(3)

where denotes the set of sensors, other than, transmitting simulta- neously on the same channel, and from (1).

(C) Cooperative spectrum sensing through imperfect reporting channels

We assume that each sensor employs a local energy detector, and a channel to be sensed has center frequency. The received signal passes through an input bandpass filter of bandwidth centered at, then a squaring device and integrator measure the received energy over an observation interval. Finally, the test statistic, , formed by the integrator is compared to a threshold, to produce the local decision [20] . The probabilities of detection and false alarm over AWGN channels are given, respectively, by

(4)

(5)

where denotes the energy detection threshold, is the instanta-

neous received SNR of primary signal at (is the received primary signal power at, is the noise power spectral density), is the time-bandwidth product which is assumed to be an integer for simplicity, , are the complete and upper incomplete gamma functions, and is the generalized Marcum Q-function. With Ricean fading we need to average (4) and (5) over using (2), resulting in the average probabilities of detection and false alarm [21] :

(6)

(7)

where is the same as that over an AWGN channel as it is independent of received SNR. When, (6) has the form

where is the average received SNR of the primary signal [21] . In the follow- ming analysis, we use for simplicity.

We assume that each sensing node gathers hard decisions from other partner nodes including its own decision, and uses the k-out-of-n fusion rule to produce a final decision ( [22] , pp. 59-61). We define the partner set of a sensor as

, and use to denote the number of partners, i.e.,

where represents the cardinality of a set. Sensor declares (signal is present in the channel) when at least k out of the decisions are. Otherwise, the output is (channel is free).

The channel from to is modeled as a binary symmetric channel (BSC) with cross-over probability, representing the uncoded BEP [8] . Without loss of generality, in our work we choose binary phase shift keying (BPSK). The average BEP for BPSK in Rician fading over reporting channel is ( [18] , p. 126)

(8)

where is the Rician parameter, and is the average received SNR at determined by the path loss as well as both AWGN and additive interference.

Hence from (3),.

If an error occurs when transmits its decision to, a (or) decision of will be turned into (or) when received by. Thus, as shown in [8] , , the equivalent probabilities of detection and false alarm received by are

(9)

(10)

We assume that each sensor experiences i.i.d. Rician fading, and performs spectrum sensing independently. In this paper, we employ combinatorial nota-

tions as in [23] . We use to represent the set of all m-combinations of having members, repre-

sents one m-combination of (are arranged in lexicographic order), and denotes the relative complement of in. Then from ( [16] , Equation (11)) we obtain the probabilities of detection and false alarm at sensor after k_i-out-of-n_i decision fusion,

(11)

(12)

where and are given in (9) and (10), and is ‘s decision fusion threshold.

In Figure 2 we present the impacts of reporting channel errors on cooperative spectrum sensing performance by illustrating ROC curves of versus. There are 5 sensors employing identical energy detection thresholds, and makes a global decision. Thus, we omit the second subscript in and. The Rician fading parameter is, and the average received SNR of the primary signal is identical at each sensors. In Figure 2(a), the vertical separation between curves indicates the degradation introduced

by reporting channel errors for OR rule (), which is small in high range, and increases when decreases. Moreover, for ROC curves with erroneous reporting channels when decreases to a certain level will drastically decrease, and any lower than a threshold cannot be achieved. In Figure 2(b), we fix the average received SNR on each reporting channel, and compare the ROC curves with different and. For a certain, higher results in better detection performance. However, the minimum values of and are no longer 0 as for error-free reporting channels. From (6), (7), (9) and (10), we have:

-When, and thus

-When, and thus

Property 1. For a partner set, and decision fusion threshold, if each (or) assumes minimum value, then (or) reaches minimum value. If each (or) assumes maximum value, then (or) reaches maximum value.

Proof: Suppose that there are Bernoulli trials, each of which has a success probability (or). Then, (or) is the probability that at least of these trials are successful, which is the complement of the Poisson-Binomial cumulative distributed function (CDF) ( [24] , Equation (8)). From Lemma 1 in Appendix A, we conclude that (or) is monotonic non-decreasing in each (or), proving Property 1.

Therefore, using (11) and (12) with and substituted by their mini- mum values for the lower bound and by their maximum values for the upper bound, the minimum and maximum probabilities of detection and false alarm for a -out-of- decision fusion rule at are

(13)

(14)

The OR fusion rule is a special case when. Since, , and, from (13) and (14) with the convention we get

(15)

(16)

Define the Achievable Range of and as

(17)

From (13) and (14), we can see that, , and thus. Therefore, the following properties about, , and hold also for, and.

Property 2. For fixed and, , , and, only depend on.

Follows directly from (13), (14) and (17).

Property 3. For fixed and, and decrease with increasing.

For any, using (13) and (14), we get

,

Property 4..

See Appendix B for proof.

(D) Other system setup assumptions

For network design purposes, we also make the following assumptions:

-Sensors are static after deployed.

-Each sensor employs an omni-directional antenna.

-A partner selection scheme has been devised to generate the adjacency matrix R for cooperation.

-Each sensor is in direct transmission range of its partners.

-The transmit power of each sensor is constant.

-Sensors communicate by broadcasting, and can dynamically switch to different sub-carriers.

-Sensors can transmit and receive at the same time on different sub-carriers.

-Sensors are synchronized ensuring time synchronous operation.

3. Spatial Reuse MAC Protocol Based on Hybrid TDMA/OFDMA

(A) MAC Design Concept

Our MAC protocol is based on TDMA/OFDMA, employing a frame of S time slots and C orthogonal sub-carriers as illustrated in Figure 3. An intuitive approach is to schedule each sensor into a particular time-frequency (T-F) slot [25] . Such a scheme is unrealistic since the number of required slots will increase linearly with the number of sensors. This problem can be solved by allowing a transmitter to share a slot with other far enough ones. The MAC protocol in

[26] reduces the number of required slots by dividing sensors into groups which can communicate simultaneously, employing spatial reuse for scheduling. The objective is to divide the N sensors into M separate sets, and assign one T-F slot to the sensors in the same set. The scheduling result is defined as an N-dimen- sional vector, where represents the ID of the T-F slot assigned to.

We assume that the T-F slots have identical frame lengths as well as sub- carrier bandwidths. Thus, we only need to care about the T-F slot sharing relationship between sensors, rather than a sensor’s specific slot ID. For instance, if and the three scheduling schemes and are the same. To avoid such repeti- tions, we introduce the following ordering restriction for the scheduling vector:

(18)

where is the set containing the indices of whose value is, and represents the smallest index. Thus, (18) means that if, the smallest index in is less than the smallest index in. For example, when, we have

So satisfies condition (18).

When and are scheduled into the same slot, a primary conflict occurs when there is a communication link between them, or they have a common cooperating recipient, a situation to be avoided. We build an conflict relation matrix with components

(19)

where and denote the logical conjunction and disjunction, means a sensor cannot have conflict with itself, means there is a communication link between two different sensors, and means and have a common cooperating recipient. Thus, when two different sensors and share the same T-F slot, (19) means that a primary conflict occurs between two different sensors and (i.e.), if there exists a communication link from to (i.e.) or a communication link from to (i.e.) or a common cooperating recipient of and (i.e.).

In other cases, there exists a secondary conflict, which can be permitted if the impact caused by mutual interference is acceptable. Given that is a partner of, i.e., when broadcasts its package, other sensors who share the same T-F slot with become the interference sources. We define a distance matrix, whose element represents the Euclidean distance between and. From (1) and (3), the average received SINR associated with the transmission from to is

(20)

where represents the scheduling scheme, and using (8) the BEP is

(21)

(B) Problem formulation

The distance matrix is determined by the sensors’ location, assumed to be fixed. Sensors should be spatially separated, to properly cover the target area. Analysis of the degradation on spectrum detection performance caused by correlated shadowing, showing that the distance between sensors should be larger than the decorrelation distance, can be found in [9] [13] . However, sensors cannot be deployed too far from each other to avoid a high BEP on each reporting channel and compromise the cooperative spectrum sensing perfor- mance as discussed in last section. Moreover, when the WSN is deployed by a service provider, the sensors may be installed in existing base stations, where the locations cannot be changed.

The adjacency matrix characterizes the cooperating relationship between sensors. If the distance between sensors is sufficiently large to avoid severe correlated shadowing, a sensor always chooses the cooperating partners with the lowest reporting channel BEP first. As we cannot decide the scheduling of T-F slots before is determined, we do not consider the mutual interference between sensors, and only consider the thermal noise when setting up. If all the sensors use the same transmit power and experience identical multipath fading, a sensor always chooses the nearest sensors around as cooperating partners. Moreover, the number of partners of each sensor should be similar, such that the spectrum sensing performance does not vary significantly between different sensors. The matrix can be changed in the network design process, and in Section 4, we will discuss how to set up for a grid network.

Given a certain number of slots M, our spatial reuse MAC protocol aims at providing a partition of the N sensors to avoid any primary conflict, and minimize the degradation caused by the BEPs on communication links between sensors. We focus on maximizing the Achievable Range of the probability of detection or false alarm, , as defined in (17), which characterizes the reporting error effect, not depending on the local sensing quality. The second argument is added because of (17) de- pends on. From (13), (14) and (17), we have

(22)

The OR fusion rule () as well as AND fusion rule () are special cases with same Achievable Range (from Property 4), which can be obtained from (15) and (16)

(23)

The network fusion factor is defined by, where is the fusion threshold at, is the number of partners of, and represents the ceiling operator. Averaging over sensor locations we obtain the Network Achievable Range of probability of detection or false alarm:

(24)

Therefore, with the adjacency matrix and distance matrix of a DetF WSN of N sensors, number of T-F slots fixed at M, and network fusion factor, the MAC protocol design can be formulated as the solution of the combinatorial optimization problem:

(25)

s.t.

(26)

(27)

(28)

where (26) is the scheduling result, (27) is the constraint for primary conflicts, and (28) is the constraint to avoid repetition. If satisfies constraint (27), it is defined as a feasible solution. If it satisfies both (27) and (28), it is called a valid solution. Moreover, we define the cost function as

(29)

which is called the Network Achievable Range Loss of probability of detection or false alarm.

Essentially, such a MAC design is a combinatorial optimization problem, that is usually computationally intractable for practical applications [27] . Many combinatorial optimization problems of scheduling or channel assignment in wireless networks using similar models are too complicated for exact solution. In [28] [29] [30] [31] [32] , efforts have been invested in developing techniques based on heuristic combinatorial optimization for such problems [33] [34] . Common heuristic methods for solving such problems include: Tabu Search, Genetic Algorithms, Simulated Annealing, Ant System, Neural Networks, [33] . Next we consider two approaches: Greedy Algorithm and Simulated Annealing.

(C) Spatial reuse by graph colouring and greedy algorithm

We first form based on the given. Then all the sensors are considered as vertices, and an edge is drawn between and if or. Thus, a simple undirected conflict graph is constructed, and finding a feasible solution can be viewed as assigning M “colours” to the vertices of this conflict graph, such that adjacent vertices have different colours. We choose the DSatur algorithm (a heuristic vertex colouring procedure) [35] to generate an initial solution. To explain this algorithm, we introduce two definitions:

i) The degree is the number of edges incident to a vertex.

ii) The saturation degree is the number of different colours in the neighbors of a vertex.

To start the DSatur algorithm we number the colours sequentially, and assign colour 1 to the vertex with the highest degree. In case of a tie, choose the one with the smallest sensor index. Select the next vertex with the highest saturation degree, and in case of a tie choose the vertex with the highest degree. Next, search the colours in ascending order, and find the first available one which hasn’t been assigned to any neighbour of the current vertex. Assign this colour to the current vertex, and keep checking the remaining uncoloured vertices in such an order until all the vertices are coloured. Let denote the number of colours used in DSatur algorithm. When the problem of determining whether such an M-colouring exists is NP-complete [36] , and thus we only consider the situation when. Finally, we obtain a feasible initial solution by setting to’s colour index. This initialization method is applicable to any network form; nevertheless, if or have certain regular structures, we can find other more efficient deterministic algorithms. An example will be given in Section IV-B.

The initial generated solution may conflict with condition (28). So we perform the realignment procedure, which will be referred to as REALIGN() throughout the rest of this paper, to transform a feasible solution into a valid solution:

a) Initialization:, , and;

b) Find the smallest index satisfying, and assign the value of to;

c) For all the indices satisfying, set to, and then set to 0;

d);

e) Repeat b) - d) until, and then output, which is a valid solution.

Next we present the complete Greedy Algorithm. Let denote the neighbourhood of a valid solution, which is defined as the set of valid solutions obtained from by performing a local change. The rule for neighbourhood generation can be chosen from a variety of existing methods [37] . For a current valid solution, our greedy algorithm changes the value of only one component to get a new solution. If violates the constraint of primary conflicts, we discard it. Otherwise, the realignment procedure is performed, and the outcome becomes one element of. Starting from the initial solution, the greedy algorithm selects from resulting in the minimum value of the cost function of (29). If, then is accepted as the new valid solution for the next state, and this procedure is repeated. If, the algorithm is terminated, and is output as the final result. The complete procedure is summarized in Figure 4.

(D) Spatial reuse by adaptive simulated annealing

Despite its easy implementation and low complexity, the greedy algorithm cannot guarantee a globally optimal solution. Hence we propose an alternative approach using Adaptive Simulated Annealing (ASA) [38] . Simulated Annealing is a probabilistic method whose random search process mimics the physical annealing process [39] . It originates from the principles of thermodynamics associated with making a metal “freeze” into a crystalline structure at a mini- mum energy configuration, when cooled slowly from a state of high temperature. If its cooling process is well controlled, the algorithm can converge to a global optimum. The ASA algorithm permits an exponentially decreasing annealing schedule which greatly accelerates the optimization process compared with some traditional simulated annealing algorithms [40] . Moreover, the re-annealing procedure is introduced in ASA to adapt to changing sensitivities in the multi- dimensional parameter-space. More details on ASA are provided in Appendix C.

In our work, the components of take integer values, and interrelate with each other subject to the constraints induced by primary conflicts (27). Thus, the generating procedure in Appendix C needs to be modified. At the start of the state, we form a random permutation of the indices, denoted by a vector. Then at the ath step, we pick, and obtain the ith component of the temporary candidate solution, , where is a sample of a random variable with the PDF of (48). The range of the ith parameter is, and if, another sample of is applied until. Next, we find the ith component of the candidate solution:

(30)

(31)

where is the set of sensors scheduled

into the mth slot before, and thus (31) guarantees no primary conflict be- tween and any sensors scheduled before it. We generate the components of according to the random order indicated by, and finally obtain a feasible candidate solution. If there is no valid value for at any step, the whole state will be started over with a new permutation vector. At the end of the generating procedure, we conduct the realignment procedure on to obtain a valid solution.

In our work the acceptance and annealing procedures are the same as those described in Appendix C. However, we bypass the reannealing stage for temperature parameters, and only conduct this procedure on cost temperatures. This stage is optional, and since the components of are integers, there is no effective numerical method to calculate the derivatives in (52). For a large numbers of parameters (N) skipping this stage helps to significantly increase efficiency. We use the same initialization method of the greedy algorithm to get the initial value of. The ASA algorithm terminates when the predefined maximum number of generated states () or maximum number of accepted states () is reached. The ASA algorithm is summarized in Figure 5.

4. Performance Results for a Grid Network

(A) Scenario setup

The sensors are assumed to be deployed on the grid of a target square region, with Euclidean distance between two nearest sensors fixed to. We establish a Cartesian coordinate plane such that is in the centre of the square, and

the coordinates of the sensors are,

where, , and is selected such that is an integer.

As to the partner selection scheme, the priority is given to the nearest sensors. We consider four adjacency matrix structures, and use the following cooperation levels to define them:

i) CL0: No cooperation between sensors, and thus is an identity matrix.

ii) CL2: A sensor selects itself and two other nearest sensors as its partners. If there are several sensors with the same distance, select in the ascending order of the sensor IDs.

iii) CL4: A sensor selects all the sensors within as its partners (including itself).

iv) CL8: A sensor selects all the sensors within as its partners (including itself).

We choose the COST-Walfish-Ikegami (COST-WI) model as the empirical path-loss model in the WSN, with parameters set for the Urban Macro scenario [41] . This model can be viewed as a simplified path-loss model in (1), with, , and. In addition, the average received SNR of the primary signal, , is assumed to be identical at each sensor, which is a reasonable assumption when generating numerical or simulation results as in [8] [42] . Furthermore, each sensor employs the same transmit power, and energy detection threshold. The scenario setup parameters are summarized in Table 1.

The C-language implementation of the ASA algorithm is based on the source code provided by A. L. Ingber, which is available at . We made some modifications as described in Section 3(D), where we tuned the ASA parameters and options according to the specifics of our optimization problem, which are summarized in Table 2.

(B) Features of the grid network

We first build an undirected grid graph by considering all the sensors as

vertices, with an edge between any two sensors whose Euclidean distance is. The grid distance between and is defined as the number of edges in a shortest path connecting them in the grid graph.

-For CL2 and CL4, the grid distance between any partner-receiver pair is 1. If no two sensors within grid distance 2 share the same slot, no primary conflict exists in the WSN.

-For CL8, the longest grid distance between any partner-receiver pair is 2. If no two sensors within grid distance 4 share the same slot, no primary conflict exists in the WSN.

If the T-F slots are viewed as “colours”, then for CL2 and CL4, a 2-distance colouring of the grid graph is a feasible solution, and for CL8, a 4-distance colouring is a feasible solution. The k-distance colouring is defined as a vertex colouring such that no two vertices lying at the grid distance less than or equal to k are assigned the same colour. The minimum number of colours necessary for the k-distance colouring of a grid graph, denoted by, is given by [43] :

(32)

In summary, for the grid network with the partner selection scheme described above, if the longest grid distance between any partner--receiver pair is, then a 2k-distance colouring of the grid graph is a feasible solution (no primary conflict). The minimum number of colours (T-F slots) needed to complete the 2k-distance colouring is. Thus, if, we can guarantee that there is a scheduling solution without primary conflict. Then, we can set the minimum value of M (number of T-F slots) as, which is 5 for CL2 and CL4, and 13 for CL8.

In addition, for the grid network, we introduce an alternative method to generate the initial valid solution, which is based on a deterministic approach of k-distance colouring:

a) Find, where is calculated by (32).

b) Obtain an initial solution by setting its components as follows:

(33)

where, , and “” represents the modulo operator.

c) Realignment procedure: p¬REALIGN(p)

The scheduling of (33) is equivalent to a -distance colouring of the grid graph [43] . In addition, because we have set. Thus, the solution of step b) ensures that there is no primary conflict. The initialization by k-distance colouring is more concise and efficient than that via DSatur algorithm for a grid network.

(C) Verification of the algorithms

This example shows how the greedy algorithm may be trapped in local minima, and how the ASA algorithm can reach the global optimum. We consider a small network with 9 sensors as illustrated in Section 4(A), and set. The adjacency matrix is constructed as

The number of partners of each sensor is, and we set the fusion factor to be 0.1 or 0.5. Then, the fusion threshold of each sensor is. When, the cost function (29) is the same as that of, and thus we do not need to use. Through exhaustive search, we find that there are 111 valid solutions out of 1935123 feasible solutions. When, the global minimum is:, with or. When, the global minimum is:, with. The initial solution is obtained by k-distance colouring as in Section 4(B), which is. The greedy algorithm generates solutions to obtain the neighbourhood of a current solution, and accept the best solution from it. If the current solution is smaller than any of the neighbour solutions, the greedy algorithm terminates and outputs the current solution.

-When, the initial solution is, with . Then the greedy algorithm generates the neighbour- hood of this initial solution, and finds 8 new valid solutions. However, the initial cost value 0.02491 is smaller than any of the 8 neighbours, and the greedy algorithm gets stuck at this local minimum ().

-When, the initial solution is, with . This time the greedy algorithm gets stuck in the local minimum, with after 180 solu- tions are generated.

Next, we apply a relatively slow ASA algorithm with, , and QUENCHing options turned off. Moreover, we adjust the generating procedure to change only one random component at each state, which results in the same neighbourhood structure as the greedy algorithm. At each state, the ASA algorithm generates a candidate solution, whose cost value is represented by the solid line in Figure 6(a) and Figure 6(b), and the dark dash line shows the acceptance procedure illustrated in Appendix C. If the generated cost value is larger than the current one, the ASA algorithm allows to accept the worse cost value at certain points. This helps the ASA algorithm to escape from a local minimum. At the end, when and, the ASA algorithm reaches the following global minimum when and, which are the same as those obtained from exhaustive search:

-When, , with.

-When, , with.

We also apply the normal generating procedure illustrated in Section 3(C) with realignment and the ASA parameters summarized in Table 2. The cost values generated and accepted at each state are shown in Figure 7, in the same form as Figure 6. If, it arrives at the global minimum 0.01830289 when, and if, it arrives at the global minimum when, showing that the ASA algorithm is efficient when its parame- ters are well-tuned.

(D) ROC curves for different configurations

We analyse the spectrum sensing performance of the grid WSN through ROC curves, which display vs. The quantities and represent the network probabilities of detection and false alarm averaged over sensor locations,

, and, where and are

defined in (11) and (12). We use the fusion factor to set the fusion thres- hold of each sensor, as, where is the number of partners of. For the partner selection schemes introduced in Section 4(A), we have. Since there is no communication link when a sensor employs its own sensing result,. Then when using the OR fusion rule, according to (16), the maximum value of or is

(34)

Thus, the maximum value of or when using OR rule is .

In each case, we change one network parameter while fixing others, and use both greedy and ASA algorithms to realize spatial reuse of T-F slots. The k- distance colouring scheme is used for initialization methods with both algorithms. After obtaining the output of the protocol, , we calculate the BEP of every communication link based on (21). Then we can calculate and using (6), (7), (9), (10), (11), and (12).

Different numbers of T-F slots

In Figure 8 we present the ROC curves for different values of M with, , , CL8, and (OR fusion rule). As M in- creases, the sensors sharing one slot can be more spatially separated, resulting in lower BEPs on communication links. In turn, it helps increase with the same, and lowers, which can be seen by comparing the curves of the same line style. Comparing the curves of different line styles with the same M, we see that the difference between the ASA and greedy algorithms becomes more significant as decreases from 1 to of the greedy algorithm, where it is ouperformed by the ASA algorithm. As M increases, the difference between the ROC curves of the two algorithms becomes smaller. When, no spatial reuse is needed, providing an upper bound to spectrum

sensing performance, that serves as a benchmark. At, the ASA and the greedy algorithms with provide a value for that are nearly the same as the benchmark. At, the difference between of the ASA and the greedy algorithms with and the benchmark can also be ignored. We can save at least 76.6% and 37.5% of T-F slots if the requirements of are 0.1 and 0.01 respectively.

Different cooperation levels

We evaluate the performance with different cooperation levels (defined in Section 4(A) in Figure 9, where, , , , and (OR rule). No T-F slot is needed for CL0, acting as a benchmark for other cooperation levels. Comparing the curves of different line styles at the same cooperation level, we see that the difference between the ASA and greedy algorithms is mainly manifested in the range between their lower bounds. For example, using CL8, the difference between the curves when is nearly negligible, and when, the ASA algorithm outperforms the greedy algorithm. Moreover, when the cooperation level increases, the difference between the values of increases.

Next, we focus on the curves of one algorithm at different cooperation levels. When the cooperation level increases, the existing partners for the lower cooperation level remain in the set, while new partners are added. Because the number of slots M is fixed, the interference caused by spatial reuse in the network remains nearly unchanged, and the BEP from an existing partner for the lower cooperation level varies very little. Then from (15), we see that increases with the cooperation level, which is confirmed by the curves in

Figure 9. When is higher than, cooperation between sensors helps increase compared with CL0. However, the difference between CL2, CL4 and CL8 in the high range () is very small. For the case shown in Figure 9, we can divide the axis into 4 intervals with boundaries close to at each cooperation level, and find the best choice of cooperation levels in each interval. Taking the ASA curves as an example, when, CL2, CL4 and CL8 perform nearly the same. We see that CL4 is the best for, CL2 is the best for, and if the system requires, then CL0 is the only choice.

Different network sizes

Three networks sizes, are analyzed in Figure 10 and Figure 11, with, CL4, , and (OR rule). In Figure 10, we fix, and in Figure 11 we fix to 0.4. We see that when, the difference between the two algorithms is very small. In relatively low range, for the same value of, the ASA algorithm results in higher compared to the greedy algorithm. For or, the ASA algorithm outperforms the greedy algorithm when, and for, the difference is identifiable when.

For CL4, a sensor located at the corner has 3 partners, the one on the edge has 4 partners, while any other sensor has 5 partners. When N is increased, the proportion of sensors on the edge, as well as that at the corner, decreases, resulting in increasing average number of partners of each sensor. When M is fixed, larger N means an increasing average numbers of

sensors sharing the same slot. Thus, the network interference level increases, resulting in higher average BEP of communication links. As shown in Figure 10, for relatively high the gain brought by more partners is counteracted by the impact of worse reporting channels. In addition, according to (15), more partners and higher BEPs of reporting channels lead to a higher. When the ratio is kept constant, Figure 11 shows that the performance improves with increasing N. This is because in a larger network, although the average number of sensors sharing one T-F slot remains almost unchanged, the average distance between them increases, which leads to a lower network interference level and lower average reporting BEP.

Different decision fusion rules

The ROC curves for fusion factor values are presented in Figure 12, where, , , and CL4 is used. For CL4, sensors at different locations in the network may have different numbers of partners. For the 4 sensors in the corner, for the sensors on the edge (but not in the corner), and the other sensors have. The decision fusion threshold at

each sensor is, and we have

(35)

Thus, according to Property 4, and (or and) result in the same Achievable Range of each sensor in this scenario. Then based on (24) and (29), and have the same cost function, and

so do and. Thus, and have the same sche- duling result, and also and have the same scheduling result.

In Figure 12, we see that the separation between the ROC curves of the two algorithms becomes smaller as increases, and we can hardly differentiate the ROC curves when. Comparing the curves for the same algorithm, we see that and decrease with increasing, following Property 3. For design purposes we have to choose according to the specific or requirements and the ROC curves. Consider the ROC curves for the ASA algorithm for example, when the required is in the range, the ROC curves of are nearly the same, and result in higher than. If the system requirement is, can not achieve this and is better than. In this scenario, for we can always choose, and is the worst choice.

5. Conclusions

In this paper, we analysed cooperative spectrum sensing performance using the k-out-of-n decision fusion rule with imperfect reporting channels, and derived the upper and lower bounds of probabilities of detection and false alarm. Then, we introduced a DetF distributed WSN for cooperative spectrum sensing, and proposed a spatial reuse MAC protocol based on TDMA/OFDMA. Two design approaches for the MAC protocol were considered: greedy and ASA algorithms. Finally, for a grid WSN, we discussed how to construct the adjacency matrix characterizing the cooperating relations between sensors. We also explain how to determine the minimum number of T-F slots, and get an initial valid solution via a k-distance colouring method.

Numerical results for a grid network in Section 4 show how the spectrum sensing performance is influenced by system parameters, and also present a comparison of the ASA and greedy algorithms. The ROC curves in Figures 8-11 show that using the OR decision fusion rule, the difference between the curves of the two algorithms is very small in relatively high range, and the advantage of the ASA algorithm can be seen when is around and smaller than the lower bound of the greedy algorithm. The ROC curves in Figure 12 show that the separation between the ROC curves of the ASA and greedy algorithms decreases as the decision fusion factor increases, and when the two curves become virtually the same.

When comparing the ROC curves of one algorithm with different network settings, we can see the influence of system parameters. From Figure 8 we see that our spatial reuse MAC protocol can save T-F slots without significant impact on the sensing performance at certain. We also see that the lower bounds and decrease when the number of T-F slots is increased. From Figure 9 we see that cooperation between sensors helps improve the spectrum sensing performance when is higher than the lower bound. However, the lower bound increases with the number of partners of each sensor. For example, the difference between the ROC curves of CL4 and CL8 is nearly negligible when, and is not achievable by CL8. Thus, we should not aim at increasing the number of partners of each sensor as much as possible. From Figure 10 we see that if the number of T-F slots is fixed, a larger network size leads to an increased lower bound, and Figure 11 shows that if the ratio is fixed, a larger network size gives better sensing performance. In Figure 12, it is not a clear cut which fusion factor is the best in general. We can use the ROC curves to decide the value of according to the specific required and. For instance, if the system required is 0.001 then is the best choice. In addition, if the number of T-F slots cannot be changed for a certain network size, adjusting the cooperation level or decision fusion threshold is necessary to improve the sensing performance subject to and requirements.

Cite this paper

Shao, X. and Leib, H. (2017) Media Access with Spatial Reuse for Cooperative Spectrum Sensing. Wireless Sensor Network, 9, 205-237. https://doi.org/10.4236/wsn.2017.97012

References

Appendix A

Consider N independent Bernoulli trials, where for the mth trial the probability of success is and. The probability of at least k successes in these N trials is the complement of Poisson- Binomial CDF ( [24] , Equation (11)),

(36)

In addition, the Poisson-Binomial probability mass function (PMF) is ( [24] , Equation (5)),

(37)

Lemma 1. For a certain series of Bernoulli trials, and fixed value of, the complement of Poisson-Binomial CDF, of (36) is monotonic non- decreasing in each.

Proof: We obtain the partial derivative of in (36) with respect to,

(38)

Then we consider a certain series of N Bernoulli trials where , and use to denote the Poisson-Binomial PMF in this case. Based on (37) we have

(39)

When, from (39) we have

(40)

Based on (39) and (40), we get

(41)

The right-hand side of (41) is exactly the same as that of (38), and hence

(42)

When, the lth trial is successful with probability 1, and hence. Thus,

Appendix B

Proof of Property 4

Suppose that there are independent Bernoulli trials, and the success probability of each trial is. Then in (13) is the probability that at least trials are successful:

(43)

and in (14) can be viewed as the probability that at least of these trials are failed,

(44)

where (44) is also given in ( [44] , pp. 251-253). Hence from (43) and (44)

(45)

Then, based on (45) and the definition of in (17), we have

(46)

and

(47)

Appendix C

Details of ASA

The ASA algorithm consists of three major stages: generating, acceptance, and annealing [38] . In a N-dimensional parameter space with the ith parameter having the range, assuming that is the tth saved point, the gene- rating procedure aims to obtain a new candidate point for the state, whose components are where is a sample of a random variable with PDF

(48)

is the parameter temperature, and is the parameter annealing index. If, a new is generated with another sample of, until.

The acceptance procedure determines whether the candidate point is accepted as the new saved point for the next state. When the cost function is denoted by, and is a sample of a uniformly distributed random variable, the acceptance procedure is

(49)

where is the cost temperature, and is called cost annealing index.

The annealing procedure for the parameter temperature is

(50)

The initial parameter temperature is usually set to 1 by users. The parameter annealing index is initially set to 0, and increased by 1 every time a new candidate point is generated. The parameter quenching factor for the ith parameter is, which is set to 1 for normal ASA. When, the “quench- ing” option is turned on to speed up the search in a large parameter space [38] . The parameter temperature scale is

where and are called the temperature ratio scale and temperature anneal scale respectively.

The annealing procedure for the cost temperature is

(51)

The ASA algorithm first generates states and calculates the cost func- tion of each state, where is named number of cost samples. Then, the initial cost temperature takes the average of the absolute values of the sampled cost functions. The cost annealing index is initially set to 0 and then increased by 1 every time a new candidate point is accepted. The cost quenching factor is similar to. The cost temperature scale is set as, where is an ASA parameter named cost parameter scale ratio.

An optional reannealing procedure will periodically rescale and. This procedure takes place every (generated frequency modu- lus) candidate points generated, or every (acceptance frequency modulus) candidate points accepted. Assuming that this reannealing procedure is conducted after states are generated, is reannealed as

(52)

where is the best cost value found as of the current state. If then is reset as. Moreover, is re- scaled as

(53)

When gets its new value, the current cost temperature is reset as

(54)

Thus, according to (51), after reannealing is

Submit or recommend next manuscript to SCIRP and we will provide best service for you:

Accepting pre-submission inquiries through Email, Facebook, LinkedIn, Twitter, etc.

A wide selection of journals (inclusive of 9 subjects, more than 200 journals)

Providing 24-hour high-quality service

User-friendly online submission system

Fair and swift peer-review system

Efficient typesetting and proofreading procedure

Display of the result of downloads and visits, as well as the number of cited articles

Maximum dissemination of your research work

Submit your manuscript at: http://papersubmission.scirp.org/

Or contact wsn@scirp.org