extfieldsofstudy:
Computer Science
Mathematics

text:
Performance Analysis of Arbitrarily-Shaped Underlay Cognitive Networks: Effects of Secondary User Activity Protocols

This paper analyzes the performance of the primary and secondary users (SUs) in an arbitrarily-shaped underlay cognitive network. In order to meet the interference threshold requirement for a primary receiver (PU-Rx) at an arbitrary location, we consider different SU activity protocols which limit the number of active SUs. We propose a framework, based on the moment generating function (MGF) of the interference due to a random SU, to analytically compute the outage probability in the primary network, as well as the average number of active SUs in the secondary network. We also propose a cooperation-based SU activity protocol in the underlay cognitive network which includes the existing threshold-based protocol as a special case. We study the average number of active SUs for the different SU activity protocols, subject to a given outage probability constraint at the PU and we employ it as an analytical approach to compare the effect of different SU activity protocols on the performance of the primary and secondary networks.

We show that many existing closed-form results in the literature for the interference analysis in the primary network can be obtained as special cases in our framework. In addition, we derive a closedform result for the average number of active SUs. To the best of our knowledge, this is the first time that such a result has been obtained in the literature for the case of underlay cognitive network. • We study the average number of active SUs for the different SU activity protocols, subject to a given outage probability constraint at the PU. We show that the guard zone protocol supports the highest number of active SUs, followed by the proposed cooperation-based protocol and then the thresholdbased protocol. The advantage of the cooperation-based protocol over the guard zone protocol is that it relies on the SUs only knowing the instantaneous channel strengths to the PUs.
The remainder of the paper is organized as follows. Section II presents the detailed system model and assumptions and describes the three different SU activity protocols, including the proposed cooperationbased protocol. The proposed mathematical framework is presented in Section III. The analysis for the interference and the average number of active SUs is presented in Section IV and Section V, respectively.
Numerical and simulation results to study the aggregate interference, outage probability and average number of active SUs are discussed in Section VI. Finally, conclusions are presented in Section VII.
The following notation is used in the paper. The probability distribution function (PDF) and the cumula- is the generalized incomplete gamma function and 2 F 1 [·, ·; ·; ·] is the Gaussian or ordinary hypergeometric function [30].

II. SYSTEM MODEL
We consider an underlay cognitive network with a PU link, comprising of a PU transmitter (PU-Tx) and a PU receiver (PU-Rx) separated by a distance r 0 , and M SUs. The network region A is an arbitrarilyshaped finite region, where A ⊂ R 2 and R 2 denotes the two-dimensional Euclidean space. We do not place any restriction on the location of the PU-Tx and PU-Rx and they can be located anywhere inside the network region A. A primary exclusion zone B, with radius , is formed around the PU-Rx and no active user is allowed to enter this region [31]. The SU locations are modeled according to a uniform Binomial Point Process, i.e., the M SUs are independently and uniformly distributed (i.u.d.) at random inside the region A , where A = A \ B.
The SUs decide whether to transmit or not depending on the adopted SU activity protocol (discussed later in this section). We assume that all the nodes operate in the frequency division duplex mode. Similar to [15], we assume that in order to know the channel strength to PU-Rx each SU receives a signal transmitted by PU-Rx via a sensing channel. We assume that this sensing channel (from PU-Rx to SU) and the SU transmitting (i.e., interfering) channel (from SU to PU-Rx) are well separated in the frequency band so that these two channels can be regarded as fully uncorrelated.
Let the RV R i (i = 1, 2, . . . , M ) denote the random distance between the i-th SU and the PU-Rx with probability distribution function f R i (r i ). We denote the transmit power of the PU-Tx as P T 0 , the transmit power of each SU as P T i and the transmit power of PU-Rx as P T S . We assume that all users have a single antenna and the wireless communication channel is modeled as a path-loss and fading channel. Let G i represent the instantaneous power gain due to fading on the SU transmitting channel from i-th SU to the PU-Rx with fading distribution function f G i (g i ) and H i represent the instantaneous fading power gain on the sensing channel with the distribution function f H i (h i ).
For the above setup, the interference at the PU-Rx generated from the i-th SU is given by where α is the path-loss exponent which is typically in the range 2 ≤ α ≤ 6 [32]. The indicator function (a) Guard zone protocol with radius r f and primary exclusion zone radius .
r 0 (c) Cooperation-based protocol with activation threshold γ and cooperation range rc . is given by where the "condition" depends on the different SU activity protocols and the explicit expressions for each protocol are given in (4), (5) and (6), respectively. In addition, although the unbounded path-loss model is used in (1), the singularity at R i = 0 and the amplification of the transmitted signal are avoided because of the primary exclusion zone around the PU-Rx, i.e., the random distance R i is always greater than ( ≥ 1) [6].
The aggregate interference at PU-Rx is given by In the following subsections, we present the definition of each SU activity protocol.

A. Guard Zone Protocol
The guard zone protocol was employed in [12], [13]. In this protocol, the SUs are permitted to enter the guard zone region but once a SU intrudes into it, it is prohibited from transmitting. This is illustrated in Fig. 1(a), where there is a guard zone region around the PU-Rx with radius r f . Consequently, the two SUs that are inside this region are inactive and do not generate any interference to the PU-Rx. The aggregate interference under the guard zone protocol can be written as

B. Threshold-based Protocol
The threshold-based protocol was proposed in [15]. In this protocol, each SU receives the instantaneous signal power transmitted by the PU-Rx on the sensing channel. If the received instantaneous signal power at the i-th SU is greater than the activation threshold γ, i.e., P T S H i R −α i > γ, it becomes silent and does not interfere with the PU-Rx. Otherwise, it is permitted to transmit, as illustrated in Fig. 1(b). Hence, for the threshold-based protocol, the aggregate interference can be written as

C. Cooperation-based Protocol
This is the new protocol proposed in this paper and is illustrated in Fig. 1(c). The basic idea of this protocol is inspired from the cooperative spectrum sensing in interweave cognitive networks, where cooperation among nodes helps to improve the detection of licensed spectrum occupancy [6], [10]. 1 In the proposed cooperation-based protocol for underlay cognitive networks, each SU receives the instantaneous signal power transmitted by the PU-Rx on the sensing channel and forms an initial decision on activation. Then this initial decision is broadcast to other SUs. For analytical convenience, we assume that, for each SU, it can only correctly receive the initial decisions from other SUs within a certain range, which is known as its cooperation range r c . Finally, in order to decide whether it is active or not, each SU applies the AND rule on the received initial decisions from other cooperating SUs and its own initial decision. Consequently, for a considered SU, it is permitted to be active as long as its preliminary decision is to be active, and the initial decision of all SUs which fall into this SU's cooperation range is also to be active. Mathematically, the aggregate interference generated at the PU-Rx is where Π d denotes the set of SUs whose received instantaneous signal power on the sensing channel is greater than the activation threshold γ, D i (r c ) represents the disk cooperation region centered at the i-th SU and ∅ denotes the null set. Note that when r c = 0, the cooperation-based protocol is the same as the threshold-based protocol. Thus, the proposed cooperation-based protocol includes the threshold-based protocol as a special case.
Remark 1: Both the cooperation-based and threshold-based protocols require the SU to receive the instantaneous signal power transmitted by the PU-Rx on the sensing channel. As such, they are much more applicable in practice. However, the guard zone protocol requires the SU to know the instantaneous signal power on the sensing channel over a relatively long period of time and then average it to determine its distance to the PU-Rx, before deciding whether to transmit or not. 2 As such, this protocol is not suitable for the scenarios where the SUs need to transmit without too much delay.

III. MATHEMATICAL FRAMEWORK
In this section, we present the proposed mathematical framework to characterize the interference and outage in underlay cognitive networks with different SU activity protocols. The aggregate interference from the secondary network in (3) is a stochastic process that strongly relies on the random location of the SUs inside the arbitrarily-shaped finite cognitive network region and the random fading channel gains. Since there is no available general expression for the PDF of the aggregate interference [35], [36], we adopt the moment generating function approach to analyze the interference and outage in this paper.
Previous work [14], [15] has also adopted the MGF approach. However, their focus is on analysing the statistics of the aggregate interference in the primary network only and the results are limited to specific, e.g., annulus-shaped regions. We consider arbitrarily-shaped cognitive network regions and analyze the performance in both the primary network (i.e., the aggregate interference in Section IV) and the secondary network (i.e., the average number of active SUs in Section V).

A. Assumptions
In this paper, we consider that the nodes are independently and uniformly distributed inside the network region A , which results in the distribution function of R i being the same for all i. Moreover, the fading gain on all communication channels is independently and identically distributed (i.i.d.) Nakagami-m fading.
This type of fading is widely considered in the wireless communications literature [32]. The transmit power for different SUs are assumed to be the same. Consequently, the distribution of interference from i-th SU becomes identical and we can drop the index i in the P T i , For Nakagami-m fading, the distribution of the power gain on the SU transmitting channel and the sensing channel can be modeled by a Gamma distribution as [32] f G (g) = g mg−1 m mg g where m g and m h represent the fading parameters, which control the severity of the fading. Note that m g = m h = 1 corresponds to Rayleigh fading channels. In addition, the n-th moment of the fading power gain on the SU transmitting channel, which is needed in the analysis in Section IV, is available in closed-form as [37]

B. Distance Distributions
The proposed formulation relies on the knowledge of the distance distribution f R (r), i.e., the PDF of the distance of a random SU from the PU-Rx. For a disk region, f R (r) is well known [7], [10], [13]- [15], [27]. For an L-sided arbitrarily-shaped convex polygon, f R (r) can be a complicated piece-wise function with at most 2L piece-wise terms [38]. The number of piece-wise terms depends on the number of unique distances between the location of the reference node and all the sides and vertices, respectively, of the polygon region. Recently, [29] proposed an algorithm to determine f R (r) for the case of a random node located anywhere inside an arbitrarily-shaped convex polygon. This algorithm is used in this work to is determined using the algorithm in [29], the expectation which is needed in the analysis in Section IV, can be easily calculated in closed-form.

C. Moment Generating Function
In general, the moment generating function of the aggregate interference is defined as [32] M where E Iagg {·} denotes the expectation with respect to the RV I agg . Assuming that the interference from each SU is independent and identical, the moment generating function of the aggregate interference in (10) can be rewritten as [32] M where I denotes the interference generated by a random SU and M I (s) = E I {exp(−sI)} corresponds to the MGF of I.

D. n-th Cumulant
The n-th cumulant of the aggregate interference can be written in terms of the MGF of the aggregate interference as [32] κ where the last step comes from the recursive moment-cumulant relationship [27], and κ I (n) and µ I (n) represent the n-th cumulant and n-th moment of the interference from a random SU respectively. Note that µ I (n) can also be directly related to M I (s) by [32] µ

E. Outage Probability
The outage probability is an important metric to evaluate the impact of SU activity protocols on the performance of the primary users over fading channels. It is given by where β is the SINR threshold and N is the additive white Gaussian noise power.
In this paper, we are interested in the spatially averaged outage probability which is spatially averaged over both the possible location of the SUs and the fading channels. When the fading on the desired link (from PU-Tx to PU-Rx) follows the general distribution defined in [39, (9)] (an important special case of which is Nakagami-m fading with integer m value), we can employ the reference link power gain-based (RLPG-based) framework proposed in [29] to evaluate the spatially averaged outage probability. The basic principle of this approach is to first condition on the interference and express the outage probability in terms of the CDF of the reference link's fading power gain. The conditioning on the interference is then removed first by removing the conditioning on the fading power gains of the interferers and then removing the conditioning on the locations of the interferers. For Nakagami-m fading channels, the spatially averaged outage probability is given by [29] where ρ 0 = indicates the average signal-to-noise ratio (SNR) and m 0 denotes the fading parameter on the desired link.
Using the frequency differentiation property of Laplace transform, the Laplace transform of the term . Then the expectation term in (15) can be expressed in terms of the MGF of the interference due to a random SU as Examining (11), (12) and (15), we can see that the proposed mathematical formulation depends on the MGF of the interference due to a random SU M I (s). This is determined for the different SU activity protocols in the next section.

IV. INTERFERENCE ANALYSIS
In this section, we derive the general expressions characterizing the MGF of the interference from a random SU for the different SU activity protocols.

A. Guard Zone Protocol
For this protocol, the SUs within the guard zone region do not transmit. The main result is summarized in Theorem 1.
Theorem 1: For the guard zone protocol, the MGF of the interference at an arbitrarily located PU-Rx due to an independently and uniformly distributed SU inside an arbitrarily-shaped finite region is where F R (·) represents the cumulative distribution function of the distance of a random SU from the PU-Rx, which can be determined by the algorithm in [29].
Corollary 1: For the guard zone protocol, the n-th moment of the interference at an arbitrarily located PU-Rx due to an independently and uniformly distributed SU inside an arbitrarily-shaped finite region is Proof of Theorem 1 and Corollary 1: See Appendix A-A.
Remark 2: (17) and (18) can also be used to obtain the results for the full activity protocol in which no activity constraint is imposed on SUs and all the SUs are in active status. In the full activity protocol, a SU located within the maximum range of and r max generates interference to the PU-Rx. In the guard zone protocol, a SU located within the smaller range of r f and r max generates interference to the PU-Rx.
Thus, when the guard zone range r f is set to equal to , the guard zone protocol reduces to the full activity protocol. Therefore, the MGF and n-th cumulant results for the full activity protocol are the same as (17) and (18) with r f replaced by .
Special Case of a Regular L-sided Polygon: Consider the special case that the PU-Rx is located at the center of a regular L-sided polygon which is inscribed in a circle of radius W . In this case, the distance distribution function is given by [38] f where |A | = 1 2 LW 2 sin 2π L − π 2 denotes the area of the underlay secondary network region, θ = π(L−2) L is the interior angle between two adjacent sides of the polygon and W p = W sin θ 2 is the perpendicular distance from the center of the polygon to any side. Substituting (19) and (7) into (17) and (18), yields the following results where Φ (r) = and r f is assumed to be less than W p .
Note that while (20) does not have a closed-form result due to the integration involving the arccos(·) term, it can be easily computed numerically.
Remark 3: When L → ∞, W p → W and the regular L-sided polygon approaches a disk region. The disk region or annulus-shaped region with centered PU-Rx and full activity protocol is the most popular scenario and has been widely analyzed in previous works [13]- [15], [27]. Under the Nakagami-m fading assumption, the MGF calculated from (20) by setting r f = (i.e., full activity protocol) and W p = W (i.e., the integration term in (20) reduces to zero) is identical to the result in [27, eq. (6)]. In addition, the n-th cumulant calculated from (21) (replacing r f by and Φ (W p ) = Φ (W )) and (12) is the same as the result from [27].

B. Threshold-based Protocol
In this protocol, the activity of each SU depends on the instantaneous signal power received on the sensing channel. The main result is summarized in Theorem 2.
Theorem 2: For the threshold-based protocol, assuming the sensing channel is fully uncorrelated with the SU transmitting channel, the MGF of the interference at an arbitrarily located PU-Rx due to an independently and uniformly distributed SU inside an arbitrarily-shaped finite region is where F H (·) denotes the CDF of the fading power gain on sensing channel.

Corollary 2:
For the threshold-based protocol, the n-th moment of the interference at an arbitrarily located PU-Rx due to an independently and uniformly distributed SU inside an arbitrarily-shaped finite region is Proof of Theorem 2 and Corollary 2: See Appendix A-B.
Special Case of regular L-sided Polygon: Substituting the PDFs f R (r) in (19) and f G (g) in (7) into (22) and (23), we can obtain the MGF and the n-th moment for this special case. For simplicity, we only show the n-th moment result, which is given by where Γ[·, ·, ·] is the generalized incomplete gamma function [30].

Remark 4:
For the disk region, (24) with L = ∞ (i.e., ignoring the integration part in (24)) is equivalent to the result in [15]. However, the method of calculating the n-th cumulant in [15] is only applicable for the special case that PU-Rx is located at the center of the disk region.

C. Cooperation-based Protocol
For the cooperation-based protocol, the activity of each SU is determined by itself as well as other SUs within its cooperative range. Thus, the interference due to each SU is not independent and (11) is not strictly valid. The analysis in the presence of correlated interference is an important open research problem. In this paper, we still use (11) to derive approximate analytical results for the cooperation-based protocol. We show that these results are accurate under certain conditions, which will be discussed in detail in Section VI. The main result is summarized in Theorem 3 below.
Theorem 3: For the cooperation-based protocol, the MGF of the interference at an arbitrarily located PU-Rx due to an independently and uniformly distributed SU inside an arbitrarily-shaped finite region is approximated by Corollary 3: For the cooperation-based protocol, the n-th moment of the interference at an arbitrarily located PU-Rx due to an independently and uniformly distributed SU inside an arbitrarily-shaped finite region is approximated by

Proof of Theorem 3 and Corollary 3: See Appendix A-C.
Remark 5: To the best of our knowledge, it is not possible to express (25) and (26) in closed-form, even for the special cases of PU-Rx located at the center of a polygon or disk region. This is because (25) and (26) contain one term, related to the RV R, which is raised to the power of M − 1 (M ≥ 2) inside the expectation. Nevertheless, (25) and (26) can easily be evaluated numerically. Also, if r c = 0, the term raised to the power of M − 1 becomes one and (25) and (26) reduce to (22) and (23).

V. AVERAGE NUMBER OF ACTIVE SECONDARY USERS
The aggregate interference at the PU-Rx and the resulting outage probability are metrics to evaluate the performance of the primary network, which was the common focus of most prior studies on cognitive networks, e.g., [12]- [15]. Ideally, the performance of the secondary network should also be evaluated.
Furthermore, this should be done subject to a quality-of-service (QoS) constraint that the SINR of each active SU is maintained higher than a desired level. One way to do this analytically is to determine the SU throughput which can be defined as the expected spatial density of successful SU transmission and depends on (i) the number of active SUs over a certain region and (ii) whether each active SU is in outage or not, i.e., whether its SINR is above a certain threshold.
The exact SINR distribution of an active SU (and consequently the SU throughput) in an arbitrarilyshaped underlay cognitive network is difficult to obtain because of two main reasons. Firstly, for an arbitrarily-shaped region with a fixed number of nodes, the Binomial Point Process is non-stationary and an active SU's SINR is, therefore, location-dependent. Thus, the SINR of an active SU at a certain location (say origin) does not reflect the SINR of other active SUs. The difficulty in analytically averaging the active SU's SINR over all possible locations in an arbitrarily-shaped region poses a significant challenge for analytical analysis. Secondly, with the consideration of the different SU activity protocols, only the active SUs generate interference to other SUs and PU-Rx. This means that when accounting for the interference to a SU-Rx (which is the desired receiver for a certain SU), the distance between an interfering SU and PU-Rx is correlated to the distance between this interfering SU and the SU-Rx. This distance correlation poses a second significant challenge for analytical analysis.
In this work, in order to evaluate the performance of the secondary network in underlay cognitive networks, we study the average number of active SUs. The average number of active SUs is an analytically tractable performance metric, which can indirectly measure the SU throughput under certain conditions.
For example, if the SINR threshold for SUs is not too high or each SU is sufficiently close to its desired receiver, it is possible that almost every active SU can transmit successfully. Under such conditions, the average number of active SUs plays the dominant role in determining the aggregate throughput of SUs 3 .

The main analytical result in this section is presented in Theorem 4 below.
Theorem 4: For any SU activity protocol with independently and uniformly distributed SUs inside an arbitrarily-shaped finite region, the average number of active SUs is given by where µ I (0) denotes the zero-th moment of the interference at an arbitrarily located PU-Rx from a random SU, which is dependent on the SU activity protocol.
Proof: See Appendix A-D.  probability. However, this would decrease the number of active secondary users, which means the licensed spectrum is not efficiently reused. In this context, (15) and (27) provide an analytical means for evaluating this tradeoff in the performance of both the primary and secondary networks. In the next section, we will use the primary-secondary performance tradeoff as a systematic way to compare the performance of the different SU activity protocols.

VI. NUMERICAL RESULTS
In this section, we present numerical results to investigate and compare the performance of the SU activity protocols. In order to validate the numerical results, we also present simulation results which are generated using MATLAB and are averaged over 1 million simulation runs. For the simulation results, we use the following procedure to uniformly distribute the SUs inside an arbitrarily-shaped region [40]: Unless specified otherwise, the values of the main system parameters shown in Table I are used. All the distance, side length and radius values are in meters (m).

A. Validation of Cooperation-based Protocol Analysis
First, we investigate the accuracy of the cooperation-based protocol analysis given in Section IV-C.

B. Moments of Aggregate Interference at the Primary Receiver
In this subsection, we investigate and compare the moments of the aggregate interference at the PU-Rx for the different SU activity protocols. We also illustrate the versatility of the proposed framework in being able to handle arbitrarily-shaped cognitive network regions.
We consider an arbitrarily-shaped cognitive network, as depicted in Fig. 1, with side lengths S 1 = and S 4 = D and interior angles θ 1 = π/2, θ 2 = π/4, θ 3 = π − arcsin Without loss of generality, the origin is assumed to be at vertex V 1 . The PU-Rx is located at coordinates ( Applying the algorithm in [29], the distance distribution function f R (r) can be expressed as Substituting (28) in Corollaries 1−3, we can obtain the analytical n-th moment results. Table II shows the 1st, 2nd and 3rd moment of the aggregate interference for the three SU activity protocols with D = 150 m. The simulation results are an excellent match with the analytical results, which confirms the accuracy  of the results in Corollaries 1−3. We can see from Table II that for the considered case, the proposed cooperation-based protocol has the smallest values of the moments, i.e., it results in the smallest aggregate interference. The next best is the threshold-based protocol, followed by the guard zone protocol.

C. Outage Probability at the Primary Receiver
In this subsection, we investigate and compare the outage probability at the PU-Rx for the different SU activity protocols. Fig. 3 plots the number of SUs M versus the outage probability, P out , for the different SU activity protocols and the arbitrarily-shaped cognitive network region considered in Section VI-B with D = 150 m. The analytical results are plotted by substituting (28) in Theorems 1−3 and then substituting in (16) and (15). As illustrated in this figure, for the considered case, the cooperation-based performs the best while the guard zone protocol performs the worst. For example, for M = 100 SUs inside the  arbitrarily-shaped region, the cooperation-based protocol can achieve the best QoS of P out = 5.33 * 10 −3 at the PU-Rx. However, the threshold-based protocol and guard zone protocol can only achieve P out = 7.59 * 10 −3 and P out = 1.54 * 10 −2 , respectively.
It must be noted that such an analysis has two main issues. Firstly, for a given shape of the network region and a given location of the PU-Rx, the outage at the PU-Rx strongly relies on the protocol system parameters (i.e., the guard zone range r f for the guard zone protocol, activation threshold γ for both of the threshold-based and cooperation-based protocols) and different values of the protocol system parameters can lead to a different performance ordering of the SU activity protocols. Secondly, it focuses on the performance in the primary network only. These aspects are addressed in the next Section VI-D.

D. Comparison of Secondary User Activity Protocols
In this section, we investigate and compare the SU activity protocols in terms of their effect on the primary network (i.e., the outage probability) and the secondary network (i.e., the average number of active SUs).  Fig. 4(a)) and Nakagami-m fading m = 1, 3, 5 ( Fig. 4(b)), respectively. The following approach is adopted to work out these curves for the SU activity protocols: 1) For each outage probability value, using (15), (16) and Theorems 1−3, we can find the value of r f for guard zone protocol and γ for threshold-based protocol and cooperation-based protocol, respectively; 2) We substitute the value r f and γ into (27) and Corollaries 1 − 3 to obtain the average number of active SUs for each protocol. This ordering can be intuitively explained as follows. The guard zone protocol supports the largest number of active SUs because it enables the SUs to determine their "average" impact on the PU-Rx from long-term sensing signal monitoring. The outage probability is usually caused by the SUs that are close to the PU-Rx. By forming a proper guard zone region around the PU-Rx, the interference from the nearby SUs is avoided and on average more SUs are allowed to transmit. The threshold-based protocol supports the smallest number of active SUs due to the effect of uncorrelated fading between sensing and transmitting channels. For example, the fading on the sensing channel may be severe but the fading on the SU transmitting channel may be weak. Thus, the SU may receive a weak signal on the sensing channel and decide to transmit, which may generate severe interference for the PU-Rx. The cooperation-based protocol helps to minimize the effect of uncorrelated fading channels by utilizing the local information exchange among SUs. Therefore, the cooperation-based protocol allows a higher activation threshold while still meeting the same outage value. This results in the larger number of active SUs, compared to the threshold-based protocol. Although the guard zone protocol supports the largest number of active SUs, the implementation of this protocol is only possible in scenarios that allow a long-term sensing signal monitoring before SUs can transmit. On the other hand, the threshold-based and cooperation-based protocols only rely on the short-term signal monitoring. It must be noted that a more comprehensive comparison requires a rigorous study of the tradeoff between performance and implementation complexity in the scenario of interest, which is outside the scope of this paper.

VII. CONCLUSIONS
In this paper, we have proposed a framework to analyze the performance of arbitrarily-shaped underlay cognitive networks with different SU activity protocols. The framework depends on the MGF of the interference due to a random SU and allows closed-form computation of the outage probability in the primary network as well as the average number of active SUs in the secondary network. We have also applied cooperation in the context of the underlay cognitive network to come up with a cooperation-based SU activity protocol, which includes the existing threshold-based protocol as a special case. We studied the average number of active SUs for the different SU activity protocols, subject to a given outage probability constraint at the PU and we used it as an analytical approach to compare the performance of different SU activity protocols in the underlay cognitive networks. Our results showed that, in the short-term sensing signal monitoring scenarios, the cooperation-based protocol improves the networks' performance compared to the threshold-based protocol. The proposed framework is especially relevant for emerging ultra-dense small cell deployment scenarios, where network regions can be arbitrarily-shaped. Future work can consider the generalization of cooperation-based protocol with multiple activation thresholds, which is outside the scope of the present work. It can also analyse the throughput performance of the SUs subject to a quality-of-service constraint.

APPENDIX A PROOF OF THEOREMS AND COROLLARIES
In this appendix, we derive the moment generating function of the interference from a random SU and the corresponding n-th moment for the SU activity protocols.
From (4), (5) and (6), we can see that whether a random SU generates interference or not is strongly dependent on the SU's random distance to the PU-Rx, R. The conditional probability mass function (PMF) of the interference from a SU is given by where P active|R represents the conditional probability that a SU is active, which is conditioned on its random distance R to the PU-Rx.
Using (29), we can express the MGF of the interference from a random SU (defined below (11)) as Substituting (30) into (13), the n-th moment of the interference from a random SU is We now define and use the value of the conditional probability P active|R for different SU activity protocol to derive the main analytical results in the paper.
A. Proof of Theorem 1 and Corollary 1 Proof: For the guard zone protocol, (4) shows that the interference from a random SU is given by . Thus, the conditional probability that a SU is active can be expressed as Substituting (32) into (30) and (31), the MGF and n-th moment of the interference from a random SU for the guard zone protocol are respectively given by and Hence, we arrive at the results in Theorem 1 and Corollary 1.

B. Proof of Theorem 2 and Corollary 2
Proof: For the threshold-based protocol, (5) shows that the interference from a random SU is given by P T GR −α 1 (PT S HR −α ≤γ) , i.e., the SU generates interference as long as H ≤ γR α P T S when the distance to PU-Rx is given. Thus, the conditional probability that a SU is active can be written as Substituting (35) into (30) and (31), we can express the MGF and µ I (n) of the interference from a random SU as and Hence, we arrive at the results in Theorem 2 and Corollary 2.

C. Proof of Theorem 3 and Corollary 3
Proof: For the cooperation-based protocol, consider a typical SU node A, cooperating with node B, as shown in Fig 1(c). Given the position of node A, let p nt represents the conditional probability that node B leads to node A deciding not to transmit. This event occurs when node B falls into the cooperative region D A (r c ) around the typical user A and the received signal at node B is greater than the activation threshold γ. Using this fact, we can express p nt as where r B = x 2 B + y 2 B is the distance from node B to the PU-Rx 4 , (x B , y B ) is the coordinate of node B, f H B (h B ) represents the fading power distribution on the user B's sensing channel and D A (rc)×A denotes the integration over the overlap region between A and D A (r c ).
We can see from (38) that p nt is a function of the location of node A. Consequently, the integration in (38) is very complicated to evaluate in closed-form. In order to simplify the analysis, we assume that: • the cooperation range r c is small compared to the size of the cognitive network region; • the SUs within the cooperation range experience the same path-loss; • the effect from the boundary is neglected so that the overlap region is the same as the cooperative region irrespective of location of node A.
Thus, we can approximate (38) as where R A is the distance from node A to the PU-Rx.
The complement of the probability p nt , denoted by 1 − p nt , is known as the probability that node B causes node A to transmit. In addition to node A, there are a total number of M − 1 SUs which are independently distributed inside the network region. Consequently, the conditional probability that M − 1 nodes can make node A to be active is (1 − p nt ) M −1 , where p nt is given by (39).
In order for node A to transmit, both the received signal powers at the SUs inside D A (r c ) and the received signal power by node A on the sensing channel must be less than the activation threshold γ.
Since nodes are identically distributed, we can drop the subscript A in R A and B in F H B (·). Thus, the conditional probability of a random SU being active can be expressed as Then the MGF and n-th for the interference from a random SU can be obtained by substituting (40) into (30) and (31) respectively, which can be expressed as and Hence, we arrive at the results in Theorem 3 and Corollary 3.

D. Proof of Theorem 4
Proof: From definition, M active is the mean value of the number of active SUs, after averaging over all possible networking realizations. Let P active denote the (unconditional) probability of a SU being active.
Mathematically, the average number of active SUs can be written as In order to further simplify (43), we can exploit the fact that P 0 T = 1, E G {G 0 } = 1 and R 0 = 1. Thus, we can rewrite (43) as Comparing the latter term in (44) with (31), we can see that it is in fact the zero-th moment of the interference from a random SU. Thus, we arrive at the result in (27).


extfieldsofstudy: Physics Medicine

text:
Fourier transform of fermionic systems and the spectral tensor network

Leveraging the decomposability of the fast Fourier transform, I propose a new class of tensor network that is efficiently contractible and able to represent many-body systems with local entanglement that is greater than the area law. Translationally invariant systems of free fermions in arbitrary dimensions as well as 1D systems solved by the Jordan-Wigner transformation are shown to be exactly represented in this class. Further, it is proposed that these tensor networks be used as generic structures to variationally describe more complicated systems, such as interacting fermions. This class shares some similarities with Evenbly&Vidal's branching MERA, but with some important differences and greatly reduced computational demands.

Leveraging the decomposability of the fast Fourier transform, I propose a new class of tensor network that is efficiently contractible and able to represent many-body systems with local entanglement that is greater than the area law. Translationally invariant systems of free fermions in arbitrary dimensions as well as 1D systems solved by the Jordan-Wigner transformation are shown to be exactly represented in this class. Further, it is proposed that these tensor networks be used as generic structures to variationally describe more complicated systems, such as interacting fermions. This class shares some similarities with Evenbly & Vidal's branching MERA, but with some important differences and greatly reduced computational demands. Solving strongly-correlated many-body systems is one of the primary challenges of modern quantum mechanics that arises in a wide variety of fields and contexts. Because direct approaches are usually intractable, an array of analytical and numerical techniques and approximations have been developed over the last century, each associated with its own region of validity, accuracy and difficulty.
One relatively modern approach is based on tensor network decompositions of many-body wavefunctions [1][2][3][4], motivated by our understanding of quantum information in this context. By decomposing the wavefunction into a particular product of tensors, one defines the structure of entanglement that is permitted (for example, the low-energy states of many local Hamiltonians obey an area law scaling for entanglement entropy [5][6][7][8]). Typically, one applies the variational principle within this class of wavefunctions to determine, for example, the tensor network state closest to the ground state. Increasing the rank of the decomposition increases the amount of allowable entanglement, and potentially leads to a more accurate description of the many-body state.
A wide variety of tensor network geometries have been proposed, beginning with the matrix-product state (MPS) [9][10][11] that is the foundation of the famous density matrix renormalization group [12] and Wilson's numerical renormalisation group [13]. This one-dimensional structure connects nearest neighbors in a chain, and is extremely accurate for 1D systems that have spatially-local correlations (proven to be exponentially close to the low-energy states of gapped, local 1D Hamiltonians [5]). Real-space renormalization group ideas lead to the development of the tree-tensor network (TTN) [14,15] and the multi-scale entanglement renormalization ansatz (MERA) [16,17]. The MERA in particular is able to reproduce larger amounts of entanglement such as that necessary to describe critical, 1D quantum systems -and has been found to correctly reproduce the features of the corresponding universality class at the renormalization fixed-point, as described by conformal field theory [18].
Extensions to higher dimensional systems are also possible. Although the MPS and TTN do not have the correct geometry to represent the area law for large 2D systems [15,19,20], the MPS can be generalized to to a two-dimensional tensor network state commonly referred to as a projected entangledpair state (PEPS) [21][22][23]. The MERA is also generalized to higher dimensions in a straightforward fashion [24]. All the above techniques have shown success in solving 2D systems (e.g. [25][26][27][28]), but are somewhat handicapped by relatively large computational demands for even slightly-entangled systems.
Furthermore, both PEPS and the 2D MERA are limited to obey the area-law for entanglement entropy, where the entanglement entropy of a region is proportional to its boundary area (or perimeter, in 2D). This excludes important classes of physical systems which violate the area law -notably any 2D system exhibiting a 1D Fermi surface (resulting in a logarithmic violation [29]), and exotic phases such as Bose metals [30][31][32].
This situation left the field of tensor networks in an awkward position, unable to accurately deal with what many outside the field consider to be the simplest models of noninteracting free-fermions, and their perturbations (i.e. Fermi liquids). More recently, a new class of tensor network that exhibits very large amounts of entanglement (up to volumetric) was proposed by Evenbly & Vidal, which they have dubbed the 'branching MERA' [33]. However, its properties and relationship to Fermi liquids has not been determined, as far as the author is aware.
In this work, I propose a new tensor-network geometry that mimics the structure of a spectral transformation and includes the quantum Fourier transform (for fermions) as a trivial example. Up to a reordering of the lattice, this 'spectral tensor network' can be seen to be a generalization of TTN, or equally a simplification of branching MERA, and local expectation values can be extracted from a wavefunction of n lattice sites in time n log n. Similarly, it is related to previously suggested circuits for use in linear-optics quantum computing [34] and its fermionic analogue [35]. Here, I will give exact wavefunctions for translationally-invariant free fermion systems in arbitrary dimensions as well as examples of 1D systems that are exactly solvable via Jordan-Wigner transformations (Heisenberg XX chains, transverse-field Ising model, etc). I will then describe a procedure for finding a variational approximation of ground state of arbitrary local Hamiltonians in an efficient manner, which may be particularly relevant to simulations of 2D systems in the Fermi liquid phase, before concluding with remarks on future directions.
Quantum fast Fourier transforms: We now discuss the unitary circuit required to transform a quantum lattice system between real-and momentum-space, and write it as a log-depth circuit using at most two-body gates. The discrete Fourier transform has long been known to decompose into a series of sparse operations [36,37], in a technique generally referred to as the fast Fourier transform (FFT). Here we will leverage this decomposition to describe the unitary circuit for the quantum Fourier transform for fermionic lattice models (similar to [35]), and in the next section show that local expectation values of wavefunctions based on this circuit can be efficiently determined.
Following the spirit of Danielson and Lanczos [36], we first demonstrate that the fermionic Fourier transform over n (even) sites can be decomposed into two parallel Fourier transforms over n/2 sites followed by simple 2-body linear gates (matchgates): (1) The fermionic creation operator for site x is denoted byĉ † x , and the LHS of the above is (proportional to) the creation operator for the momentum mode k (with wave-number 2πk/n). The RHS is the sum of two terms, each corresponding to a Fourier-transformed mode on the subset of even (or odd) sites. This sum is a linear transformation between two modes that can be implemented with a 'beam-splitter' and 'phase-delay' (graphically depicted in Fig. 1). The beam-splitter is nothing other than the two-site Fourier transform written above in the number basis {|00 , |01 , |10 , |11 }. Notice thatF 2 |11 = −|11 because of the anti-commutation relations of the creation/annihilation operators. The phase-delay takes care of the so-called twiddle-factor e 2πik/n , and is writtenω k n =Ẑ 2k/n (Ẑ =1 − 2n is the Pauli matrix,n being the occupation operator).
The decomposition in Eq. (1) can be iterated k times to fully determine the Fourier transform over 2 k sites -however one must be careful to keep track of the ordering of modes, given by a bit-reversal operation. The resulting circuit for 8 sites is given in Fig. 1 (a). The structure of the circuit is identical to the Cooley-Tukey FFT [37]. One can independently verify that the circuit produces the correct transformation because it is (a) linear in the field operators, and (b) performs the correct transformation on the single-particle subspace, in analogy with the classical FFT. For systems of higher dimensions, the Fourier transform along each dimension can be applied sequentially along parallel wires and then decomposed. Furthermore, the decomposition can be alternated along different dimensions, for instance to recover an alternating structure with gates along the x, y, etc dimensions at each length scale, as shown for 2D in Fig. 1 (b).
So far, this gives an efficient prescription for performing the Fourier transform on fermionic systems in arbitrary dimensions using a log-depth circuit and two-body gates. This is potentially useful for state preparation or measurement schemes. More generally, a linear circuit with the same structure can be applied to bosonic systems. For bosons,F 2 is the beamsplitter operation that maps two input annihilation operators (â 1 ,â 2 ) to (â 1 +â 2 ,â 1 −â 2 )/ √ 2, while the phase gatê Z a/b transformsâ 1 to (−1) a/bâ 1 . Unlike fermions, the local Hilbert-space dimension is not fixed at two and in general can grow as large as the total number of particles in the system (and thus will not lead to a numerically efficient scheme as discussed below -though this has already been suggested as a powerful tool in linear-optics quantum computation [34]). It would be interesting to determine if the structure is applicable to anyonic or spin models.
The spectral tensor network: Consider a chain of n = 2 k sites described by the second-quantization formalism, that begin in the simple Fock-state |Ψ 0 = |α 1 |α 2 . . . |α n = c †αn n . . .ĉ †α1 1 |0 . The circuit corresponding to the inverse Fourier transform can be applied to an (unentangled) productstate wavefunction in momentum space to yield a (highlyentangled) wavefunction in real space, as depicted in Fig. 2. I call this tensor network structure a 'spectral tensor network', and the wavefunction is a spectral tensor network state. In general, the connectivity of the diagram is that of a hypercube with side length 2 (even in higher spatial dimensions). Ignoring completely the permutation of sites at the bottom of Fig. 2, the state resembles a branching MERA with half of the gates removed (making it significantly cheaper to contract), or similarly a generalized TTN. However, the site reordering turns the traditional concept of real-space renormalization on its head, as the tensor network couples sites with maximal separation first. An intuitive explanation more likely comes from the decomposition of the cyclic group C n corresponding to translation invariance that motivates Eq. (1) and the FFT (where C pq = C p × (C pq /C p ), which is isomorphic to C p × C q ).
When performing calculations in the Fock basis, one must remember to respect the correct statistics of the degrees of freedom in the tensor network diagram by performing the appropriate permutation operation when two wires crossspecifically, introducing a phase of −1 whenever an odd number of fermions cross [38][39][40][41]. This phase can be accounted for by including an extra tensor at every crossing, fortunately without increasing the scaling of the computational cost.
Together, this gives us a prescription for describing translationally-invariant free-particle systems in arbitrary dimensions, because these Hamiltonians are exactly diagonalized by the Fourier transform. In particular, we have a tensornetwork wavefunction for free fermions in arbitrary dimensions. As is well known, such wavefunctions can exhibit quasi-long range correlations (polynomially decaying) and logarithmic violations to the area law. Nonetheless, we now show that extracting local expectation values from these wavefunctions can be achieved by an efficient tensor network contraction scheme, scaling (essentially) linearly with n.
First, we take advantage of the unitary nature of the tensors to vastly simplify the calculation of expectation values of local operators. Figure 3 shows the tensor network corresponding to the expectational value of a single-site operator. The number of tensors reduces from O(n log n) to O(n) and by con- For the systems we study here, both ground states and (grandcanonical) thermal states can be studied because the transformation exactly diagonalizes the Hamiltonian.
As an simple example, we examine free-fermions in 1D and 2D with nearest-neighbour tunnelinĝ where <i, j> corresponds to neighboring sites on the lattice with i < j (or similar in higher dimensions). We create the ground state wavefunction for a low filling factor and calculate the normalized first-and second-order correlation functions: The numerical results for 1D and 2D are shown in Fig. 4. These results should be considered exact, to numerical precision. The 2D simulation describes a highly-entangled system (in real-space) of more than quarter of a million sites, yet the calculation was easily completed on a laptop computer using MATLAB (of course, in this case the results could be obtained analytically or by alternative numerical techniques).
Generic free fermion systems: The quantum circuit structure above can be used to construct translationally invariant states in a very wide range of phases by a straightforward extension to more spin or spatial degrees of freedom, multiple species, and/or including a Bogoliubov transformation to treat anomalous Hamiltonian terms (such asĉ iĉj + h.c.). The first-order and second-order normalized correlation functions g (1) and g (2) for the ground state of a 1D system of free fermions (103 fermions on 1024 sites). (b) Secondorder normalized correlation function g (2) for a 2D system of free fermions (2093 fermions on a 512 × 512 lattice). In both cases the distance (∆x and ∆y) is normalized to the mean particle spacing.
In general, we can consider each site to allow s different types of fermion, described by a Hilbert space of dimension 2 s . Then the Fourier transform from a state initially unentangled in momentum space takes the same form as before, by treating each fermion type individually. The entire state can be encapsulated in a spectral tensor network with bond dimension χ = 2 s . Conversely, the Fourier transform partially diagonalizes translationally invariant free-fermion models, resulting in a Hamiltonian that is local in momentum space (but couples the different species in a momentum-dependent fashion) -meaning the spectral tensor network can describe all eigenstates of translationally invariant bilinear Hamiltonians. With s > 1 we have a richer set of possibilities in a given momentum mode than simply 'occupied' or 'unoccupied', resulting in wider range of possible phases. These include the standard multiple-band possibilities including gapped insulators, standard gapless metals, higher-dimensional systems with interesting Fermi surfaces such as the Dirac point observed in graphene, and perhaps most interestingly, topological systems with non-trivial Chern numbers, as seen in the integer quantum Hall effect. These include as a subset the chiral PEPS states given in Ref. [42].
Hamiltonians with anomalous terms are only partially diagonalized by the Fourier transform, leaving coupling between opposite momentum modes ±k. The Supplemental Material describes how to include the Bogoliubov transformation into the spectral tensor network directly in momentum space while not changing the n log n computational scaling. This addition allows us to treat systems with superconductivity, Majorana fermion modes, or symmetry-protected topological order.
Some spectral tensor network ground states, such as insulators, chiral systems, and 2D systems with Dirac points have entanglement scaling with the area law. Meanwhile, other states such as those in the metallic phase contain significantly more entanglement with a logarithmic violation. It is even possible to achieve a volumetric scaling, for example, with a high-energy eigenstate or the ground state of a long-range Hamiltonian with random couplings. As far as the author is aware, the spectral tensor network is able to exactly de-scribe a wider range of phases and dimensions than any other efficiently-scalable tensor network ansatz.
An additional result is a compact and exact tensor-network representation of strongly-correlated 1D systems that can be analytically solved using a Jordan-Wigner transformation. The Appendix provides details on the process and uses the transverse-field Ising model as an example.
Simulation of arbitrary fermionic systems: More generic systems are free to be studied by employing the variational method on the manifold of states defined by the tensor network diagram (in addition to the unitary constraints and any symmetry constraints of the model, e.g. the fermion parity). For instance, simple energy minimization may yield states very close to highly-entangled ground states, particularly in the Fermi-liquid phase where the entanglement structure should be related to that of free fermions. The bonddimension of the tensor network can be increased by combining neighboring lattice sites, which increases the fraction of Hilbert space covered by the ansatz and thus potentially the accuracy of the minimum energy state. This is an area of intense interest to the author and is the subject of further work. Furthermore, it would be interesting to see if the spectral tensor network can accurately represent systems with different boundary conditions or impurities, or be applied effectively to spin systems.

Conclusion:
The spectral tensor network has been introduced here as a way of efficiently representing the quantum fast Fourier transform and certain classes of quantum states. The Fourier transform can be used to construct free-fermion states with a logarithmic violation of the area law, and as far as the author is aware is the first efficiently contractible tensor network that has been shown to exactly capture this phase in two-and higher-dimensions.
The tensor network is shown to be a convenient form for capturing analytic solutions to 1D spin problems that are solved by the Jordan-Wigner transformation. Further, we suggest that this tensor network may be used as a variational ansatz for low-energy states of many-body systems. This may be especially effective in the case of Fermi-liquid phases, where from a local perspective the system is highly entangled and is somewhat difficult to treat with existing tensor network techniques, while the Fourier transform is able to convert the system into a relatively disentangled momentum-space basis. Work in this direction is ongoing.
The spectral tensor network is somewhat related to the branching MERA construction of Evenbly and Vidal, with two major differences. The spectral tensor network contains only half the tensors of the branching MERA and is more efficient numerically. A more striking difference is the nonlocal reordering of lattice sites placed at the bottom of the unitary circuit. In complete opposition to the spirit of real-space renormalization, the unitaries at the bottom of the circuit deal with the longest length-scales of the system, with the length scales decreasing as we ascend the diagram.
Here we give additional technical details to complement the main text. We begin by giving a fuller derivation of the quantum fast Fourier transform for fermion/bosonic systems, and discuss the inherent freedom allowed by the decomposition. We then detail the tensor contractions necessary for performing calculations with the spectral tensor network, including derivations of the computational cost of measuring one-and two-site local variables and performing ground state optimizations in arbitrary dimensions. We also consider the extended case corresponding to a Fourier transform combined with a Bogoliubov transform that couples modes with opposite momentum, which should be contracted in a slightly different order to remain efficient. The 1D transverse-field Ising model is given as an example application of how both the Jordan-Wigner transformation and Bogliubov transform can be used in conjunction with the spectral tensor network to efficiently extract properties of strongly-correlated systems.

Derivation of the quantum fast Fourier transform
The Fourier transform for fermions (and bosons) over n (assumed even) sites is given by the following linear transformation: We now define two subsystems containing the even sites: and the odd sites Each subsystem contains n/2 sites and have associated Fourier transforms: It is straightforward to verify the following relation (Eq. (1) of the main text), which decouples even and odd sites in the full n-site Fourier transform: (10) This can be written in terms of the above variables as where we note thatã † k+n/2 =ã † k and similarlyb † k+n/2 = b † k . Equation 11 is a simple two-body, linear transformation between modes {ã † k ,b † k } and {c † k ,c † k+n/2 }. Generically this transformation can be represented with the unitary This allows us to decompose the Fourier transform over n sites into smaller gates, which include the two smaller Fourier transforms for n/2 theâ † x andb † x modes (i.e. the even and odd sites), as well as n/2 one-and two-body linear gates. By iterating the decomposition recursively, the remaining Fourier transforms can decomposed into one-or two-body gates. The complete decomposition has depth ∼ log 2 (n) with a total of ∼ n log 2 n gates.
One interesting feature of the fast Fourier transform is the flexibility of in the decomposition, which comes from three sources: (a) graphical manipulations of the unitary circuit/tensor network diagram, (b) the fact that the Fourier transform is self-transpose,F n =F T n , and (c) commutability between different dimensions. Graphical manipulations include 'pushing' the permutation through to the top of the diagram, which simply rearranges the gates and means the permutation performed at the momentum space side of the diagram. The self-transpose property can be applied at different stages of the decomposition. An example using 8 sites is provided in Fig. 5. Furthermore, in two or higher dimensions the transformation layers along different directions commute -see for example Fig. 6. This flexibility is analogous to that available to numerical algorithms for the classical FFT.
As a final note, it should be possible to extend this decomposition to system sizes that are not a power of two while retaining the efficiency. For instance, the decomposition works for factoring out of n any prime factor p, but would necessitate p-body gates and therefore increase the computation scaling as a power of χ. The classical Fourier transform can calculated efficiently (i.e. with n log n scaling) even for large primes n [43], and it would be interesting to determine if a simple quantum circuit can be deduced for these situations, and furthermore whether it would be associated with an efficiently contractible tensor network. However this is beyond FIG. 7: (Color online) The expectation value of a single-body operator can be contracted efficiently by contracting indices on the outside of the diagram and working inwards. Each primitive step consists of contracting a section of the diagram like that highlighted in yellow, corresponding to the operation in Fig. 8 (a). This has to occur n times, leading to a total cost scaling as O(nχ 5 ).
the scope of the present work.

Tensor contractions for one-and two-site operators, and optimization
In the main text, we briefly showed that the expectation value of a single-site observable can be calculated with cost O(n). To reiterate this more precisely, we describe further both the process of removing unitary gates from the expectation value and the contraction scheme required to efficiently compute the final value.
First, we must recall that the tensor network diagrams here are for fermionic Hilbert spaces. Each bond (or wire) in diagrams such as Fig. 3 of the main text represent one or more fermionic modes. The tensor network language lets us graphically express the total Hilbert space as if it were a product of independent Hilbert spaces for each mode (or wire). However, we know such a decomposition is not possible for fermionic Hilbert spaces, at least in the usual sense, and thus additional rules are required to remain consistent with fermionic statistics. Specifically, when two wires cross, this is equivalent to algebraically re-ordering our fermionic modes and thus should introduce a factor of −1 when an odd number of fermions pass through each wire. One way of encoding this is to place a diagonal operator ("mini-tensor") at each of the wire crossings, and then the resulting diagram can be interpreted and computed in the usual (bosonic) sense. Furthermore, it is always possible to choose a new ordering of the fermionic modes that we use to define our Fock-space basis, in either the traditional algebraic or graphical tensor network language. In the diagrams, this is achieved by dragging the wires over each other and pulling them through tensors, each of which is allowed without changing the result (note that mini-tensors at wire crossings may be added or removed because of these manipulations). These graphical rules are a powerful tool for simplifying tensor network diagrams. As an example, consider Fig. 3 of the main text. In this equation, all of the unitaries that are not causally connected to the op-erator at the 7th site cancel. To see this cancellation clearly, we can drag around the wires in the centre (those that cross the "physical" plane) so that the cancelling unitaries multiply their conjugates without wire crossings in-between (at which point they can be removed from the diagram). In some cases (e.g. tensors further from the centre) it may even be necessary to move the unitary tensors up or down to achieve this effect. The freedom given by the allowed manipulations leads to the conclusion that wire crossings do not impair the application of the unitarity identityÛÛ † =Î.
Next we consider the contraction scheme for efficiently computing this expectation value, as depicted in Fig. 7. The contraction proceeds by working from the outside inwards, taking advantage of the very small amount of connectivity in the diagram (consider that the diagram folded around a horizontal line through the center is a simple tree). Each of these basic steps follows the diagrams in Fig. 8 (a) and have cost O(χ 5 ), and occur n times, leading to a total cost of O(χ 5 n).
The expectation value of few-site observables can also be calculated efficiently with cost O(n), although with a cost which grows exponentially with the size of the operator in question. In Fig. 9, the necessary contraction for a widelyseparated, two-site operator is shown. Note here that we are really working in the fermionic Hilbert space and it is unnecessary to include a string of operators between the two observables, as would be typically seen in the Jordan-Wigner transformation (this is a demonstration of the power and simplicity of the graphical, fermionic tensor network language). Like we saw earlier, many of the unitaries cancel each other resulting in a sparser tensor network diagram.
As before, this diagram can be contracted using simple steps starting from the outside of the diagram and working towards the physical indices, layer-by-layer. These steps each cost up to O(χ 8 ) for two-site operators, and are shown in Fig. 8. At the outer-layers, the single-site contractions ( Fig. 8 (a)) suffice until the two sites 'fuse' in the tree, described by Fig. 8 (b). After this point, a effective two-site 'density operators' must be carried through the diagram as in Fig. 8 (c). For a given observable, n such steps are necessary, making the total cost O(χ 8 n) for a two-site observable. The exponent of χ would grow for observables over more sites.
Fortunately, when computing a range of observables many computations can be reused to reduce the total cost. For instance, in a non-translationally invariant model, the entire set of one-body observables Â i can be calculated with cost O(χ 5 n log n). This is achieved by noting that, over all values of i, only two versions of the outside contraction is needed and can be reused (corresponding to the left and right versions of the diagrams in Fig. 8 (a)). However, there are n/2 two-body unitaries in that layer of the circuit, leading to n unique calculations. At the next layer, there are now four possible 'directions' to account for but only n/4 unitaries, so there are again n unique calculations to perform -and so on for every layer. Because there are log 2 n layers, the total number of unique contraction steps required is reduced to just n log 2 n , while a naïve scheme would perform n 2 contraction steps. As another example of this speed-up, in a translationallyinvariant system, the entire set of two-body observables Â 0Bi can be calculated with cost O(χ 8 n log n) (as was done to generate Fig. 5 in the main paper). The same scaling applies to the expectation value of local, two-body Hamiltonians (with no assumption on translational invariance). With a simple modification to the above procedure, one can additionally recover the derivative of the expectation value with respect to the tensors themselves (the so-called 'environment' of each tensor) with the same O(χ 8 n log n) scaling. This allows us to follow a derivative-based optimization procedure for determining the state with minimum energy, such as steepest-descent within the unitary subspace [44], singular-  value decomposition updates [45] or more complicated approaches [46].

Jordan-Wigner transformation for spin chains and Bogoliubov transformations
The spectral tensor network is also useful in treating nonfermionic systems. For example, the Jordan-Wigner transformation can be used to transform some 1D spin systems into non-interacting fermionic models. A straight-forward example is the fully-anisotropic Heisenberg spin-1/2 chain (XX  Fig. 10. Efficient contraction relies on unitarity (first equality) followed by contracting the diagram from the outside in. The typical step for large systems is highlighted in yellow, corresponding to first diagram in Fig. 12. model), which transforms into the free-fermion system studied in the main paper. Other models, such as the quantum transverse-field Ising chain on n sites with Hamiltonian are slightly more complicated because the require a Bogoliubov transformation between opposite momentum modes. This system corresponds to a free fermion system by the transformationĉ i = 1 2 (X i + iŶ i ) j<iẐ j whereĉ i are fermion annihilation operators, resulting in This Hamiltonian is bilinear in the fermionic operators and translationally invariant, and so can be solved using a Fourier transform. In the case of a quadratic Hamiltonian with anomalous pair terms, like above, a Bogoliubov transformation coupling modes with opposite momentum will diagonalize the Hamiltonian. That is, we coupleĉ k withĉ † −k , whereĉ k = j exp(2πijk)ĉ j / √ n, by applying an additional transformation at the 'top' of the tensor network diagram, as shown in Fig. 10.
However, contracting the tensor network naïvely in the previous order will result in growing bond-dimensions in the intermediates steps. To perform the contraction efficiently, we simply perform the layer-by-layer 'renormalization' on the coupled pairs instead of the individual sites, as shown for a single-site observable in Fig. 11. At each step, we combine two pairs of sites with a unitary transform and partial trace, resulting in a density matrix for a single pair of sites. We can see the steps required for calculating single-site observables in Fig. 12 O(n log n) steps for a full set on every site by reusing calculations). A similar procedure applies to the case of observables over two or more sites.
We have implemented and tested this procedure for the transverse-field Ising model. In Fig. 13 we present results for the magnetic susceptibility in the field direction, based on a simple numerical derivative evaluating We observe a sharp peak at the critical point at h = 1, as expected.
The scheme presented here might be improved on in several ways. For instance, it has not yet been investigated if the spectral tensor network can represent the Bogoliubov transformation natively, that is, without the extra tensors at the top linking ±k modes, which is the subject of future work.


Virtual Backbone Trees for Most Minimal Energy Consumption and Increasing Network Lifetime In WSNs

Virtual backbone trees have been used for efficient communication between sink node and any other node in the deployed area. But all the proposed virtual backbone trees are not fully energy efficient and EVBTs have few flaws associated with them. In this paper two such virtual backbones are proposed. The motive behind the first algorithm, Most Minimal Energy Virtual Backbone Tree (MMEVBT), is to minimise the energy consumption when packets are transmitted between sink and a target sensor node. The energy consumption is most minimal and optimal and it is shown why it always has minimal energy consumption during any transfer of packet between every node with the sink node. For every node, route path with most minimal energy consumption is identified and a new tree node is elected only when a better minimal energy consumption route is identified for a node to communicate with the sink and vice versa. By moving sink periodically it is ensured the battery of the nodes near sink is not completely drained out. Another backbone construction algorithm is proposed which maximises the network lifetime by increasing the lifetime of all tree nodes. Simulations are done in NS2 to practically test the algorithms and the results are discussed in detail.

INTRODUCTION
Wireless sensor networks (WSN) can be defined as the number of sensor nodes which form a network and monitor the location and send the data to the sink. Some of the main applications of WSN are machine health monitoring, smart home monitoring, area monitoring etc. To achieve low cost monitoring, sensors are deployed in the specific area to be monitored. These sensors communicate with each other through wireless link. All the nodes must send their messages to the sink node in an energy efficient manner. For sustenance of the network, one must have both energy efficient transmission and high overall network lifetime. The main goal is to minimize the energy consumed and maximize the network lifetime. Clustering and backbone formation are two contrasting schemes for efficient routing in wireless sensor network [13][14]. Various types of clustering like distributed clustering, intra cluster routing exists. Basically every node will transfer its message to its cluster head and the cluster head would communicate to sink via many intermediate cluster head. Virtual backbone tree is a backbone formed to cover the entire network. Backbone consists of tree nodes which are selected based on the energy of the sensor node, fitness factor, distance from the sink node and also the angle in which the node has to transmit and receive packet from its parent. Other sensor nodes receive and send messages via the tree nodes. Every sensor node(non-tree node) will select a tree node as its parent. Virtual backbones not only provide energy efficient communication infrastructure but increases the network lifetime. The tree nodes which are near the sink node are prone to failure soon as most of the messages which are communicated pass through them. The biggest issue with the sensors is their limited power. In this paper, sink is assumed to be a mobilizer which has the ability to move within the sensor network and it has unlimited power.

RELATED WORKS
Virtual backbone tree has been constructed in many ways. One of the approaches used is by constructing connected dominating set [8][9][10]. T.Acharya et al build a connected dominating set which is distributed and nodes are given status as tree nodes dynamically and they forward their data to their parent and node does not need any routing table [1]. H. Raei et al have constructed a virtual backbone by first building a maximal independent set and then connecting them together [2]. Connected dominating set (CDS) gives minimal number of nodes through which a backbone is formed. When large number of packets is transferred through these nodes, energy of these backbone nodes get drained quickly leading to more re-construction and sometime network failure. Hence multiple connected dominating set were formed. Jing He et al have proposed a load balanced CDS, in which workload is shared between nodes and the number of dependents of particular tree node is load balanced [3]. Zhao et al maximize the overall network lifetime by constructing virtual backbone through rules 1, 2 and k and have implemented virtual backbone through iterative local replacement [4].
The second approach is to send BCR packet from the sink. The node which receives it calculates its fitness factor with respect to the node which had sent it. Time delay is calculated based on the fitness factor. Before this delay expires, if the node receives another BCR request packet it becomes a sensor node i.e. a non tree node else it becomes a tree node and becomes a part of the backbone. The non tree node picks the nearest tree node as its parent [5]. ViTAMin [6] is an extension of EVBT proposed in [5]. For all non tree node instead of picking the nearest tree as its parent, for each tree node distance from the sink is stored and a modified EBCR request packet is sent through with every non tree node is associated with a parent tree node such that it has a shortest path to the sink [6]. In modified-EVBT, energy consumed through various links are tracked in the every node and forwarded to their child node leading to a better EVBT in terms of energy consumed.

Most Minimal Energy consuming Virtual Backbone Tree (MMEVBT)
In this MMEVBT, firstly backbone tree construction algorithm has been proposed which ensures minimal energy consumption for all the packets sent by all the nodes. Though the energy consumption is kept minimal, the energy of tree nodes nearer to the sink will decrease rapidly. To overcome this, the sink which is a mobilizer changes its position periodically. In few applications like monitoring military battle fields, sink cannot move to any position in what wants to. So sink places itself in the best possible position which it can.
Based on the energy of a node, the node is given a status. If the energy is greater than threshold it is eligible to become a tree node but there are other conditions as well. A node can become a tree node when some node wants it as parent based on energy consumption between sink and itself . The main objective is to select a route path for every node which must be the most minimal and optimal path in terms of energy consumption to send a packet to the sink. Always a node i is a tree node when a node j wants it to be its parent. Any node j which is a child of node i can elect some other node as its parent node k when energy consumption through node i to the sink node is becoming greater than node k . If a tree node i which had child/children but now had lost all of them by the above process, then the node i becomes a non tree node which can become a tree node later on.
Each node has one of the statuses associated with it: Tree node, Permanent non tree node, Non tree node which can become tree node or a failed node. Total energy needed to send a packet from a node is minimal and optimal. if Energy i ≥Th&& Count(No. child(node i ))<=0 STATUS of node: Non tree node which can become tree node if some node wants it to be parent else if Energy i ≥Th&&Count(No. child(node i ))>0 STATUS of node: Tree node else if Energy i < Th STATUS of node: Non Tree node else STATUS of node: Node failed The energy consumption in data delivery is minimal because: i) All nodes whose energy greater than threshold and has the ability to be a tree node are selected ii) For every node N, a.
One finds the shortest path to the sink based on energy consumption b.
For all nodes which can become parent, whichever has Energy consumption (Sink Parent + Parent Node N) as minimum, then this parent becomes the tree node if not before and a parent node for N. c.
Always this above shortest path is updated and a tree node can become a non tree node (with can become tree node as its status) d.
Whenever a link failure happens, the above algorithm is continuously updated.
A route with the minimum energy consumption is always selected to send a packet between sink and a particular node.
Periodically sink changes its position so that the tree nodes nearby it don't drain out. Sink finds the region of nodes having more average battery power and moves there. Moving sink periodically ensures the overall network lifetime is increased.

Increasing network lifetime by reducing node failures and reconstruction in WSNs
Another backbone construction algorithm has been proposed which increases overall network lifetime. In this a child node can select one from multiple tree nodes to forward data to sink. In existing VB construction mechanism best tree node was picked to be its parent. But when the node sends many messages frequently, the tree node's energy can be drained quickly. Though there are many other tree nodes as it chooses its parent which is best tree node, the energy of its parent is drained. To avoid this situation, this construction mechanism has been proposed.
Nodes which can be tree nodes are initially picked if it has energy greater than the threshold. Every node has a fitness factor with respect to another node based on the distance, energy of the node and the angle between the nodes.
Fitness factor f i (node n) is the fitness factor of node i with respect to the node n. (1) where c 1 +c 2 +c 3 =1. f d is the inverse of distance between node i and n. f e is the energy of node n.
, where β is the angle between the two nodes. It must be kept straight to ensure better fitness factor.
Every node can send the data to sink through any one of the tree nodes. Let , , … to indicate which one of the immediate tree nodes(totally k nodes from 0…k-1 ) to be selected to send the data to sink. Thus would be 1 if the node node 0 is selected to send the data. Likewise would be 1 if the node p is selected to send the data where p<k. The maximum number of child nodes which can choose a tree node to send its data must be minimized to ensure increase in overall network lifetime. If a particular node with higher fitness factor is used to send the data to sink by many nodes, then it is prone to failure as the energy would be drained alarmingly. Let count(i) denote the number of child nodes select the tree node i to send its data. Let be the maximum number of nodes which select any tree node i . Our aim is to minimize mc.
For each tree node T which can be selected by any child node to send their data, } One can state the problem as, (3) (4) The objective is to minimize mc (2).(3) ensures the packet is sent to only one of the tree node and can be different for each node i .(5) ensures at most mc nodes send through tree node T. One of the is 1, but choosing this becomes difficult. A node with respect to another node can be judged based on the fitness factor.
In figure 2, with respect to node N 7 , f i (N 4 )=0.58 and f i (N 5 )=0.62. Now for the node N 7 to communicate with the sink it must select either one of Node N 4 or N 5. Instead of permanently selecting one of the tree node it is done in the following way. Suppose N5 is selected, it is having access via two tree nodes N2 and N3. Now again it takes the route path in any of the possibilities with probability of taking be and respectively. Independently for each node i which needs to send one of a tree node T out of k tree nodes, Now to select a tree node T to send one can select random number R between 0 and 1. If , then data is sent to tree node 0 out of k tree nodes. If , then data is sent to tree node 1 out of k tree nodes.
Similarly tree node is chosen to send to the message.
Expectation of number of nodes which chooses tree node i is calculated in (7),(8), (9) and (10). One can apply in markov and chebbyshev's inequalities which guarantee that in any distribution, nearly all values are close to the mean. All upstream links through the tree nodes based on the fitness factor with respect to the other node to which it communicates. Probability of choosing to send via a particular tree node is directly proportional to its fitness factor. Though one can choose any path, there is a higher chance of taking the path via the node which has highest fitness factor. Here in this algorithm one tries to use as many links as possible. Suppose one always concentrates on one path, the energy level of particular node which is elected as a tree node get depleted. By using only one particular tree node to communicate always one can reduce energy consumption. But sooner than later its energy gets drained out by sending too many packets, link can get busy which can lead to overloading the particular node. When there is a failure of this node the tree gets broken and it is tough to reconstruct as more nodes use this as their parent. This node has every possibility to become a permanent non tree node soon. By using this scheme overloading of particular tree node is avoided and depending upon the capacity(fitness factor) of a tree node it is allotted packets to be sent.

Construction of backbone in MMEVBT
Here a tree node initiated scheme from the sink for the minimal energy consumption is discussed. Initially all nodes with energy ≥ Th act as a non tree node but it can become tree node if a child node elects it. If node's energy < Th, it becomes non tree permanently.
First nodes which can sense sink in their range finds the energy consumption from the node to sink (direct transfer). The other nodes find the energy consumption from it to the node n ( if node n is in its sensing range) which already has direct access to sink. Say a node k has several nodes which has direct access to sink in its sensing range. It selects the node with which it has minimum E(k,n) + Consumption(n) value. The node k elects the node n to be a tree node. Note node n must have energy greater than the threshold. Consumption of node k is defined as, The same process is repeated for all nodes. Nodes elect a node as a tree node if it already has a path to the sink and also it must have the minimum E(k,n) + Consumption(n). Here minimal energy consumption is ensured for any packet sent from a particular node to the sink and vice versa by making child nodes electing the necessary tree nodes.
Simulation is done in NS2. In figure 3, for each sensing range all the three algorithms are made to run with the same random deployment of nodes. The average number of tree nodes is calculated through 15 successful formation of single virtual backbone tree in each sensing range. For d=20 m, no single virtual backbone tree could be formed after several attempts. For d=25m, 15 successful single VBT was captured after 23 failures. For d=30m and 35m, 3 and 1 failures occurred respectively.

VBT with Minimal Tree Nodes
Initially node with highest reachability is picked. Nodes within its sensing range are covered. Covered i with value 1 and 2 indicates it covered and it is a tree node respectively. Next in the nodes which are covered, one finds the node which has maximum number of reachable nodes in |Total nodes -Covered nodes|. Such a node is made a tree node. This process goes on till all nodes are covered.  Energy(k,n) Energy consumed in node k when trying to send a packet to node n.
Fi(n) Fitness factor of node I with respect to node n Table 1. Notations used in the paper

CONCLUSION
In this paper virtual backbone algorithm with minimum energy consumption has been discussed. This algorithm ensures always most minimal energy is always consumed when a message is sent from any node to the sink. Another algorithm which increases the network lifetime has been discussed. This is not deterministic algorithm. The expected number of nodes which chooses a particular node to forward the data is calculated and number of messages passing through a node is minimized.


text:
Vertical Clustering of 3D Elliptical Helical Data

This research proposes an effective vertical clustering strategy of 3D data in an elliptical helical shape based on 2D geometry. The clustering object is an elliptical cross-sectioned metal pipe which is been bended in to an elliptical helical shape which is used in wearable muscle support designing for welfare industry. The aim of this proposed method is to maximize the vertical clustering (vertical partitioning) ability of surface data in order to run the product evaluation process addressed in research [2]. The experiment results prove that the proposed method outperforms the existing threshold no of clusters that preserves the vertical shape than applying the conventional 3D data. This research also proposes a new product testing strategy that provides the flexibility in computer aided testing by not restricting the sequence depending measurements which apply weight on measuring process. The clustering algorithms used for the experiments in this research are self-organizing map (SOM) and K-medoids.

I. INTRODUCTION
Computer Aided Testings of geometrically complicated shapes is very challenging task in many manufacturing fields. The resent development of 3D scanning and 3D printing brings definite advantages to industry. On the other hand rapid development on scanning precision brings too much excessive data for analysing process which slows down computation process. The effective combination of existing computer science knowledge is expected to reduce this overhead and contribute toward integrity to a certain degree. Our contribution is in machatronics for welfare industry.
In this paper we propose a novel vertical data clustering strategy. This method will be used as a pre-process to welfare product evaluation model originally described in figure 5 of research [2], which is cited in this paper as cross section-wise product evaluation procedure in figure 2. We propose that this 3D vertical clustering method could be used in other research areas as well. Research [1] briefly describes the overall machining project.
Self-organizing map (SOM) is a popular type of artificial neural networks (ANN), first introduced by Finnish professor Teuvo Kohonen. SOM is using unsupervised learning to produce low dimensional outputs, in other words maps. This method is very useful as a clustering algorithm to address nonlinear data as this algorithm clusters equally distanced data into same cluster. A successful example of SOM is described in [4].
K-medoids is an efficient clustering algorithm originally proposed by Leonard Kaufman and Peter J. Rousseeuw in 1987 as described in [3]. k-medoids is known to be robust to noise and outliers over famous k-means as it minimizes a sum of pair wise dissimilarities instead of a sum of squared Euclidean distances. The term medoid here can be explained as the object of a cluster, whose average dissimilarity to all the objects in the cluster is minimal, i.e. cluster centers are centrally located either one of clustering data. In order to proceed with the cross section-wise product evaluation for surface data as illustrated in figure 2, the resulting vertical clusters are expected to be as slim as possible.
In the following sections of this paper we address this vertical clustering in details and the relevant threshold values. The threshold number denotes here as the number of maximum clusters that preserves the resulting shape to be vertical, and with exceeding which the shape is not vertical anymore. However this number is not in absolute precision, rather rough evaluation measure due to the fact that results of clustering slightly improve with recursive trainings. ISSN: 2231-2803 http://www.ijcttjournal.org Page 100 II. CLUSTERING WITH 3D DATA The following figures illustrate clustering results using 3D data for SOM and K-medoids algorithms. Figure 3 illustrates the K-medoids clustering preserves the vertical feature roughly in a 15 group clustering. Figure 4 illustrates the 20 group clustering for K-medoids. This means the threshold is between 15 to 20 groups. In figures 3, 4 and 5 "group no:number of members" is added to explain quality of clustering. SOM usually produce similarity than K-medoids.
SOM is able to manage and return 23 groups that vertical features are preserved in an expected number is originally set to be of 25, where 2 groups were empty. This allows us to assume the threshold to be roughly 23, which slightly better than K-medoids. But trainings of SOM are computationally expensive task. Figure 5 illustrates SOM 23 groups.  It should be mentioned that the above experiments were performed using single turned elliptical helix to avoid confusion. Therefore it is stated that a turn-wise split is a prerequisite even in the following alternative method. The following figure 6 illustrates this turn-wise split.
ISSN: 2231-2803 http://www.ijcttjournal.org Page 101 Figure 6. Turn-wise split of helix before clustering III. PROPOSED METHOD To achieve higher threshold value and prepare data for cross section-wise product evaluation procedure, we propose the following new strategy as illustrated in following figure 7. This method brings two options to proceed with. The former denotes sequence depending scanning and latter denotes flexible scanning. Both will be explained in following sections.
Due to technical merit we adopt the flexible scanning method which requires 3D vertical clustering which is more precise than in previous section follows by data isolation.
IV. SEQUENCE DEPENDING SCANNING Sequence depending scanning assumed that number of measurement around a certain cross-section of the surface to be a constant as illustrated in figure 8. The advantage of this method is easiness of labeling each cross-section as a single group. This avoids the problem of vertical clustering and relevant cluster accuracy issue. How ever this applies measuring restrictions, i.e. user has to make sure that the number of measurement is always constant. Further this method is quite impracticable for asynchronous scanning methods. Many ongoing 3D scannings developments are asynchronous, as the scanning are done on one at a time basis followed by a later on merging several scanned images to combine into a 3D model.
Since this is quite straightforward method for rest of computation process as with a known data group programmer only has to mask the data and isolate it. Hence during this paper this method is considered as less important method, but not denies the validity.
V. FLEXIBLE SCANNING For a more generalized platform and as a good research problem it can be considered that scanning is done asynchronously and the number of data on a cross-section is not certain. In this case some sort of a clustering is the option to proceed with and clustering accuracy will become an issue.
In our case we need our data groups to be in isolated slim surfaces as illustrated in figure 1, i.e. vertical clustering. We propose use of 2D data (X and Y data only) for clustering, followed by merge the resulting clusters to original 3D data and proceed to data isolation process. This proposed method is illustrated in the following  With the above results it can be stated that vertical clustering ability is improved as threshold values shown in following table 1. Although the upper limit of above threshold numbers is still unknown due to slow development process, it can be stated that there is a definite improvement using the new strategy.

VI. CONCLUSIONS
The preliminary 3D oriented clustering experiments shows that SOM works better than K-medoids in preserving the vertical shape in clustering with higher threshold number, but met with limitations to proceed with due to excessive information related to Z axis.
With the proposed strategy of using 2D data for clustering and then merge the clusters to original 3D data proved to increase the vertical clustering ability as current thresholds recorded to be of 72 (means 5 degree interval).
It could be stated that further improvement is theoretically possible, but development with SOM is too slow. Also the actual product is also still due.