extfieldsofstudy:
Computer Science
Mathematics

text:
Lossless Size Reduction for Integer Least Squares with Application to Sphere Decoding

Minimum achievable complexity (MAC) for a maximum likelihood (ML) performance-achieving detection algorithm is derived. Using the derived MAC, we prove that the conventional sphere decoding (SD) algorithms suffer from an inherent weakness at low SNRs. To find a solution for the low SNR deficiency, we analyze the effect of zero-forcing (ZF) and minimum mean square error (MMSE) detected symbols on the MAC and demonstrate that although they both improve the SD algorithm in terms of the computational complexity, the MMSE point has a vital difference at low SNRs. By exploiting the information provided by the MMSE method, we prove the existence of a lossless size reduction which can be interpreted as the feasibility of a detection method which is capable of detecting the ML symbol without visiting any nodes at low and high SNRs. We also propose a lossless size reduction-aided detection method which achieves the promised complexity bounds marginally and reduces the overall computational complexity significantly, while obtaining the ML performance. The theoretical analysis is corroborated with numerical simulations.

I. INTRODUCTION
W HEN the transmitted symbols are from a finite set, the problem of optimal detection is an integer least-squares (ILS) problem. It arises in many applications such as code division multiple access (CDMA) systems [1], Vertical Bell Labs Layered Space-Time (V-BLAST) structure [2], linear dispersion space-time block coding (LD-STBC) [3] and generalized spatial modulation (GSM) schemes [4] to name just a few most frequent and established applications. The maximum likelihood (ML) detector results in an optimum solution of the ILS problem. However, the ML detection problem can be solved by a brute-force search which is computationally infeasible [5]. Thus, sphere-decoding (SD) was proposed as an efficient tree-search based method to obtain the ML solution [6]. Unlike the brute force search, the SD algorithm searches over the lattice points that lie within a hyper sphere of radius R around the received signal. The SD algorithm was first introduced by Fincke and Pohst (FP) in [7]. Later, a more efficient variation of the SD algorithm known as Schnor-Euchner (SE) refinement was presented in [8]. Based on FP and SE algorithms, two improvements of these variations of the SD algorithm were proposed in [9], and shown to offer a M. Neinavaie  computational complexity reduction compared to the SE and FP variations.
The computational complexity of the SD algorithm was studied in [10]- [12]. In [10] and [11], the expected number of operations required by the algorithm was derived over the Rayleigh fading channel, realization of the noise and transmitted symbols. It was shown that the expected complexity has a polynomial behavior at a wide range of signal-to-noise ratios (SNRs). Contrasted with this claim, the main result of [12] is that the expected complexity of the SD is exponential for a fixed SNR, and the complexity exponent behavior shows that the SD algorithm is not efficient for the systems which operate under low-SNR conditions or have a large size. In [13], the complexity distribution for random infinite lattices for the SD algorithm was also analyzed. With a focus on the spacetime codes (STC) and diversity-multiplexing tradeoff (DMT) optimality, the minimum complexity for the SD algorithm, which achieves a vanishing gap to the ML performance at high SNRs, was derived in [14]. This minimum complexity is described via introducing the SD complexity exponent. Aiming for reducing the computational complexity, there are a number of other variants of the SD algorithm which can be divided according to the error performance into optimal and suboptimal SD algorithms [15]- [23].
At the opposite extreme, linear detection (LD) schemes including the zero-forcing (ZF) and minimum mean square error (MMSE), perform linear operations which incur a much lower complexity compared to the SD algorithm [5]. This polynomial complexity comes at the cost of a dramatic performance loss [24]. As an example of auxiliary/initial, low cost information, the LD method sometimes results in a reduced search space for the SD algorithm [25]- [28]. Most of these schemes achieve either a sub-optimal performance to reduce the computational complexity, e.g., [27], or have exponential computational complexity to achieve the ML performance, e.g., [29]. In [30], an ML performance-achieving method which is as complex as the ZF method with probability one, at high SNRs was proposed. In other words, at a high SNR regime, this method meets both complexity and performance extremes with probability one. However, this method does not achieve the optimal performance at a low SNR regime and only operates in a V-BLAST system with the Rayleigh fading channel.
A fundamental question for SD algorithms is the minimum possible search space to achieve the optimal ML performance when auxiliary low cost information, such as the detected symbol by the LD method or an initial radius, is available. In this paper, we address this question by presenting the minimum achievable complexity (MAC) of an SD algorithm. Moreover, the exponential behavior of the SD algorithm at low SNRs and large number of input symbols is, arguably, the most significant drawbacks of SD algorithm [12]. In this paper, theoretical study and possible solutions to overcome these drawbacks are given.

A. Main Contributions
1) Using the law of large numbers, we obtain the minimum feasible complexity, i.e., MAC of the SD algorithm for a given set of initial information. This set may solely contain the classic initial information of the conventional SD algorithms, e.g., the initial radius and the channel matrix, or it may involve more information, such as the initial point detected by an LD method, hereafter denoted by s LD . This complexity bound can be used as a bench mark to determine how well a particular SD algorithm exploits the initial information. The proposed complexity bound, MAC, is distinct from the complexity exponent in [14] in some important respects. Unlike the complexity exponent, which only considers the high SNR optimal performance achieving SD, the MAC is the minimum complexity bound for the SD algorithms which achieve the exact ML performance at all SNRs. Moreover, our bound describes the complexity behavior in a more general sense. Indeed, it is not limited to a specific setting or a type of fading channel.
2) The proposed MAC reveals an inherent limitation of some conventional SD algorithms at a low SNR regime. More precisely, we prove that the results obtained in [12] about the weakness of the SD algorithm at small SNRs are natural and the auxiliary information of these SD algorithms is not effective at low SNRs.
3) Although, the size reduction notion, in the sense that SD algorithms can search over a reduced search space with a performance loss, already exists in the literature, e.g., [27], it is in this paper that the concept of a lossless size reduction in SD algorithms is introduced as the capability of reducing the effective size without any performance loss. Along with introducing the concept of a lossless size reduction, the derived MAC allows us to prove that by adding appropriate low cost auxiliary information, a solution for the low SNR deficiency problem of conventional SD algorithms is attainable. Specifically, we show that, unlike the ZF detected symbol, adding the MMSE detected symbol to the information set helps to overcome the weakness of conventional SD algorithms at low SNRs.
4) In addition to capabilities and bounds, an ML performance-achieving SD algorithm which follows the lossless size reduction concept is proposed. We prove that this algorithm intelligently deploys the initial information to reduce the effective problem size without any performance loss. It is also capable of operating under any type of fading channels. By defining marginal optimality as achieving the optimal error performance without any tree-search at low and high SNRs, we prove that the proposed algorithm is marginally optimal. The distinct characteristics of the proposed algorithm which, to the best of our knowledge, are not met in any other SD algorithms are as follows: providing a lossless size reduction, i.e., reducing the effective size while being optimal in the sense of error performance; an exemption from the tree-search at a range of SNRs, especially low SNRs.
The remainder of the paper is organized as follows. After reviewing the basic SD algorithm and its computational complexity in Section II, we derive the MAC of SD algorithms in Section III. We present the lossless size reduction concept in Section IV and propose the marginally optimal SD algorithm in Section V. Section VI explores the validity of theoretical results via simulations. Finally, Section VII concludes the paper.

B. Notations
Throughout the paper boldface small letters denote vectors and boldface capital letters denote matrices. A superscript (·) T denotes the transpose of a matrix, |x| stands for the absolute value of x and x stands for the Euclidean norm, [X] mn denotes the element in the mth row and the nth column of matrix X and [x] i is the ith element of vector x. The probability of event A is denoted as P(A). Mathematical expectation of X over variable Y is denoted by E Y {X}, while f (X) is the probability density function (pdf) of the random variable X and f (X|Y ) is the conditional pdf of the random variable X given Y . We also use the notation= to denote the asymptotic exponential equality, i.e., f (ρ)=g(ρ) means that lim log ρ . Finally, C denotes the field of complex numbers and |S| is the cardinality of set S.

Consider the system model
where H is the L × K channel matrix, the K × 1 vector s ∈ C K consists of the information symbols drawn from an arbitrary M -ary quadrature amplitude modulation (QAM) or pulse amplitude modulation (PAM) constellation, y denotes the L × 1 received vector, and n is the independent and identically distributed (i.i.d.) additive complex Gaussian noise with variance σ 2 , and the SNR is defined as ρ 1 σ 2 . The channel H is general enough to capture a number of applications such as, uncoded V-BLAST and STC MIMO systems, precoded orthogonal frequency-division multiplexing (OFDM) systems [31], and multiuser systems [32].
The ML solution for the information symbol decoding is which is the closest lattice point search problem. Unlike the brute-force ML detector, the SD algorithm reduces the computational complexity by searching over the lattice points inside a sphere with radius R. The essence of any SD-based method is the FP algorithm and its refinements, such as the SE enumeration [6]. The computational complexity of the SD algorithm is a function of the number of visited nodes in the tree-search [10]. In this paper, as in [12] and [13], we consider the number of visited nodes itself as the complexity measure. The number of visited nodes in the SD algorithm is equal to the sum of visited lattice points at the kth layer, k = 1, . . . , K. If we denote the number of lattices, in a k dimensional hypersphere with radius R, by N k , the number of visited nodes of the SD algorithm is [13] where N k = s k ∈ C k ỹ k − R k s k 2 ≤ R . Indeed, N k depends on the information set, denoted by I, which is fed to the algorithm. This initial information is mostly embedded in the preprocessing stage and the initial choice of R. The preprocessing stage is comprised of the QR decomposition of the channel matrix H, and for some variants of the SD algorithm, also an LD detected symbol, e.g., the ZF or MMSE points, and sometimes an ordering stage. The ordering can be a natural back-substitution or a more sophisticated one which is topically based on the channel matrix realization H. For example, see the ordering algorithms in [9]. For the initial radius R, the two most well-known choices are latticeindependent and lattice-dependent radii [13]. The FP variant of the SD method primarily adopts a lattice-independent radius, and the SE refinement is a lattice-dependent based SD algorithm. A powerful choice for a lattice-independent radius is proposed in [10,Section 4]. The information set for the SD algorithm presented in [10] is the channel matrix and an initial radius, i.e., I li = {H, R H }. The initial radius presented in [10], denoted by R H , guarantees the existence of at least one lattice point inside the sphere with a high probability. In the lattice-dependent variants of the SD algorithm, such as the SE refinement, the provided information set is I ld = {H, R B }, where R B is the initial lattice-dependent radius obtained by R B = y − Hs B 2 , and s B is the Babai point or the zero forcing-decision feedback (ZF-DF) estimate [8].
It is worth mentioning that the ZF-DF point can be modified to the other points, such as the MMSE detected symbol. Intuitively, the more information the additional point gives us about the ML detected symbol, the more effective the initial information set becomes. Therefore, if we add a point which is very likely to be the ML detected symbol, the set I plays a more important role in reducing the computational complexity. Nevertheless, this additional auxiliary point should not impose a high computational complexity to the SD algorithm itself. This is the reason that traditional SD algorithms commonly deploy LD methods which incur an acceptably low, often polynomial, complexity.

III. MAC IN AN SD ALGORITHM
As it was mentioned previously, the initial information, I, can potentially reduce the computational complexity of the SD algorithm. In other words, the initial information may make it unnecessary to search over all the lattice points inside the sphere. As an extreme example, assume that I = {s B } and we know that s B is the ML detected symbol with probability one. Therefore, we lose nothing, with probability one, if we only visit the nodes corresponding to s B . Thus, in general, according to this information, some of the lattice points become probable or typical. The typical set, or equivalently, the set of minimum possible lattice points, can be determined using the asymptotic equipartition property (AEP) and the law of large numbers [33]. If the typical set of lattice points is provided, the SD algorithm only needs to perform the search over this set. The typical set concept allows us to obtain the minimum necessary and possible number of lattice points. Then, an algorithm which searches over the typical set is able to find the ML solution with the minimum possible number of visited nodes. Hereafter, this minimum possible number of visited nodes is referred to as the MAC of an SD algorithm which can be interpreted as a complexity bound for an SD algorithm. Achieving this bound for the number of visited nodes is realizable by constructing the typical set and searching over it, and can be considered as a benchmark for how efficient a variant of an SD algorithm is, in terms of computational complexity. By a marginal analysis of this bound, we investigate the inherent drawback of the conventional variants of the SD algorithm which appear primarily at the low SNR regime. The basic difference between this type of analysis and the lower bounds obtained in the literature, for instance [12], should be noticed carefully.
In the SD complexity analysis presented in [12], the lower bounds are derived for a specific SD method and show the limitations of those methods, exclusively, with a certain radius, body search strategy, and preprocessing method. Nonetheless, the MAC, obtained by the law of large numbers, reveals the smallest possible search space for any given variant of the SD algorithm and, therefore, the inherent limitations of the SD algorithm with a given set of information is clarified. Indeed, the MAC is the ultimate potential of an SD algorithm.
To obtain this lower bound, we consider a sequence of N ML search candidates as where s k ML [n] is the k dimensional ML search candidate at the nth time slot. To obtain the possible sequences S k ML or the typical sets, the probability P(s k ML |I) needs to be calculated. By looking at large sequences of these symbols and using the law of large numbers, these probabilities reflect on which possible sequences of the ML search candidates s k ML 's are more likely to happen. As in Shannon's AEP, the set of these probable sequences for a large number of observations N is referred to as the typical set [33]. According to the law of large numbers, if the typical set has to be available, we can find the ML solution by searching over the typical set. We also know that the sequences of the typical set are equiprobable, which means that if we search over a smaller set than the typical set, we will miss s ML with a considerable probability. Therefore, in order to find the ML point, the typical set has to be the minimum sufficient and necessary search space. In the following lemma, we present the MAC, denoted by C min SD , for a given information set I.
Lemma 1: The MAC of a given SD algorithm with the initial information set I is Proof: See Appendix A.
In (5), −E s k ML log P s k ML |I is the entropy of s k ML given the set I. Designing a method which solely searches over the typical set, and hence achieves the MAC, is attainable, yet seems to be a challenging problem. Nonetheless, the MAC can be considered as a computational complexity bench mark. It should be noted that the MAC is only a function of the initial information set, i.e., I. As it was mentioned previously, according to the AEP and for a given initial information set, no matter which radius, body search strategy or preprocessing is adopted, if the number of visited nodes is smaller than C min SD , the ML performance is not achieved.
The following theorem reveals a fundamental low SNR limitation of the conventional SD methods with latticeindependent and lattice-dependent radii. It should be noted that in the proofs concerning the lattice-independent radii, we have considered an FP method with the lattice-independent radius in [10] which is also adopted as the radius of the SD algorithm in many other FP algorithms, e.g., [13]. Also, for the lattice-dependent based SD algorithm, we have considered an SD method which applies the lattice-dependent radius R B = y − Hs LD 2 . Moreover, regimes with ρ → 0 and ρ → ∞ are sometimes referred to as the low and high SNR regimes, respectively.

Theorem 1:
The MAC of a lattice-independent and latticedependent conventional SD algorithm satisfies the following inequality C min SD ≥ 2 2 K − 1 , at low SNRs and the equality C min SD = K at high SNRs. Proof: In order to calculate C min SD of a lattice-dependent based SD method, at a low SNR regime, we have to find P s k ML |I ld , where I ld = {H, R B } and R B = y − Hs B 2 . Note that at zero SNR, we have y = n and, consequently, where Γ s k ML is the ML decision region, that is Voronoi region, for the symbol s k ML . Using the independence of H and n, we have In [34], it is shown that f (n | n = ν ) = 1 SK δ ( n − ν) where δ(·) is the Dirac delta function and S K = 2π .
For an M -ary modulation scheme, the integral (7) should be calculated over M k Voronoi regions corresponding to each s k ML . In the following, we show that the integral (7) over the Voronoi regions corresponding to s k ML and its rotated versions k ML = Ts k ML both lead to the same result, where the orthogonal matrix T is the rotation matrix.
We have We can change the variable as n = T Hn to get The above equality holds since n = n . Therefore, According to the symmetrical properties of the constellation, each s k ML in each hyperoctant 1 is a rotated version of an s k ML in the first hyperoctant. Thus, according to (10), it is sufficient to solely calculate the integral (7) over the Veronoi regions in the first hyperoctant. For the binary modulation case, we denote the Voronoi region corresponding to the point Therefore, in order to calculate (7), we can change the variable as dn = r k−1 drdΩ to obtain Since, S K is the volume of a K-dimensional hypersphere and for a k dimensional lattice with binary entries, the 2 k possible Voronoi regions have equal volumes, we obtain Consequently, we have lim Therefore, the MAC of a lattice-dependent radius based SD algorithm is lower bounded by Now, we focus on a lattice-independent radius based SD method. The SD presented in [10] considers the FP algorithm, with a proposed radius that tends to infinity as ρ → 0. Therefore, the radius does not contain any information about s ML at low SNRs, or equivalently, I li = {H} and When ρ → 0, we have y = n and using the independence of n and H we have Therefore, since the volume of the Voronoi regions corresponding to inner lattices tends to zero at low SNRs, according to (17), we obtain where the inner and outer sets, correspondingly, are the inner and outer modulation points in the constellation set. Consequently, Consider now the high SNR regime. In a lattice-dependent radius based SD method, the initial radius is R B = y − Hs 2 , and when the SNR tends to infinity, s B = s ML = s, that means that only one point, merely s ML , exists in the sphere, with a probability one. In other words, for the given information set, i.e., I ld = {R B , H}, no uncertainty remains on s ML when the SNR tends to infinity. Therefore, we have −E s k ML log P s k ML |R B = 0 and lim ρ→∞ C min SD = K. On the other hand, the proposed lattice independent radius in [10] is R li = αK ρ , where α is determined such that we find a lattice point inside the sphere with probability 1 − ǫ [10], i.e., where F χ 2 K (·) is the cumulative distribution function (CDF) of a chi-squared random variable and Γ(·) is the gamma function. For instance, if α = √ ρ, at high SNRs, ǫ tends to zero and at the same time R li approaches zero. Therefore, with probability one, only one lattice is inside the sphere at high SNRs which is s ML . Hence, having the information set I which is d li at high SNRs does not leave any uncertainty on s ML and, therefore, −E s k ML log P s k ML |d li = 0. Theorem 1 claims that for the lattice-dependent and independent based variants of the SD algorithm, such as the FP algorithm in [10] and the SE refinement in [9], we have C min SD = K when the SNR tends to infinity. The complexity analysis of the SD in [10] at high SNRs, for the FP algorithm shows that the number of visited nodes of the FP algorithm with the proposed radius tends to K at high SNRs. This means that these methods are effective in the sense that they achieve the minimum possible complexity at high SNRs with the information set I = {H, R li } fed to the SD algorithm.
The main weakness of these methods shows, indeed, at the low SNRs. The weakness of the classic FP and SE algorithms is because of the information fed to these methods which leads to an exponential complexity with respect to the problem size. Analyses of the complexity of the FP based SD algorithm in [12] also shows that this method suffers from a high computational complexity at low SNRs. This theory shows that even if the best body search strategy, preprocessing or ordering techniques are applied to the SD algorithm, for the given lattice-independent and dependent radii, an exponential computational complexity occurs at low SNRs.
Remark 1: Clearly, for an SD algorithm which searches over the lattice points inside a sphere of radius R, the best, yet infeasible, radius which contains merely one lattice point is The proof of Theorem 1 conveys that, even with R ML , the idea of searching inside a sphere leads to an exponential computational complexity at low SNRs. In other words, the initial radius R is ineffective at low SNRs.
A fundamental question arises here: is it possible to unravel this exponential behavior at low SNRs without any performance loss? It is known that, unlike the ZF, the MMSE method declares the ML solution at low SNRs, i.e., s MMSE = s ML , when ρ → 0 [5]. Therefore, there is a prospect of the existence of a method which finds the ML solution at low SNRs without visiting any nodes but just by, intelligently, relying on s MMSE . Theorem 1 claims that, regardless of the fact that s MMSE = s ML at low SNRs, deploying the MMSE detected symbol only as the initial radius will not be successful as far as the computational complexity is concerned. In other words, a lattice-dependent based SD algorithm is not able to benefit from the information provided by the MMSE algorithm perfectly. Indeed, the initial point obtained by the MMSE method, i.e., s MMSE , has more information to be exploited.
Presumably, adding the MMSE detected symbol to the information set I, not only in R B but as a separate initial point, may able to compensate for this exponential behavior of C min SD at low SNRs. Along with the evidence we have for the existence of a lossless method which relies on the s MMSE and, consequently, detects the s ML without visiting any nodes, there is also an expectation of existence of an algorithm which is capable of relying on some or all of the detected symbols of the MMSE method at all SNRs which reduces the overall effective problem size without any performance loss. A method which is capable of relying on some or all of the symbols of the initial point without any performance loss is referred to as a lossless size reduction (LSR) aided method. The concept of an LSR-aided SD is addressed in the next section.

IV. MAC IN A LSR-AIDED SD
The information set of the lattice-independent and dependent algorithms can be enriched by adding a separate initial point to set I. In addition, having this point in the initial information set can be interpreted as a separate processing block in the preprocessing stage which enables obtaining the ML solution without visiting any nodes. The combination of a decoder that comprises this block and an SD algorithm is referred to as an LSR-aided SD algorithm. By partially, or completely, relying on the initial point, e.g., s MMSE , this separate block makes a decision for some, or all, of the transmitted symbols. These symbols are already declared to be detected and do not play any role in the SD search; thus, the problem size is changed. Taking into account the LSR in an SD algorithm, the problem size of the SD algorithm, K, becomes a random variable. This random problem size depends on the number of symbols of the initial point on which the LSR-aided algorithm relies.
Assuming that the effective problem size after applying the LSR reduces to K r , the MAC for a given K r and I LSR is obtained by where I LSR = {H, s B }. Therefore, the MAC for an LSRaided SD is The event when K r = k can be interpreted as relying on K − k of the initial point. For example P(K r = 0) = 1, at a given SNR, implies that we have trusted the initial point entirely, with probability one at that SNR, and consequently, C min SD = 0. Along with considering the optimal error performance, the following definition takes into account the complexity to provide a more general view of the concept of optimality in the class of ML performance achieving algorithms.
Definition 1: An initial information set is said to obey the zero-complexity achievable (ZCA) property at a given SNR, if at that SNR C min LSR = 0, and an SD algorithm which exploits the ZCA property at zero and infinity SNRs, is considered to have the marginal complexity optimality, i.e., achieves the ML performance without visiting any nodes at ρ → 0 and ρ → ∞.
Based on Definition 1, the following lemma analyzes the capability of an information set containing the MMSE or ZF points in terms of ZCA.
Lemma 2: The initial information set corresponding to an MMSE-based LSR algorithm, i.e., I LSR = {s MMSE , H}, is ZCA at ρ = 0 and ρ → ∞ and the information set of a ZFbased LSR, i.e., I LSR = {s MMSE , H}, is only guaranteed to be ZCA at ρ → ∞.
Proof: See Appendix B.
Analyzing the MAC, we have been looking for a low computational complexity point to be added to the information set to compensate for the low SNR weakness. This lemma shows that if we add s MMSE to the information set, i.e., I = {s MMSE , H}, the inherent deficiency of the conventional SD algorithms at low SNRs is resolved. These results are summarized in Table I, and it can be seen that the conventional SD algorithms with lattice-dependent or independent radii, are not able to achieve the ML performance without visiting any nodes at zero and infinity SNRs. On the other hand, an algorithm which is fed with I = {s MMSE , H}, i.e., MMSE based LSR-aided SD, is capable of achieving the ML performance without visiting any nodes at zero and infinity V. A LOSSLESS SIZE REDUCTION-AIDED SD So far, we have described the capabilities of an LSR-aided SD in terms of MAC. More precisely, we have evaluated the effect of adding the initial point s LD to the information set I in Lemma 2. In the detection process, adding this information, can be translated to adopting a separate preprocessing step to determine the status of the symbols of the initial lattice point beforehand. This notion has been considered in some existing works, as an approach to reduce the computational complexity, e.g., [26], [27], and [30]. However, this point of view usually arrives at a sub-optimum, near ML, error performance. By focusing on the LSR property, our aim is to derive a detector which partially or entirely relies on the initial lattice point without a performance loss. From the LSR perspective, achieving the ML performance with a reduced problem size and, even sometimes without visiting any nodes, is feasible. In this section, we propose an LSR-aided SD algorithm.
In the detection problem (2), the equalized vectorỹ can be written asỹ = W p y, where W p is the preprocessing equalization matrix. The joint detection problem can be decoupled into a single detection problem which often has a lower performance compared to the ML detector. The LSRaided SD either relies on the detected symbols of the initial point or preserves the symbol in a set, hereafter denoted by S, to be searched by the SD algorithm.
The kth element ofỹ, is where k = 1, . . . , K. Assuming that E{|[s] k | 2 } = 1, the kth received SNR depends on the underlying LD method. The proposed algorithm uses the instantaneous SNR to assess the reliability of each symbol. For instance, when the ZF equalizer is adopted, then SNR k = ρ [(HH) −1 ] kk , and for the MMSE equalizer, we have In order to perform a lossless size reduction, we need to find the reliable symbols of the initial point. The indices of the reliable detected symbols form a set denoted by G. Indeed, the proposed detection method relies on the detected symbols whose indices are in G, and the rest of the symbols construct the setḠ. In Theorem 2, we determine G such that the proposed method guaranties the ML performance. The set G is constructed as where η k is obtained from the following equation where E k LD and E k ML are the kth symbol error events of the LD and ML detection methods, respectively.
It should be noted that finding η k from (26) is an offline process. Indeed, using (26), a lookup table can be provided to find η k at each SNR. More details about finding η k will be discussed later. The reduced search space is where [s LD ] i = arg min s∈C |[ỹ] i − s| denotes the ith symbol of the initial point s LD .
The following theorem provides the sufficient reduced search space which relies on some or all of the initial point symbols and leads to achieving the exact ML performance.
Theorem 2: An algorithm which relies on the initial point symbols whose indices are in G, and searches over the remaining symbols in the set S , where |S| = M K−|G| , achieves the optimal ML performance.
Proof: In order for the algorithm to achieve the ML performance, η k should be selected such that P ( The kth symbol error probability of the proposed method can be expanded as where D k is defined in (27), s andŝ are the transmitted symbol and the detected symbol by the proposed algorithm, respectively. The first term of the right hand side of (28) can also be expanded as According to the proposed detection method, in the first term on the right hand side of (29), the event Now, we focus on the second term on the right hand side of (29). It should be noted that the event {|D k | = M } means that all the modulation points exist in the set D k and, therefore, the event Note that the proposed algorithm performs the ML search over the set S. The error event in the detection of the kth symbol occurs when all the search candidates, in S, sharing the same kth symbol with the transmitted vector, do not meet the ML minimum distance detection criteria. We denote the set of all vectors sharing the same kth symbol with s by Λ [s] k , that is, It should be noted that we have S ⊆ C K , therefore Next, we focus on the second term on the right hand side of (28). We can write According to the proposed method, joint event Since, the event {|D k | = M } is equivalent to the event SNR k ≤ η k , it follows from (28), (32), (33), and (35) that Therefore, in order to achieve the ML performance it is sufficient to have Since, the kth symbol error probability of the ML detector can be expanded as which are the symbol error events corresponding to the LD and the ML methods, respectively, the sufficient condition for the proposed method to achieve the ML performance is obtained by (26).
We have shown that a threshold which is obtained by (26), guarantees the ML performance. However, in order to prove that the algorithm has the lossless size reduction property, we have to show thatŝ = s ML . It should be noted that the ML decision has the uniqueness property [35]. In other words, an algorithm which achieves the same performance as the ML detector, has also the same decision with probability one, i.e. P(ŝ = s ML ) = 1.
Theorem 2 proposes a fading-type and application independent algorithm. In other words, the derived threshold is general in the sense that it is applicable to different fading types, e.g., Rayleigh, Nakagami, etc, and applications, e.g., coded and uncoded MIMO, OFDM systems, etc. The detection algorithm is summarized in Algorithm 1. It should be noted that regardless of which SD algorithm we use, the lossless size reduction step reduces the overall computational complexity.
As it was mentioned previously finding η k from (26) can be accomplished via a lookup table which is provided off line by Monte Carlo simulations. One way to build the lookup table at a given SNR is to compute the probabilities P E k LD , SNR k > η k and P E k ML , SNR k > η k for different values of η k , and their intersection gives the proposed η k . In the following section we provide a more convenient way to construct the offline lookup table.

A. Constructing the lookup table
In order for a lossless size reduction aided algorithm to achieve the ML performance at a given SNR, it is sufficient to choose an η k , or equivalently η k ρ , which is an answer/root of (26). The smallest root of (26) is, hereafter, denoted by η ⋆ k . It should be noted that at a given ρ, (26) may have multiple roots and an efficient algorithm should choose the smallest η ⋆ k to obtain a lower computational complexity. A trivial answer for (26) is η k ρ = ∞ and, in general, it is not guaranteed that a finite η k ρ exists for all values of ρ. Also, η ⋆ k ρ = ∞, at a given SNR, implies that the initial information is not capable of pruning the search tree at that SNR.
In general, obtaining a closed form solution for (26) may be complicated and depends on the fading type and the adopted LD method. In this section, we provide a general suboptimal answer which is less or equal than the smallest root of (26). Since, η k ρ = ∞ is always a valid answer, it is guaranteed that scaling the suboptimal η k always arrives at a solution for (26). Intuitively, if choose η k ρ larger than η ⋆ k ρ , it means that we have considered more restrictive conditions for relying on an LD detected symbol and, consequently, scaling a suboptimal η k ρ leads to a better performance and a higher computational complexity. By neglecting P ([s ML ] k = [s] k , SNR k < η k ) in (37), we can arrive at the integral (39) In general neglection of this term violates ML achieving property. In other words, the root of (39) is less or equal than η ⋆ k ρ . Yet, since we are seeking a subotimal solutionl, we are not obligated to keep this term. However, later in this section, we show that this term is negligible at high SNR regime and this approximation leads to the ML performance when ρ → ∞. This implies that the root of (39) at ρ → ∞, is We can rewrite the integral in (39) as is the error probability of a detected symbol by the LD method given x k and it is bounded as Using (41) in (39), results in an η k which is smaller than or equal to η ⋆ k . Therefore, it is a suboptimal solution. According to (39), (40) and (41) we can write Denoting the root of the above inequality as η sub k , we have η sub where

B. Marginal Complexity Optimality of an MMSE-based LSRaided SD
As it was mentioned in Section IV, the initial information set of an MMSE based LSR-aided SD, has the ZCA property, i.e., the potential of achieving the ML performance without visiting any nodes at zero and infinity SNRs. Now, we examine the computational complexity of the proposed algorithm to see if the algorithm is marginally optimal, i.e., if it is capable of exploiting the ZCA property. As it was mentioned previously, if a method obeys the marginal complexity optimality, it does not need to tolerate any complexity more than the LD computational complexity at zero and infinity SNRs, and while achieving the ML performance, it does not need to visit any nodes. The following theorem addresses this property for the proposed algorithm.
Theorem 3: The proposed MMSE based LSR-aided SD algorithm is marginally optimal.
Proof: Assume that the effective problem size is K r . If for the proposed method at a given SNR, we can show that P(K r = 0) = 1, then the number of visited nodes becomes zero with probability one at that SNR. In order to prove that the proposed method is marginally optimal, we need to show that P(K r = 0) = 1 at ρ → 0 and ρ → ∞. We have where the last inequality follows from the union bound. Hence, since SNR k = ρx k , the sufficient condition for marginal optimality is Therefore, in order to prove the marginal optimality, it is sufficient to show that for the given η k obtained from (26), we have lim ρ→0,∞ η k ρ = 0. It follows from Appendix B that the events E k ML and E k LD are equivalent when ρ → 0. Therefore, when ρ → 0, (26) holds for all values of η k ρ , including η k ρ = 0. Now, we consider the case when ρ → ∞. It should be noted that (37), similar to (26), results in an ML performance achieving η k . At high SNR regime, for the ML method, we have P ([ where d ML is the diversity gain of the ML method. We show that if η k satisfies where ǫ is an arbitrary small number, then (37) holds. The reason is that if (46) is satisfied, the first term of (37) becomes negligible at high SNR since The conditional symbol error probability of M -ary QAM is [33] where α = 3 M−1 and β = 2 1 − 1 √ M . For linear equalizers, the problem turns into some single symbol detection problem, and for a conditional SNR and channel realization, (49) holds as far as square QAM is adopted. Invoking the fact that Q(·) is a decreasing function of its argument, the upper bound Q( √ y) ≤ 1 2 exp(− y 2 ), holds. Moreover, since Consequently, using (46) and (50) we obtain lim ρ→∞ η k = 2 α ln βρ dML+ǫ , and, therefore, lim ρ→∞ η k ρ = 0. The proposed method is as complex as the MMSE method at zero and infinity SNRs with probability one. However, the theory does not imply that the algorithm deterministically adopts the LD method at these SNRs, and there is always a probability that the proposed method performs as an ML search.

C. High SNR Approximation for the Threshold
A finite η k that is capable of achieving the ML performance and exploiting the ZCA property can be obtained by (37) or (26). Using some approximations, we propose a threshold that can be used in a near ML method that does not need a lookup table. In the simulation section, the approximated method will be shown to have a near ML performance while achieving a very low computational complexity. As it was stated previously, according to (47), the term P ([s ML ] k = [s] k , SNR k < η k ) can be neglected in (37). Therefore, we can write .
Using (52) as an approximation of the solution of (26) will result in a suboptimal performance and a dramatically reduced computational complexity. As it was previously stated, since η k ρ = ∞ is a trivial solution of (26). By scaling η k , we can come arbitrary closer to the ML performance without a lookup table. In the simulation section, we show that scaled η k yields a performance which is very close to that of the ML detector with a significantly lower computational complexity.
VI. SIMULATION RESULTS In this section, we first compare the computational complexity bounds with the actual simulated number of visited nodes FP Algorithm [21] ((a)) Lattice-independet radius  to examine the ZCA property for different methods. Next, we verify the claimed theoretical results on the performance and the computational complexity of the proposed method in two different channels: flat fading Rayleigh MIMO channel and frequency selective channel. In our simulations, we consider [21] as an FP variant and the SE algorithm of [9] as an SE variant of the SD method. The curves of complexity and symbol error probability are plotted versus the total SNR, ρ T Kρ, and the number of transmit antennas.  SD algorithm where R H is the proposed radius in [10] and s B is the Babai point. It can be seen in Figs. 1(a) and 1(b), that at low SNR regime, the MAC of both FP and SE variants of the SD algorithm demonstrates a high computational complexity. It should be noted that the gap between the MAC and the actual number of visited nodes decreases with increase of the SNR. Figs 1(d) and 1(c) depict the behavior of the MAC for an MMSE-based LSR and ZF-based LSR with I = {s MMSE , H} and I = {s ZF , H}, respectively. This behavior confirms the ZCA property of the MMSE-based LSR at low and high SNR regimes. Nonetheless, it can be seen that adding the ZF detected symbol to the information set does not lead to ZCA property at low SNRs. In other words, as it can be seen in Lemma 2, the ZF detected point is not able to resolve the low SNR deficiency of the SD algorithm. This confirms the fact that the ZF-based LSR-aided SD does not obey marginal complexity optimality.

B. Frequency flat Rayleigh Fading MIMO Channel
In this simulation example, the MIMO channels are considered to be i.i.d complex Gaussian with zero mean and unit variance. The performance of the proposed method is evaluated through symbol error probability. The number of visited nodes in the SD algorithm is also calculated in order to compare the complexity of the proposed method with that of some other detection methods.
In Fig. 2, a MIMO system with six transmit and receive antennas and 4-ary QAM is considered, and it can be seen that the proposed method achieves the ML performance. The same configuration is considered in Fig. 3, to compare the complexity of the proposed method with that of the SD algorithm presented in [21] with R H . For comparison, the performance and the computational complexity of the widely linear SD in [23] is also plotted. It can be seen that the proposed algorithm achieves a lower complexity and, unlike the other SD algorithms, is as complex as the MMSE algorithm at low and high SNRs. This result corroborates our claims in Theorems 2 and 3, which means that the proposed algorithm achieves the ML performance at all SNRs and exploits the ZCA property. Moreover, it can be seen that the approximate threshold proposed in (52), with a scaling factor of two, also leads to a performance which is very close to that of the ML detector. It also demonstrates a significantly lower computational complexity. The same results can be observed from Figs. 4 and 5 for 64-ary QAM and four receive and transmit antennas. It can be seen that the performance threshold proposed in (52) is very close to the ML detector while achieving a significantly lower computational complexity.
Figs 6(a)-6(b) and 6(c) demonstrate the effect of increasing the number of antennas on the complexity of the MMSE based LSR-SD algorithm for ρ T = −5, 15, and 25. It can be observed that the LSR in the MMSE based LSR-SD compensates the SD algorithm for its high computational complexity, especially at low SNRs. Although at high SNRs, the SD algorithm has almost a linear complexity increase with the number of antennas, the MMSE-based LSR-SD leads to a dramatic complexity decrease.

C. Frequency Selective Channel
To evaluate the performance of the MMSE based LSR-SD algorithm in another application, in this simulation example, we consider a wireless point to point frequency selective channel with Rayleigh fading. The L c channel coefficients h = [h 0 . . . , h Lc−1 ] are i.i.d distributed with zero mean and unit variance. The channel input-output model is where the additive noise w[n] is i.i.d with zero mean and variance σ 2 . The transmission scheme is considered to be single carrier zero padding (ZP) block transmission [36]. One can reformulate (53) as the system model (1) [36]. In this example, the number of channel coeficients is considered to be L c = 7, the transmit vector lengths is K = 8, and consequently, the receive vector length is L = K + L c − 1. Fig. 7 demonstrates the symbol error probability for a single carrier ZP system which adopts 16-QAM as the modulation scheme. Similar to other simulation examples, it is observed that the proposed algorithm achieves ML performance and outperforms the ZF detector. Also, the approximated threshold (52), with a scaling factor of two, achieves a very close to ML performance. In Fig. 8, we compare the complexity of the proposed scheme with other simulated schemes in terms of the number of visited nodes in the reduced SD method. It can be observed that the MMSE-based LSR-SD algorithm reduces the number of visited nodes in comparison with the SD algorithm and exploits the ZCA property. Moreover, the approximated threshold (52) leads to a significantly low computational complexity.

VII. CONCLUSION
Using the law of large numbers, the minimum achievable complexity has been derived for any arbitrary SD algorithm with a set of auxiliary information. The theoretical reason for a fundamental flaw of the conventional SD algorithms at low SNRs has been analyzed. The lossless size reduction concept has been introduced as a potential solution to the low SNR deficiency of conventional SD algorithms. An ML performance-achieving method which is marginally optimal in the sense of computational complexity has been driven. Along with achieving the exact ML performance and being marginally optimal, the proposed method has been shown to reduce the computational complexity by performing a lossless search over a reduced search space.
where s k ML [n] is the k dimensional ML search candidate at the nth time slot. In order to obtain the possible sequences According to Shannon's AEP, for a given I, the number of typical k dimensional lattice points is M −Es ML {log M P(s k ML |I)} . Therefore, the number of typical k dimensional lattices is obtained as E I M −Es ML {log M P(s k ML |I)} . It should be noted that |T k | is the number of typical k dimensional lattices at the kth stage of the SD algorithm. Hence, the MAC of an SD algorithm given the information set I is According to (60) and according to (23)  Since for a fading channel, this event occurs with zero probability, a ZF based LSR-aided SD is not guaranteed to be ZCA at ρ = 0. Now we consider the high SNR regime. Using the fact that lim ρ→∞ P(s ML = s MMSE ) = 1, we have P(K r = 0) = 1, and according to (23), we obtain lim ρ→∞ C min LSR = 0.


extfieldsofstudy:
Computer Science
Medicine

s2fieldsofstudy:
Computer Science
Medicine

text:
Collaborative and secure transmission of medical data applied to mobile healthcare

Purpose We propose a collaborative and secure transmission scheme in order to safely and efficiently transmit medical data and provide telemedicine services, lighten the load on wireless access networks, and improve the quality of medical treatment such as surgery. Methods First, the transmission technology based on opportunistic networks is used to upload patient physiological data and share medical information. Second, we propose a trusted transfer scheme based on the circle of friends, which is constructed with historical encounters and social features of nodes. This scheme takes the forwarding policy of each packet by close friends to effectively prevent the participation of strangers, and avoid privacy issues and deal with selfish behaviors. At the same time, the structure of friend circle is beneficial to the improvement of medical data transmission. Third, we present a lossless compression scheme with less computation and higher compression ratio to reduce the amount of medical data and improve the performance of the transmission. Results The experimental results show that the proposed scheme is effective and has good transmission performance while ensuring the safety and reliability of media data. Conclusion The mobile healthcare faces some challenges such as the vastness of medical data and sensitivity of patient information. Using opportunistic networks to transmit medical data in mobile healthcare is a good solution, which can effectively divert and offload the data traffic of mobile Internet. The structure of friend circles and the technology of data compression are beneficial to safely and efficiently transmit the patient’s physiological parameters and medical health information.

Alleviating the difficulty of getting medical treatment, reducing medical costs, improving the level of diagnosis and treatment, and promoting health and disease prevention, mHealth has become a hot topic in academia and industry recently [1]. In China, from the perspective of market size, there was about 2.95 billion yuan in 2014 and increased by 44.7% to 4.27 billion yuan in 2015, as shown in Fig. 1a. From the aspect of user size, they reached 72 million in 2014 and 138 million in 2015. In addition, there are more than 2000 mHealth platforms.
However, mHealth faces the following problems in the application. First, it is regarding how to process the massive medical data. The diagnosis and treatment of patients will generate a lot of information, including their personal information, past medical history, examination items, hospitalization records, and discharge records. According to the statistics of the second Xiangya hospital of the Central South University, each patient undergoing PET-CT examination will produce about 300 images, a total of about 1 GB of data. Unfortunately, massive images and videos generated by mobile intelligent terminals have overwhelmed the current mobile Internet, and their rapid growth rate has far exceeded the speed of the expansion of mobile Internet bandwidth [2]. The yearbook report of Cisco also shows that video data account for more than 85% of the data traffic of the entire mobile Internet in 2018 [3]. Second, it expresses concerns about the patient privacy and data security. Mobile healthcare is highly dependent on network and information technology, and it is difficult to ensure the security of patients' personal information and medical information. In the process of data transmission, data anomalies and leakage problems will be caused by the external malicious interference. In the interview, 25% interviewees expressed concerns about patient privacy and data security. It can be seen that the privacy and security of data are the focus and difficulty for both patients and medical workers.
Therefore, mHealth needs a secure and efficient data transmission technology. The opportunistic networks (OppNets) do not need a complete connecting path between nodes. It uses the encounter opportunity formed by node movement to realize communication in the scheme of "store-carrying-forward, " which has many advantages such as flexible networking, rapid expansion, and distributed control [4]. In particular, with the development of communication technology in recent years, mobile intelligent terminals have been rapidly popularized. Using these devices to network, OppNets can realize conveniently, quickly, and efficiently the sharing of content, resources, and services. The emergence of OppNets promotes the process of free communication in medical data sharing environment, expands the use range of network, and is an important part of ubiquitous communication in the future [5]. In this paper, the OppNets is used to transmit medical data in mHealth applications. To improve the performance of transmission, and avoid the privacy issue and the selfish behavior of nodes, we propose a novel trust transmission scheme based on friend circles in OppNets for mHealth. This scheme utilizes the historical contacts and social character of nodes to construct the friend circles in order to create a collaborative and secure transmission environment, and selects a node as the relay only if it satisfies the following conditions: it is within the friend circles of the source node, and has more opportunity to access the destination node. By forwarding each packet via friends, this mechanism can prevent the strangers from participating in the transmission, and avoid significantly privacy issues and the selfish behavior. At the same time, it has high transmission performance because of the structure of friend circles.
The contributions of this paper mainly include the following items. (1) To lessen the cost pressure on users and also lighten the load on wireless access networks, we introduce OppNets into mHealth systems. (2) To achieve higher transmission performance and deal with the selfishness and privacy issues, we propose a collaborative and secure medical data transmission scheme based on friend circles. (3) To reduce the amount of medical data in the transmission, we propose a lossless compression scheme with less computation and higher compression ratio.

Related work
Mobile healthcare based on medical data communication technology and intelligent terminal has become a new telemedicine mode, and it has moved from a concept to a reality which its application extends to every field of medical treatment [6]. Doukas et al. [7] present a mHealth system by means of Cloud Computing. In [8], a mHealth service system is introduced by means of RFID technology and mobile devices. David et al. [9] present mHealth applications and discuss possible challenges facing the development of mobile applications. Baig et al. [10] analyze the critical issues and challenges related to security and privacy of data in mobile phone-based sensor applications of mHealth. Rongxing et al. [11] introduce a secure and privacy-preserving framework based on a new access control and privacy-preserving technique. Kumar et al. [12] propose a novel solution of security of private data transmission. Rahman et al. [13] discuss the security scheme to prevent the attack of wireless communications in mHealth systems. Azzedine et al. [14] propose a secure multicast strategy to only permit trustworthy nodes to take part in communications. AlMuhtadi et al. [15] propose an emergency call mechanism with a view to preserving personal privacy. Kuan et al. [16] present many secure and privacy-preserving strategies in mHealth.
OppNets is ubiquitous because of the use of mobile smart terminals, and has the characteristics of node mobile and self-organization, which helps to have a good application prospect in various normal and nonnormal scenarios and attract the attention of the domestic and foreign academic circles. First, many transmission algorithms are proposed to improve the performance of OppNets. Vahdat et al. [17] propose a floodingbased Epidemic algorithm with the highest transmission success rate and lowest latency. Lindgren et al. [18] use the historical encounters to present a predictive transmission algorithm PRoPHET. Hui et al. [19] propose the BUBBLE algorithm which uses the community structure to forward the data packet. Wenrui et al. [20] propose the ferrying mechanism to deliver the message by the ferry node. Second, some trust transmission methods are proposed to deal with the selfishness and privacy issues. In addition, many routing algorithms based on other characteristics of nodes are proposed, such as the relationship [21], interest [22], context aware [23], Big Data [24][25][26][27], IoMT [28,29], etc. Na et al. [30] selected the appropriate node to forward messages by counting the number of feedbacks to measure the trust values of node based on the "watchdog" mechanism.
In [31], the selfish nodes were bypassed according to the trust values of node which can be evaluated through the number of historical encounters. In [32], the trust metric of each node was the number of hops from it to the destination on forwarding path, and the data were forwarded sequentially from the lower trust nodes to the higher trust nodes. Trifunovic et al. [33] proposed an OppNets trust model according to social trust which was evaluated by the relationship between nodes, and it was established by the network topology and the number of hop. Xi et al. [34] proposed a forwarding algorithm according to social trust which is built by the similarity, the intimacy and the service between nodes. Bulut et al. [35] introduced the metric of trust, and presented a routing algorithm which used friendships to make the forwarding decisions of messages.
In the existing mHealth research, wireless access network and mobile terminal are mainly used to transmit medical data and provide telemedicine services. At the same time, privacy protection and secure transmission are discussed in terms of security technology and means. However, the current mobile Internet has been overburdened, and the data traffic needs to be diverted and offloaded. Therefore, exploring the data transmission technology of OppNets and applying it to mobile medical service is of great significance to promote the application of mHealth.

System model
In 1967, a social psychologist Milgram Stanley put forward the Six Degrees of Separation theory [36]. It reveals an important principle: any two strangers in the world can contact with each other by a link made up of six people. Later, he conducted a "chain letters" experiment in which he randomly sent some letters to 160 people living in Omaha, and asked each recipient to send the letter to a friend who thought he was closer to a Boston stockbroker. In the end, most of the letters were sent to the stockbroker after five or six steps. Motivated by the Six Degrees of Separation phenomenon, we propose a trusted data-forwarding scheme based on friend circles. This scheme can effectively prevent strangers from participating in the process of data transmission by constructing a trusted transmission environment-friend circles and relying on the friends of nodes to forward each packet. Therefore, the privacy problem and selfish behavior can be avoided effectively, and the data transmission performance is high.
In our work, the model of mHealth system is designed as shown in Fig. 2. Based on the transmission of OppNets, the patient physiological data collected by various sensors are sent to the hospital in order to realize the personal monitoring of human health, and patients can access whenever and wherever a variety of medical health information from doctors or other peoples to establish a health concept oriented to promoting disease prevention and strengthening disease prevention.
In the OppNets, we assume that each node has different social relations and behaviors which can be described by his/her social features and history encounters. These social features can be obtained by a certain means (for example, questionnaire survey) before the deployment of the network, and the history encounters can also be collected with the wireless terminal devices after a period of network running.
The transmission mechanism in mHealth is described as follows: (1) Transmission of the patient physiological data. To ensure the security, these data use a single-path transmission scheme. That is, they are forwarded in turn by the people who are within the friend circles of the previous one and have more opportunity to access the destination. (2) Transmission of the health information accessed from other people. To improve the transmission efficiency, this information uses a multipath transmission scheme. In other words, they are copied into all friend circles of the people, and the process ends when the people obtain this information.

Construction of friend circles
In the section, we first analyze the relationship between nodes reflected by their historical encounters, and discuss the importance of different social features of nodes, then construct the friend circles of nodes according to this information.
Historical encounters The historical encounters can generally be obtained from the records of software attached to the mobile intelligent terminal. They can reflect the relationship between nodes and reveal the characteristics of node mobility over a period of time by some statistical measurements, including the number, average time, and average time intervals of encounters, and so on. In general, the more the number of encounters between nodes is, the longer their encounter time is, and the higher their encounter frequency is, the closer their relationship is. On the contrary, the less their encounter number is, the shorter their encounter time is, and the lower their encounter frequency is, the more distant their relationship is.To exactly measure the relationship between nodes, we introduce a metric as follows: where T is the time interval between the collected data in system. f(t) is the average wait time for each packet forwarding. t k is the kth interval time of encounters. w ij is the measurement of the relationship between nodes v i and v j . It is obvious that w ij ≥ 1, and the value of w ij is bigger, nodes v i and v j are closer.
Social features In OppNets, nodes are the smart mobile devices used or carried by people, so they have the social characteristics of people, including natural features (such as gender, age, and body mass index) and social features (such as classmate, friend, and colleague). These features can be used to describe the relationship between nodes in society, and affect node movement and data forwarding. It is proved that the smaller the feature distance between nodes is, the more their connection is [37]. However, there are many social features of nodes. Two real trace datasets (Infocom 2006 [38] and MIT Reality [39]) provide more than 10 social features, such as affiliation, city, neighborhood, research group. In these features, only a small fraction has a significant impact on the relationship between nodes, and can be picked out by their Shannon entropy as follows: where x j is a possible value of the social feature f i . p(x j ) is the probability of x j . Clearly, the larger the Shannon entropy E(f i ) is, the bigger the impact of f i is.
Circles of friend Definition 1 For any two nodes in the network, if their relationship metric is greater than a certain threshold, namely, they have a close relationship, then they can be called friend. It is described as follows: where w ij is the relationship metric defined in formula (2). τ is the threshold which is used to adjust the degree of intimacy relationship between nodes. F i is the friend set of node v i .

Definition 2
For any nodes in the network, if they have the same value of a social feature (that is, they have the same hobbies and characteristics) and they are friends with each other, they form a circle of friends.
The specific construction process of friend circles is as follows: Step 1. Construct the social circle of the node according to its social features.
where f i is the ith feature value of the node. F(v j ) is a function for finding the feature values of node v j . C i is the ith social circle of the node and is composed of nodes with f i . It is worth mentioning that there are many social features for each node, and each feature has many values. In practical application, important social features and eigenvalues should be screened according to the formula (2) to avoid interfering with the process of data transmission by the irrelevant social features. The social circles of nodes are shown in Fig. 3. Here, a social feature corresponds to a certain kind of social circle, and a value of the social feature corresponds to a specific social circle.
Step 2. The friend circles are constructed by removing strangers from the social circles of the node using the formulas (3) and (4). Thus, we have where FC i is a friend circle of node v i .

Trust transmission algorithm
In the section, to meet the needs of different application scenarios of mHealth, we provide two trust transmission algorithms based on the structure of friend circles.
Multipath transmission algorithm In OppNets, a flooding-based routing algorithm, such as epidemic [17], is proposed. It has the highest delivery ratio and minimum transmission delay by sending a large number of data copies along multiple paths. Based on the above idea, we propose a multipath transmission algorithm based on the structure of friend circles. Its transmission strategy is designed as follows: the source node forwards a copy of data to each of its friend circles, and each recipient does the same until the destination node receive the data. Forwarding via the friends of the node, the data are transmitted along the multiple circles of friends, which can improve the chance of meeting the destination node as much as possible, and obtain a larger delivery ratio and a smaller transmission delay. This algorithm is suitable for the application scenarios where the data need to be transmitted quickly and widely. For example, the medical and health information that patients need is transmitted in mHealth.
The multipath transmission algorithm based on friend circles is shown in algorithm 1, its process is explained as follows: At a certain point, the node v c has a data packet p to send to the node v d , and it meets the node v i . If v i is v d , or v i does not have p and is a member in friend circles of v c , v c copies p to v i . If v d has accepted p, this transmission process ends. Otherwise, the above process is repeated.

16: end while
Single-path transmission algorithm In order to reduce the network overhead and ensure the security of data, we propose a single-path transmission algorithm based on friend circles. In this algorithm, only one piece of data is allowed to exist in the whole transmission process, and the data are transferred along a path and finally arrive at the destination node. In order to improve the forwarding effect, the relay nodes need to be selectively identified. Therefore, we designed a transmission algorithm based on the greedy strategy. If the encounter node is a member in the friend circles of the current node, and it has more opportunities to access the destination node, it can be selected as the relay node. Furthermore, if the encounter node is in the friend circles of the destination node, it is considered to have more opportunities to access the destination node. In addition, if the encounter node has more friends than the current node, it is considered to have more opportunities to access the destination node. In a word, the selection strategy of relay node is as follows: the encounter node is a member in the friend circles of the current node. If it is in the friend circles of the destination node, or it has more friends than the current node, it is selected as the relay node. The single-path transmission algorithm based on friend circles is shown in algorithm 2, its process is explained as follows: At a certain point, the node v c has a data packet p to be sent to the node v d , and encounters the node v i . If v i is v d , or v i has more opportunities to access v d than v c , v i is select a relay and v c forwards p to v i . If v d has accepted p, this transmission process ends. Otherwise, the above process is repeated.
The algorithm can only forward the data packet to an optimal encountered node which is within the friend circles of the current node and considered to have more opportunities to access the destination node. It is similar to the experiment of chain letter, that is, it can verify the Six-Degree Separation theory to a certain extent. Therefore, this algorithm has the minimum number of data copies and good transmission performance. It is suitable for the application scenario with dense distribution of nodes and high-security requirements. For example, the patients' physiological data are uploaded to the hospital in mHealth.

Algorithm 2 Single-path Transmission Routing Based on Friend Circle
Input: source node v s , destination node v d , data p, friend circle

Description of problem
In the diagnosis and treatment of patients, we produce a large number of medical data, such as patient information, medical record, examination data, doctor's advice, etc. Among them, the examination data are especially large. To get an accurate understanding of the patient's condition, various examinations are often required. In the laboratory inspection, it includes routine, biochemical, immunologic, bacteriological, and other tests; each examination contains a number of subitem checks; and each check contains medical data of a hundred fields. Table 1 shows a routine biochemical test report which contains 26 inspection items, and more items are examined in some special cases. In the imaging examination, it includes X-ray, CT, B-ultrasound, NMR, and these examinations will produce a lot of images. In the case of PET-CT, each patient produces an average of 400 images, of about 2 GB. According to the report [40], the global medical big data were 153 TB in 2013, and is expected to reach 2314 TB by 2020, estimated at an annual growth rate of 48%, as shown in Fig. 1b. Faced with such a large amount of data, the communication technology is not enough to deal with them. Therefore, a compression technique is needed to reduce the amount of medical data in the network.

Integer wavelet transform
In image processing, the input data are expressed as integers, so we use the integer wavelet transform to compress medical image data. Integer wavelet transform can remove the correlation between data to a certain extent, eliminate redundant information, and reduce the entropy of data; thus, it can provide a theoretical basis for lossless data compression [41,42]. For the original signal S i , it is decomposed into the low-frequency signal S i−1 and the high-frequency detail signal D i−1 by integer wavelet transform, and the transformation process contains the following three steps.
Step 1. Splitting: The original signal S i is usually divided into two disjoint subsets: even and odd sequences.
Step 2. Prediction: In view of the correlation between data, S i-1 can be used to predict D i−1 by adopting a prediction operator p, so that D i−1 = p(S i−1 ). One of the simplest prediction operators p is the mean of two adjacent even numbers, we have: Step 3. Updating: After n times decomposition, the wavelet of the original data is expressed as {S i−n , D i−n , D i−n+1 ,…, D i−1 }. The process of reconstruction can recover the original signal by antiupdating, antiprediction, and merging steps, as shown in Fig. 4.

Entropy code
To improve the compression performance, the data need to be rescheduled and shuffled before entropy coding to prioritize the same bytes as possible. In the compression process, the algorithm of entropy code is the deflate algorithm which is a general lossless compression algorithm. It is a combination of the lz77 dictionary coding and the Huffman coding [43]. In addition, TS wavelet filter is chosen to carry out integer wavelet transform, and its advantage is that the compression and decompression time overhead is much less and the compression ratio is slightly less than the binary arithmetic coding.

Simulation datasets
Two real trace datasets are used in our simulations, and their details are described as follows. (1) Infocom 2006 trace datasets [38] is a common trace data and available at Crawdad. This datasets is collected by recording the contacts between attendees with iMote. It consisted of two kinds of data: contacts data and social features of the attendees. Among them, the data of 61 attendees are only used because the profiles of other 18 attendees have some problems. We use the data including 74,981 contacts in 337,418 s, and five social features such as affiliation, living city, nationality, language, and residing country.
(2) MIT reality mining datasets [39] is a common trace data and collected by recording the contacts between 94 teachers and students with mobile phone. It is also consisted of two kinds of data: contacts data and social features. Among them, we use the data of 57 participants because the incomplete information of the other, including 411,313 contacts in 897,921 s, and five social features such as neighborhood, commuter time, haunting, affiliation and working time.

Performance metrics
There are four performance metrics used to assess each algorithm. (1) Delivery ratio: the ratio of the number of medical data delivered successfully to send out during a given interval.
(2) Delivery delay: the time taken for the data to be successfully delivered. a node is forwarded only if it is within the friend circles of the current node and has more opportunity to access the destination. (3) Spray-and-wait (S-W) [44]: there are 10 data copies at the beginning. First, each node with more than one copy sends half to the encounter node, and then none of the nodes forwards any data copy until the destination is encountered. (4) SimBet [45]: it forwards data based on SimBet utility. (5) ST-Epidemic (ST-E) [32]: an effective transmission algorithm based on social trust. (6) F-R [33]: an effective transmission algorithm based on friendship.

Data compression
In the simulation, the proposed algorithm is evaluated by comparing to several lossless compression schemes. Among them, TS wavelet filter is selected to carry out integer wavelet transform, and the actual data MIT-BIH (Beth Israel hospital of Massachusetts institute of technology) arrhythmia database [46] is used as simulation data. The results are shown in Table 2, it can be seen that the proposed compression algorithm increases the compression ratio by 55% compared with several compression algorithms, while the compression time cost is equal to that of other compression algorithms. The simulation shows that the proposed compression algorithm based on integer wavelet transform has proven excellent performance.

Effect of threshold
In the simulation, the effect of threshold τ is evaluated. Figure 5 shows that τ has important influences on the multipath scheme, while the effect of the single-path scheme is relatively small. In the multipath scheme, with the threshold τ increases, the lists of nodes friend get smaller, and nodes which participate in the forwarding get smaller. Hence, the number of forwarding gets smaller, the hop count gets smaller, and the delivery delay rises. To our surprise, the delivery ratio increases maximum and then decreases. The reason is as follows: the threshold decreases to a certain value, the copies of the message is so enough that the cache is full and some packages are discarded. Hence, the delivery ratio reduces.

Comparison of different transmission algorithms
In the simulations, the proposed transmission algorithms are assessed by comparing to server existing algorithms. From Fig. 6, it is clear that the multipath scheme has a larger delivery ratio and a shorter delay. It can achieve 62% of delivery ratio, while single-path, SimBet, S-W, ST-E, and F-R, could only deliver 58%, 59%, 56%, 61.2%, and 60.6% respectively. In addition, the single-path scheme has the least hop counts and number of forwarding. Compared to multipath scheme, SimBet, S-W, ST-E, and F-R, the single-path scheme decreases the number of forwarding by about 50.9%, 20.3%, 62.1%, 48.6%, and 46.3% respectively. In the MIT reality mining datasets, the simulations result is shown in Table 3. Clearly, our algorithm is better than other. Compared to the single-path, SimBet, S-W, ST-E, and F-R, the multipath scheme increases the delivery rate by about 7.3%, 5.1%, 10.2%, 2.8% and 4.0%, and reduces the latency by about 5.5%, 3.6%, 7.2%, 2.0% and 2.4% respectively. Compared to the multipath, SimBet, S-W, ST-E, and F-R, the single-path scheme decreases number of forwarding by about 55.8%, 29.7%, 65.4%, 54.4%, and 54.3% respectively. The simulation results are consistent with the above results.

Discussion
In previous studies, wireless access networks such as 3G/4G and Wi-Fi were mainly used to transmit medical data in mHealth. However, with the vigorous development of the mobile Internet, its data traffic is growing exponentially, which brings serious challenges to divert and unload these traffic and has become a common concern of  academia and industry. The introducing of OppNets can not only lighten the load of access networks, but also reduce the cost pressure of users. Therefore, it is a significant attempt to introduce OppNets into mHealth. In our study, the transmission algorithm based on friend circles has a low time complexity and only O(n). Its disadvantage lies in the use of the social features and historical encounters of nodes. The former can be obtained by filling in a questionnaire when the user is registered, and the latter is a kind of dynamic data which need to be updated and maintained every now and then. In addition, the data compression algorithm based on integer wavelet transform is a mature and developed technology, which has the advantages of consuming less computation and less compression times.
In the transmission algorithm, the parameter τ is mainly used to control the degree of intimacy between nodes. The larger the value of τ is, the closer the relationship between friends is, and the fewer the number of nodes involved in medical data transmission is, the higher the data security is, but the greater the transmission delay of medical data is. On the contrary, the smaller the value of τ is, the more the number of nodes participated in transmission is, the lower the medical data security is, and the shorter the transmission delay of medical data is.
In this study, we mainly use the friend circles to achieve the safe and efficient medical data transmission. Among them, the definition of friends only takes into account historical encounter data, not other factors, such as recommendations of others, and it can be carried out to more accurately measure credibility between nodes in the future. In addition, we only consider simply the data compression problem, and we should construct a complete data compression scheme in the future from the perspectives of time and space.

Conclusion
The mHealth framework faces some challenges such as the vastness of medical data, sensitivity of patient information and ubiquity of patient physiological information collection, whereas OppNets has the characteristics of node mobile, self-organization, and ubiquitous, which makes it has a good application prospect in various normal and nonnormal scenarios. In this paper, we use OppNets to transmit medical data in mHealth, which is a good solution, and can effectively divert and offload the data traffic of mobile Internet. In addition, the structure of friend circles is beneficial to safely and efficiently transmit the patient's physiological parameters and medical health information, and the data compression based on the integer wavelet transform can effectively reduce the amount and size of data and is beneficial to the faster transmission of medical data. The experimental results show that the proposed scheme is effective and has good transmission performance while ensuring the safety and reliability of media data.


extfieldsofstudy:
Physics
Computer Science

text:
AnatomyMR: A Multi-User Mixed Reality Platform for Medical Education

Mixed Reality (MR) has opened up new means of imparting education, especially in the medical field. Students could view the whole human anatomy and it’s components at multiple levels of scale to learn their location and naming nomenclature, and also interact with them separately to familiarize themselves with their functions. In this paper we propose a platform for Medical education in MR which creates shared experiences, providing support for teaching within classrooms. The application would also work as a standalone experience, augmenting important information over the anatomy model for the student’s reference when a shared experience is not in session, thereby facilitating self-study. The platform would be built in such a way that the instructors would also have the option to add 3D models and relevant content to the existing courseware and have it rendered in the mixed reality space.

INTRODUCTION
Anatomical education is the foundation of medical science, without a proper grasp of the functions and structure of the organs and biological systems a medical professional wouldn't be able to understand the effects a disease or accident might have on the human body. Of all the conventional approaches to imparting anatomical education cadaver dissection is considered to be the gold standard [1], but this approach has proven to be costly, time intensive, and found to induce a significant amount of psychological stress among medical students [2,3], furthermore, some students might not be able to learn through cadaver dissection due to cultural or religious beliefs [4]. With the advances in visualisation technologies and techniques,3D representations of the organs and biological systems can be displayed in immersive media such as Augmented Reality(AR), Mixed Reality(MR) and Virtual Reality(VR), to supplement the use of cadavers in teaching anatomy or maybe even completely replace the use of cadavers [5].
Mixed Reality(MR) is a hybrid between a digital reality and the real-world, the simulated 3d objects of the digital world are placed over the real-world environment in such a way that they are perceived to be a real-world object that interacts naturally with its environment. .

Fig.1: Mixed Reality
The Reality-Virtuality Continuum proposed by [6] shows Mixed Reality(MR) encompassing the spectrum of the different types of realities between Real Reality and Virtual Reality.
Mixed Reality could prove to be a powerful tool as an anatomical education tool, since the 3d models simulated in this immersive environment mimic real-world models, a model of the human anatomy could be displayed in MR with multiple levels of details and overlaid information. Also, MR based

EXISTING METHODOLOGIES
A number of MR/AR based education tools have been put forth for anatomical education or for specific medical procedures. [8] suggests an augmented reality enabled studio which used projection mapping to superimpose a 3d rendering of the anatomy over a person. This approach creates a collaborative environment for learning, as multiple people can perceive the projections without the aid of any special Head Mounted Display (HMD), but the need for a volunteer to act as a screen for the projections might not be ideal to teach the more complex systems and parts of the gross anatomy, since the projections might not perfectly conform to the volunteer's shape and posture, the rendering of the different parts of the anatomy might be disproportionate compared to the volunteer's actual anatomy. [9] is an augmented reality-based solution meant to be deployed in mobile applications, fiducial markers are used to augment the 3d models and the option to manipulate the rendered models are provided. Though this system might be better than the conventional methods of teaching [10] it's been found to be less effective than cadaver dissection [11], which might be due to the lack of immersion compared to a HMD based mixed experience where the 3d models might resemble and react to the environment like a physical object.

PROPOSED SYSTEM
We propose a multi-user mixed reality platform which creates a collaborative learning environment within classrooms. The system would ideally consist of multiple Mixed Reality HMDs with spatial mapping capabilities (such a the Microsoft Hololens) communicating over a network to render the 3d models of the anatomy at the same position and orientation with respect to the environment they are in, instead of using the HMD as a frame of reference to position the models, this would be executed through the sharing of spatial anchors [12]. The HMDs would also be aware of each other's position and direction of gaze in the room for a better collaborative environment.
The system would keep track of the type of user i.e student or faculty and generate a separate session to which the devices could be connected to, who is using the device to incorporate the dynamics that exist within classrooms, and thereby work as an effective supplementary tool for teaching. The system would also be provided with a desktop application which can be used to upload 3D Models and related information to a server, from which the HMDs would download the data to be displayed during class so that the application's contents aren't static and can be updated based on the courseware.

METHODOLOGY
The platform's functionality is dependent on the mode it's operated in : • Standalone Mode: This mode is used when the HMD is not connected to a network or when there's no other device in the network that is in the same session. Standalone mode provides a self-learning experience to the user, they are allowed to interact with and manipulate the parts of the anatomy model while being able to derive information from them through voice-overs triggered through interaction or through spatial annotations.
• Classroom Mode: This mode would be used when multiple devices are present in a session and a faculty's device is detected, the model displayed in this mode would have less integrated voiceovers and annotations compared to standalone mode, since the faculty is expected to guide the students through the experience.
When operated under classroom mode, to capture the dynamics that exist between the faculty and students, the application in the faculty's HMD would be equipped with extra functionalities such as: • Ability to manipulate and select models within the whole anatomy model • The ability to draw in 3d space During the session, the student's HMD would have the option to take screenshots or record certain parts and save as a video for a later session.

APPLICATIONS
This platform could be extended to teach other and more specialized medical topics, such as Histology and Neuroscience, provided the appropriate 3d representations of the cells or neural pathways are available. The effect of a disease on multiple levels of scale could be visualized more clearly, right from its effects on the gross anatomy and it's symptoms to the structure and working of the microbe that's causing the disease. Furthermore, real DICOM data of patients with certain diseases or patients who have met with an accident could be converted to 3D models and displayed within the application for a deeper understanding [13], with a streamlined workflow this approach could also be used for surgery planning as well [14].

CONCLUSION AND FUTURE WORKS
Mixed reality tools could revolutionize the medical industry especially medical education. With the improvements in processing power and MR hardware we can expect more and better applications that leverage this media to seep into everyday use for medical professionals. Thus, digital simulations of the human body could one day be realistic enough to completely replace the need for the use of cadavers to teach anatomy or practice surgical procedures. This platform is at its preliminary stages and requires more research to understand it's efficacy and to improve the interactions. With the everchanging MR hardware landscape, the platform would have to be standardized and scalable to make it device agnostic.