Statistical Channel Knowledge-Based Distributed Power Allocation for Analog Network Coding in High SNR

Abstract

A novel distributed power allocation scheme for analog network coding (ANC) in high signal-to-noise ratio (SNR) is proposed by using statistical channel knowledge at the transmitters only. The scheme considers nonorthogonal amplified-and- forward (NAF) protocol. In the derivation, a general Rayleigh fading multiple hop network is accurately approximated by a simpler two hop network, and the closed-formed expression for the outage probability of the simplified two hop network is obtained and optimized with respect to the power allocation. Numerical results show that the derived power allocation scheme has significant performance gain over the equal power scheme. In some cases, it approaches the optimal scheme.

1 Introduction

Recently, physical network coding (PNC), or analog network coding (ANC), have been widely studied to achieve better network performance [1,2,3,4,5]. It allows senders to interfere, then lets the router forward these interfering signals instead of the data packets. At the destinations, each node extracts its desired signals by subtracting the overheard signals from the interfering signals.

1.1 Related Works

The works on PNC can be classified into two categories: One is the denoise-and-forward network coding (DFNC) scheme. In this scheme, multiple sources transmit simultaneously to a relay, and the relay maps the received signals into symbols from a discrete constellation. The routers forward these mapped signals to their corresponding destinations. Zina etal. [6] analyzes error probability of the joint physical network coding (PNC) mapping with interleaving and multiuser detection techniques. Khan et al. [7] considers DFNC scheme based on multiple relay system to analyze various performance metrics, including error probability, outage probability and channel capacity. The random coding error exponent for the uplink phase of a two-way relay system is investigated, based on XOR coding scheme in [8]. Abu [9] proposes joint PNC and forward error correction scheme to improve BER performance. However these schemes require complex decoding and precise (amplified and phase) channel estimate at relays, It may not be feasible to be employed in some systems with limited resources.

The other is nonorthogonal amplified-and-forward network coding (NAFNC) scheme. This scheme simply amplifies and forwards the received signals from sources over a multiple access channel (MAC). The amplified signals are finally forwarded to the destinations by the router. Thu et al. [10] improves system throughput at a millimeter-wave radio system. Modem and Prakriya [11] proposes joint ANC and beamforming scheme based on two-way energy harvesting scheme. It is presented that joint ANC and space time block coding schemes improve BER performance in [12], based on two-way channels. These works focus on practical systems instead of general systems and are not able to be employed in different systems. For practical ad hoc systems, with strict power constraints, NAFNC is more attractive as it does not require complex decoding at the relays. In addition, unlike DFNC, NAFNC does not require precise (amplified and phase) channel estimate to operate pre-equalization [13]. In the other hand, main works about NAFNC focus on a detailed two-way system. Differently, we consider NAFNC in a general network with multiple sources, relays and destinations in this paper.

A lot of works have conducted on power allocation with instantaneous channel state information (CSI) at both transmitters and receivers in a two-way system with ANC [14, 15]. However, these are required to feedback instantaneous-CSI in each data frame, leading to a lot of network overheads. These real-time power allocation schemes may not be feasible in some systems. Feedback channels from receivers to transmitters may have very low capacity [16, 17]. Using statistic channel knowledge (SCK) at transmitters in a two source butterfly network with regenerative network coding [19], power allocation that minimizes the frame error probability has been studied. However these works assume very special networks which make it difficult to extend them to other networks with ANC.

However, it has been demonstrated that some common algorithms proposed for some optimized problems achieve excellent performance, there are some challenges and problems in real-time implementation with central coordinating mechanisms. It is because central coordinating mechanisms require much network overheads and high computational complexity. Distributed power allocation algorithms, requiring every node to know local channel-state-information instead of global one, are popular to be employed in real-time systems by consuming few network overheads and low computational complexity [20, 21]. This paper focuses on proposing distributed power allocation algorithms with SCK.

1.2 Analysis and Contributions

In general, a destination requires two parts of information to recover its source in a network with ANC. One is “the interfering signals” or the mixed information, referred to as network coded information (NCI) in this paper. The other is the information that the destination overhears from other sources rather than its own source, referred to as side information (SI). Both of them need to be forwarded to the destination successfully as Fig. 1. An ANC-based fading system with 3 source-destination pairs {$s_{1},d_{1}$}, {$s_{2},d_{2}$} and {$s_{3},d_{3}$} is shown in Fig. 4. For simplicity, each dotted line in this figure denotes a wireless subnetwork rather than a realistic channel. For destination $d_{1}$, the information from sources $s_{2}$ and $s_{3}$ are defined as its SI. This SI is transmitted in a subnetwork denoted by a dotted line. NCI is denoted by $f(s_{1},s_{2},s_{3})$, i.e., the overlapped analog signal waveforms the relay receives over a MAC when three sources transmit simultaneously. If any of the information $s_{2}$, $s_{3}$ and $f(s_{1},s_{2},s_{3})$ is transmitted erroneously to the destination, the destination will fail to recover the source $s_{1}$. Moreover, NCI and SI are not transmitted at the same time in the same links.

In the fading system, $P_{nci}^{d_{1}}$ is assumed to be the probability of event $\varepsilon _{1}$ that it fails to forward NCI $f(s_{1},s_{2},s_{3})$ to destination $d_{1}$, and $P_{si}^{d_{1}}$ is the probability of event $\varepsilon _{2}$ that SI ($s_{2},s_{3}$) aren’t obtained at destination $d_{1}$. The events ${\varepsilon }_{1}$ and ${\varepsilon }_{2}$ are mutually independent because SI and NCI are conveyed in different independent links, and thus the probability of event that $d_{1}$ fails to recover $s_{1}$ is $P_{o}^{d_{1}}=1-(1-P_{nci}^{d_{1}})(1-P_{si}^{d_{1}})=P_{nci}^{d_{1}}+P_{si}^{d_{1}}-P_{nci}^{d_{1}}P_{si}^{d_{1}}\approx P_{nci}^{d_{1}}+P_{si}^{d_{1}}$ in the high signal-to-noise ratio (SNR) regime since the term $P_{nci}^{d_{1}}P_{si}^{d_{1}}$ is much smaller than $P_{nci}^{d_{1}}(P_{si}^{d_{1}})$ and it can be ignored. From the above simple example, it can be seen that the outage probability of source $s_{i}$ in a network with ANC equals the sum of two probabilities, giving, $P_{si}^{d_i}+P_{nci}^{d_i}$. This motivates us to optimize the network performance by improving the two parts of outage probabilities separately in networks with ANC.

Fig. 1

A network example with ANC

In this paper, We first minimize the outage probability [27] caused by the event that NCI is conveyed unsuccessfully using a power allocation strategy in a general wireless network with NAFNC. This proposed power allocation scheme requires only SCK at transmitters to improve the outage probability performance. We then extend the proposed scheme to the case, where both NCI and SI are considered. The novelty of this work lies in the fact that it considers the case when the link between the source and the relay in a network with NAFNC suffers from deep fading and the outage probability performance of the source get worsen if other sources greedily transmit with a large power, which has never been studied before. This work uses power allocation as an efficient technique to balance the outage probability performance of the sources and to guarantee the system fairness. It provides a distributed greedy algorithm to achieve a practical solution, reducing network overhead compared with these centralized processing schemes. The contribution of this paper can be summarized as follows:

• Based on a Rayleigh fading multiple hop system for NCI, we first simplify the multiple hop network as a two hop network, then derive the corresponding closed-form expression of the system outage probability in the high SNR regime. Moreover, we simplify our derivation by approximating the complex terms of the expression with averages of special values.

• Using the simplified expression, a power allocation scheme, referred to as simultaneous iterative greedy algorithm (SIGA), is proposed for this system with a given transmission rate requirement for each source. The algorithm is performed in a distributed way to reduce the network overhead, requiring only SCK at transmitters. It is also validated to be convergent and approximates the optimal solution by computer simulation. We also extend SIGA to scenarios where both SI and NCI are considered.

2 System Model and Protocol Description

In this section, we first show a general multiple hop network model with NAFNC, where SI isn’t considered. It characterizes the NCI conveying process. Then, the network is simplified as a two-hop network. Based on this simplified network, we analyze the channel capacity for each source and define the system outage probability. For SI, it will be introduced in section V. Two assumptions are made as follows

• The destinations are assumed to know the fading-coefficients.

• The system is assumed to be synchronized, requiring only transmitted symbol synchronization.

2.1 System Model

There are m source destination pairs¹$\{\{s_{1},d_{1}\},\{s_{2},d_{2}\}$,

$\dotsc ,\{s_{m},d_m\}\}$ , one relay $r_{n}$, and these nodes conveying NCI by the routers. Source $s_i$ transmits at a fixed data rate $v_i$. Relay $r_n$ operates network coding (NC) over a MAC (see Fig. 1) and forwards the amplified signals. Let $\{r_{i1},r_{i2},\ldots ,r_{ik_i}\}$ denote $k_i$ relay nodes conveying NCI from relay $r_n$ to $d_i$ for source $s_i$. We assume that each terminal is equipped with a single antenna and operates in a full-duplex mode instead of a half-duplex constrain for simplicity.

Fig. 2

The simplified system model, not considering SI

Consider frequency non-selective, quasi-static fading and additive noise for each link. The channel gain is modeled as zero mean, independent, circularly symmetric complex Gaussian random variable. The channel gain from source $s_{i}$ to $r_{n}$ is denoted as $a_{s_i}$, and the channel gain from $r_{x}$ to $r_y(d_y)$ is denoted as $a_{r_y}(a_{d_y})$. Denote $1/\lambda _{x}$ as the variance of the channel gain $a_{x}$. Then the corresponding $|a_{x}|^{2}$ follows the exponential distribution with parameter $\lambda _{x}$. For example, $|a_{r_{12}}|^2$ as the channel gain from relay $r_{11}$ to $r_{12}$ is exponentially distributed with parameter $\lambda _{r_{12}}$. For simplicity, we also set $\lambda _i=\lambda _{s_i}$ in the following. Without loss of generality, the additive noise is assumed to be a complex Gaussian random variable with mean zero and variance $N_{0}$.

2.2 Simplified System Model

In a multiple hop network with NAFNC, the capacity expression of the system is too complex, and thus it is necessary to simplify the network using approximation. To express it more clearly, we show a 2-hop relay network with AF protocol including one source-destination pair and one relay. Source s forwards information to destination d with the help of relay r without a direct link from s to d. Each terminal with a single antenna is assumed to transmit with power P in a full-duplex mode. The channel gains from s to r and r to d are assumed as $x_1$ and $x_2$, respectively. Thus $|x_1|^2$ and $|x_2|^2$ are exponentially distributed and their parameters are assumed to be $\lambda _{x_1}$ and $\lambda _{x_2}$, respectively. The additive noise power is normalized as 1. Then the received $\text {SNR}$ [23] at the destination is

$$\begin{aligned} \begin{aligned} \text {SNR}_r=\frac{|x_1|^2|x_2|^2 P^2}{|x_1|^2 P+|x_2|^2 P+1} \end{aligned} \end{aligned}$$

(1)

We rewrite Eq. (1) and observe as follow

$$\begin{aligned} \begin{aligned} \text {SNR}_r&=\frac{P}{\frac{1}{|x_1|^2}+\frac{1}{|x_2|^2}+\frac{1}{P}} \\&< \frac{P}{\frac{1}{|x_1|^2}+\frac{1}{|x_2|^2}}< \min (|x_1|^2,|x_2|^2)P. \end{aligned} \end{aligned}$$

(2)

With $\frac{1}{P} \rightarrow 0$ in the high SNR regime, we have

$$\begin{aligned} \begin{aligned} \text {SNR}_r&=\frac{P}{\frac{1}{|x_1|^2}+\frac{1}{|x_2|^2}+\frac{1}{P}} = \frac{P}{\frac{1}{|x_1|^2}+\frac{1}{|x_2|^2}}\\&\ge \frac{1}{2}\min (|x_1|^2,|x_2|^2)P \end{aligned} \end{aligned}$$

(3)

where additive noise power is normalized. $\text {SNR}_r$ can be upper-bounded [24,25,26] with

$$\begin{aligned} \begin{aligned} \text {SNR}'_r=|z|^2P, \end{aligned} \end{aligned}$$

(4)

where $|z|^2=\min \{|x_1|^2,|x_2|^2\}$ is also exponentially distributed with parameter $\lambda _z=\lambda _{x_1}+\lambda _{x_2}$. Alternatively, the two hop network with AF is regarded as a point-to-point Rayleigh fading channel with fading coefficient z.

Motivated by this observation, we extend it to a multiple hop network with AF. Assume $x_i$ denotes the channel gain at the ith hop in this network. We give the received SNR in 2,3 and 4 hop networks in Table 1. From this, we find that the received SNR in the k hop network can be upper-bounded as

$$\begin{aligned} \begin{aligned} \text {SNR}_r=\sum _{i=1}^{k}\frac{P}{1/|x_i|^2}<\min \{|x_1|^2,|x_2|^2,\ldots ,|x_k|^2\}P. \end{aligned} \end{aligned}$$

(5)

Equation (5) means that the received SNR is subject to the worst channel among a multiple hop network with AF. Thus, we can upperbound the received SNR in a multiple hop network with AF by using a point-to-point Rayleigh fading channel. Then, the $(k_i+1)$ hop network from $r_n$ to $d_i$ in the system is approximated by a point-to-point Rayleigh fading channel with fading coefficient $b_{d_i}$, where $|b_{d_i}|^2=\min \{|a_{i1}|^2,|a_{i2}|^2,\ldots ,|a_{ik_i}|^2,|a_{id_i}|^2\}$ also follows an exponential distribution with parameter

$$\begin{aligned} \begin{aligned} \lambda _{bd_i}=\sum _{j=1}^{k_i}\lambda _{r_{ij}}+\lambda _{d_i}. \end{aligned} \end{aligned}$$

(6)

In this way, the multiple hop network model can be approximated by a two hop network, as shown in Fig. 2. The additive noise terms are $Z_n$ and $Z_{d_i}$ with mean zero and variance $N_0$.

Table 1 SNR in a multiple hop network with AF

2.3 Description of NAFNC

For convenience, we assume that each node transmits signals with power P. All relays simply amplify and forward their received signals to their next nodes. Using the simplified network, the corresponding NAFNC protocol consists of two stages. In the first stage, each source transmits signals to relay $r_{n}$ simultaneously. The signals received at the relay are

$$\begin{aligned} Y_{n}&=\sum _{i=1}^{m}\sqrt{P} a_{i}X_{i}+Z_{n}, \end{aligned}$$

(7)

where $X_{i}$ is the scaled symbol source $s_i$ transmits with the normalized power and $Z_{n}$ is an additive white Gaussian noise (AWGN) term with mean zero and variance $N_{0}$. In the second stage, relay $r_n$ forwards the amplified signals to destination $d_{i}$, and the received signals are

$$\begin{aligned} \begin{aligned} Y_{d_i}&=\beta b_{d_i} Y_{n}+Z_{i}\\&=\beta b_{d_i} \sqrt{P}\sum _{i=1}^{m} a_{i}X_{i} +\beta b_{d_i}Z_{n}+Z_i, \end{aligned} \end{aligned}$$

(8)

where $Y_{d_i}$ is the received signals at relay $r_n$ and $\beta$ is the amplifying factor, given by

$$\begin{aligned} \beta =\left( \frac{P}{\sum _{i=1}^{m} |a_i|^{2}P+N_{0} } \right) ^{\frac{1}{2}}. \end{aligned}$$

(9)

2.4 Performance Metric

Denote $I(X_{i};Y_{i}|H_i,X_{-i})$ as the capacity of source $s_i$, where $H_i$ denotes the CSI of the router for source $s_i$, $X_{-i}=\{X_{1},\dotsc ,X_{i-1},X_{i+1},\dotsc ,X_{m}\}$ is source $s_i$’SI and $Y_i$ is the received signals at destination $d_i$. To guarantee the system fairness, the system outage probability $P_{nci}$ caused by NCI is written as [19]

$$\begin{aligned} \begin{aligned} P_{nci}&{\mathop {=}\limits ^{\Delta}}1-\text {Pr} \left( \bigcap _{i\in \{1,\ldots ,m\}}I(X_{i};Y_{i}|H_i,X_{-i})\ge v_i\right) . \end{aligned} \end{aligned}$$

(10)

Equation (10) means that the system suffers from an outage if any source’s mutual information is smaller than its given transmit rate, or, $I(X_{i};Y_{i}|H_i,X_{-i}) < v_i ~\exists i$.

To the best of my knowledge, The maximum $I(X_{i};Y_{i}|H_i,X_{-i})$ can’t be driven as a detailed expression, and require high complexity due to using joint multiple-user decoding. The mutual information $I(X_{i};Y_{d_{i}}|A,b_{d_i},X_{-i})$ denotes the mutual information achieved by using an suboptimal decoding scheme, which information from other sources is considered as interference terms . It is also popular to be employed in some paper [3, 4] due to low complexity of decoding. Then the system outage probability in this paper is defined as

$$\begin{aligned} \begin{aligned} P_{nci}&= 1-\text {Pr} \left( \bigcap _{i\in \{1,\ldots ,m\}}I(X_{i};Y_{d_{i}}|A,b_{d_i},X_{-i})\ge v_i\right) , \end{aligned} \end{aligned}$$

(11)

where $A=[a_{1},a_2,\dotsc ,a_{m}]$ is the CSI vector. Next, we analyze the mutual information $I(X_{i};Y_{d_i}|A,b_{d_i},X_{-i})$. In (8), the received signals $Y_{d_i}$ can be decomposed as

$$\begin{aligned} \begin{aligned} Y_{d_i}&=\underbrace{\beta \sqrt{P}b_{d_i} a_{i}X_{i}}_{\text {source information}} +\underbrace{\beta \sqrt{P}b_{d_i}\sum _{j=1,j\ne i}^{m} a_{j}X_{j}}_{\text {interference terms}} \\&\quad +\underbrace{\beta b_{d_i}Z_{1}+Z_2}_{\text {noise}}, \end{aligned} \end{aligned}$$

(12)

and therefore, the signals become

$$\begin{aligned} \begin{aligned} Y'_{2}=\beta \sqrt{P}b_{d_i} a_{i}X_{i} +\beta b_{d_i}Z_{1}+Z_2, \end{aligned} \end{aligned}$$

(13)

after the interference terms² are canceled. Substituting (9) into (13), we have

$$\begin{aligned} \begin{aligned}&Y'_{2}=\frac{b_{d_i} a_{i}P}{\sqrt{\sum _{i=1}^{m}|a_{i}|^2 P+N_{0}}}X_{i}\\&+\sqrt{\frac{P}{\sum _{i=1}^{m}|a_{i}|^2 P+N_{0}}} b_{d_i}Z_{1}+Z_2. \end{aligned} \end{aligned}$$

(14)

From (14), $I(X_{i};Y_{2}|A,b_{d_i},X_{-i})$, denoted as $I_{i}$ for convenience, is derived as

$$\begin{aligned} \begin{aligned} I_{i}=\log \left( 1+\frac{|a_{i}|^{2} |b_{d_i}|^{2}\rho ^{2}}{\sum _{i=1}^{m} |a_{i}|^{2}\rho +|b_{d_i}|^2+1}\right) , \end{aligned} \end{aligned}$$

(15)

where $\rho =\frac{P}{N_{0}}$.

3 System Outage Behavior in High SNR

In this section, we derive the system outage probability $P_{nci}$ in the high SNR regime. First, the upper bound of the outage probability is derived as

$$\begin{aligned} \begin{aligned} P_{nci}&=1-\text {Pr}\left( \bigcap _{i\in \{1,\ldots ,m\}} I_{i}\ge v_i\right) \\&=\text {Pr}\left( \bigcup _{i\in \{1,\ldots ,m\}} I_{i}\ge v_i\right) \\&\le \sum _{i=1}^{m}\text {Pr}(I_{i}< v_{i}) \end{aligned} \end{aligned}$$

(16)

In the high SNR regime, we also have

$$\begin{aligned} \begin{aligned} P_{nci}&=1-\text {Pr}\left( \bigcap _{i\in \{1,\ldots ,m\}} I_{i}\ge v_i\right) \\&\overset{(a)}{\ge } 1-\prod _{i=1}^{m}\text {Pr}(I_{i}\ge v_{i})\\&=1-\prod _{i=1}^{m}(1-\text {Pr}(I_{i}<v_{i}))\\&\overset{(b)}{=}\sum _{i=1}^{m}\text {Pr}(I_{i}<v_{i}) \end{aligned} \end{aligned}$$

(17)

where the inequality (a) holds because the event $\epsilon (I_{j}\ge v_{j})$ implies a large $|a_{j}|^2$ can only worsen source $s_i$’ channels and thus make $\text {Pr}(I_{i}\ge v_{i}|I_{j}\ge v_{j})\le \text {Pr}(I_{i}\ge v_{i})$ (see (15)), and equation (b) follows because outage probability of each source $\text {Pr}(I_{i}<v_{i})$ approaches zero in the high SNR regime such that $\text {Pr}(I_{i}<v_{i})\text {Pr}(I_{j}<v_{j})\ll \text {Pr}(I_{i}<v_{i})$ can be ignored. Using (16) and (17), it is easy to show that the system outage probability in the high SNR regime can be approximated as

$$\begin{aligned} \begin{aligned} P_{nci}=\sum _{i=1}^{m}\text {Pr}(I_{i}<v_{i}). \end{aligned} \end{aligned}$$

(18)

Using (15), it can be shown that

$$\begin{aligned} \begin{aligned} \text {Pr}(I_{i}<v_{i})=\text {Pr}\left( \frac{|b_{d_i}|^2|a_{i}|^2}{\sum _{i=1}^{m}|a_{i}|^2+|b_{d_i}|^2+1/\rho }<\frac{2^{v_{i}}-1}{\rho }\right) . \end{aligned} \end{aligned}$$

(19)

Two cases can be discussed.

Case 1: $\lambda _{i} \ne \lambda _{j},~\forall i,j$.

Define $u:=|a_{i}|^2$, $v:=|b_{d_i}|^2$, $\delta =1/\rho$, $h(\delta )=(2^{v_{i}}-1)/\rho$ and

$$\begin{aligned} \begin{aligned} q_{k}&:= \left\{ \begin{aligned}&|a_{k}|^{2}~~~~\text {if}~k<i\\&|a_{k+1}|^{2} ~~\text {otherwise}, \end{aligned} \right. \\ \end{aligned} \end{aligned}$$

(20)

where $k\in \{1,2,\dotsc ,m\}$. Using Lemma 4 in Appendix B, the closed-form expression of $\text {Pr}(I_{i}<v_{i})$ in the high SNR can be derived as

$$\begin{aligned} \begin{aligned}&\text {Pr}\left( {I_{i}<v_{i}}\right) =P_{i}(\lambda _{1},\lambda _{2},\dotsc ,\lambda _{bd_i},\rho )=\frac{2^{v_{i}}-1}{\rho }\left[ \lambda _{bd_i}\right. \\&\quad +\lambda _{i}-\sum _{j=1,j\ne i}^{m}\left( c+\underbrace{\ln \left( \frac{\lambda _{bd_i}\lambda _{i}(2^{v_{i}}-1)}{ \lambda _{j}\rho }\right) }_{\text {Complex term I}}\right) \frac{\lambda _{bd_i}\lambda _{i}}{\lambda _{j}}+\\&\qquad \left. \left( \sum _{l=2}^{m-1}\sum _{\overset{1 \le k_{1} \le \cdots \le k_{i-1}}{\le k_{i+1}\cdots \le k_{l} \le m-1} }\sum _{s=1}^{l}\underbrace{\frac{\lambda _{k_{s}}^{l-2}\ln \lambda _{k_{s}}}{\prod _{j \ne s}^{l}(\lambda _{k_j}-\lambda _{k_{s}})}}_{\text {Complex term II}}\right) \lambda _{i}\lambda _{bd_i}\right] , \end{aligned} \end{aligned}$$

(21)

where c is a constant and $P_{i}(\lambda _{1},\lambda _{2},\dotsc ,\lambda _{bd_i},\rho )$ denotes $\text {Pr}({I_{i}<v_{i}})$ for convenience.

Case 2: $\lambda _{i}=\lambda _{j}~\exists i,j$.

Let $\lambda _{k_1}=,\dotsc ,=\lambda _{k_s}=\lambda _a\in \mathbb {R}^+$. Then

$$\begin{aligned} \begin{aligned} \text {Pr}\left( {I_{i}<v_{i}}\right) =\lim _{\overset{\lambda _{k_{j}}\rightarrow \lambda _a,}{\forall j\in \{1,2,\ldots ,s\}}} P_{i}(\lambda _{1},\lambda _{2},\dotsc ,\lambda _{bd_i},\rho ). \end{aligned} \end{aligned}$$

(22)

Note that the limit in (22) is finite. This can be proved for $\lambda _i=\lambda _a~\forall i$ in Theorem 1 in the next section. Other scenarios in (22) can be proved in a similar way.

By generalizing (21) and (22), we derive the system outage probability $P_{nci}$ as

$$\begin{aligned} \begin{aligned} P_{nci}=\lim _{x_j\rightarrow \lambda _j,\forall j}\sum _{i=1}^{m}P_{i}(x_{1},x_{2},\dotsc ,\lambda _{bd_i},\rho ) \end{aligned} \end{aligned}$$

(23)

Note that (23) is complex and nonconvex, which is not suitable for distributed power allocation.

4 Distributed Power Allocation with SCK

In this section, we simplify (23) to enable power allocation.

4.1 Simplification

From (21), we find that there are two types of complex terms. For the first type, we can simplify it as

$$\begin{aligned} \begin{aligned} \ln \left( \frac{\lambda _{bd_i}\lambda _{i}(2^{v_{i}}-1)}{\lambda _{j}\rho }\right) \sim \ln \left( \frac{2^{v_{i}}-1}{\rho }\right) , \end{aligned} \end{aligned}$$

(24)

because $\frac{\lambda _{bd_i}\lambda _{i}}{\lambda _{j}} \gg \frac{2^{v_{i}}-1}{\rho }\rightarrow 0$ in the high SNR regime. For the second type, we derive some properties in Theorems 1 and 2 before simplifying the term. For convenience, we set

$$\begin{aligned} \begin{aligned} \mathbf{t} =&[t_{1},t_{2},\dotsc ,t_{k}],~\mathbf{T} =[T_{1},T_{2},\dotsc ,T_{k}] \\ f(\mathbf{t} )=&\sum _{i=1}^{k}\frac{t_{i}^{k-2}\ln t_{i}}{\prod _{j \ne i}(t_{j}-t_{i})}. \end{aligned} \end{aligned}$$

(25)

Theorem 1 describes the limit of $f(\mathbf{t} )$ is linear with the reciprocal of the constant when all elements of vector $\mathbf{t}$ approach a constant.

Theorem 1

If $t_{i}\in \mathbf{t} ,t_{a}\in \mathbb {R}^{+}$ for $1 \le i \le k\in \mathcal {N}$, then

$$\begin{aligned} \begin{aligned} \lim _{\forall t_{i} \rightarrow t_{a}}f(\mathbf{t} )=\frac{(-1)^{k+1}}{k-1}t_{a}^{-1} \end{aligned} \end{aligned}$$

(26)

proof Please see Appendix C.

Moreover, if some elements in vector $\mathbf{t}$ approach a positive constant while other elements approach a different positive constant, the limit of $f(\mathbf{t })$ is still finite. These can be proved but are omitted here due to the length restriction. Overall, these results show that the function $\lim _\mathbf{T \rightarrow \mathbf{t} }f(\mathbf{T} )$ is continuous in the space of $\mathbb {R}^{k+}$. It also proves that $\text {Pr}(I_i<v_i)$ is a continuous function for variable $\lambda =[\lambda _1,\lambda _2,\ldots ,\lambda _m,\lambda _{bd_i}]$.

Theorem 2 describes function $f(\mathbf{t} )$ is monotonic for any $t_{i}$ if other variables are fixed.

Theorem 2

If $t_i>0~\text {where}~t_i\in \mathbf{t} ,\forall i$, then $f'(\mathbf{t} )=\partial f(\mathbf{t} )/\partial t_{i}~\forall i$ satisfies

$$\begin{aligned} \begin{aligned} f'(\mathbf{t} ) \left\{ \begin{aligned} >0&~~~~\text {if}~~(k~\text {mod}~2)=0\\ <0&~~~~\text {Otherwise} \end{aligned} \right. \end{aligned} \end{aligned}$$

(27)

proof Please see Appendix D.

Fig. 3

The relative mean error versus the source number

Considering the above, we approximates $f(\mathbf{t })$ with $g(\mathbf{t} )$ as

$$\begin{aligned} \begin{aligned} g(\mathbf{t} )&=\frac{1}{k}\sum _{n=1}^{k} \lim _{\begin{array}{c} {t_{l} \rightarrow t_{n}}\\ {l\ne n,\forall l} \end{array}}\sum _{j=1}^{k}\frac{t_{j}^{k-2}\ln t_{j}}{\prod _ {i\ne j}\left( t_{i}-t_{j} \right) }\\&=\frac{(-1)^{k+1}}{k(k-1)}\sum _{i=1}^{k}\frac{1}{t_{i}}, \end{aligned} \end{aligned}$$

(28)

where $g(\mathbf{t} )$ averages k particular points of the function $f(\mathbf{t} )$ and the second equation holds according to Theorem 1. These points are $\lim _{\forall T_{j} \rightarrow t_{i}}f(\mathbf{T} )$ for $i=1,2,\ldots ,k$, and the upper bound of the corresponding approximation error is

$$\begin{aligned} \begin{aligned}&|f(\mathbf{t} )-g(\mathbf{t} )|\\&\quad <\frac{1}{(k-1)k}\max \left\{ \left| \frac{k}{t_{\text {max}}}- \sum _{i=1}^{k}\frac{1}{t_{i}}\right| ,\left| \frac{k}{t_{\text {min}}}-\sum _{i=1}^{k}\frac{1}{t_{i}}\right| \right\} , \end{aligned} \end{aligned}$$

(29)

where $t_{\max }=\max (\mathbf{t} ),t_{\min }=\min (\mathbf{t} )$. Clearly, the upper bound of the error decreases when k increases with given $t_{\max }$ and $t_{\min }$. Using (24) and (28), the results in (21) and (22) become

$$\begin{aligned} \begin{aligned}&\text {Pr}'(I_{i}<v_{i})=P'_{i}(\lambda _{1},\lambda _{2},\dotsc , \lambda _{bd_i},\rho )\\&=\left( \lambda _{i}+\lambda _{bd_i}+h\left( \frac{2^{v_i}-1}{\rho }\right) \sum _{j=1,j\ne i}^{m}\frac{\lambda _{i}\lambda _{bd_i}}{\lambda _{j}}\right) \left( \frac{2^{v_i}-1}{\rho }\right) , \end{aligned} \end{aligned}$$

(30)

where $h(x)=-c-\ln x+\frac{1}{m-1}\sum _{i=2}^{m-1}\frac{(-1)^{i+1}}{i-1}{m-1 \atopwithdelims ()i}$. To show the error caused by these approximations, we define the relative mean error as

$$\begin{aligned} \begin{aligned} e=E\left( \frac{|\text {Pr}(I_{i}<v_{i})-\text {Pr}'(I_{i}<v_{i})|}{\text {Pr}(I_{i}<v_{i})}\right) . \end{aligned} \end{aligned}$$

(31)

Numerical results are shown in Fig. 3 where $v_{i}=1$ and $\lambda _{j}$ is drawn randomly within the interval [1 10] for any $j\ne i$. It is shown that the relative mean error e decreases when $\lambda _{i},\lambda _{m+1}$ and $\rho ^{-1}$ increase. Given the smallest value $\lambda _{m+1}=1$ and $\lambda _{i}=1$ in a practical system, the relative mean error e is smaller than 0.2 in the scenario of 6 sources when SNR=20dB.

Therefore, the outage probability $P_{nci}$ in (23) can be simplified as

$$\begin{aligned} \begin{aligned} P'_{nci}=\sum _{i=1}^{m}P'_{i}(\lambda _{1},\lambda _{2}, \dotsc ,\lambda _{bd_i},\rho ). \end{aligned} \end{aligned}$$

(32)

where $P'_{i}(\lambda _{1},\lambda _{2},\dotsc ,\lambda _{bd_i},\rho )$ is given by (30).

4.2 Problem Formulation

Obviously, each relay conveying NCI in a network with NAFNC improves the outage probability performance if it transmits with a larger power, except the source nodes. To simplify the optimization problem, we give a constraint that these relays transmit with equal power.

Without loss of generality, we assume that the power budget of each source is $E_{s}$, each relay has a power budget of $E_{r}$, and the total available power of the system is limited to $E_{t}$. $\phi _{i}$ is the power allocation factor profile of source $s_i$, $\phi _{r}$ denotes that of the relays, and the complement of the power factor profile of source $s_i$ is defined as $\phi _{-i}=(\phi _{1},\ldots ,\phi _{i-1},\phi _{i+1},\ldots ,\phi _{m})$ such that $\phi =(\phi _{i},\phi _{-i})$. Thus source $s_i$ transmits with power $\phi _{i}E_{s}$ and the relay transmits with $\phi _{r}E_{r}$. The minimum power factor profile of source $s_i$ and the relay are defined as $\phi _{i}^{\min }$ and $\phi _{r}^{\min }$, respectively. The additive noise power $N_{0}$ is normalized as 1. Considering (23) and the simplified system in Section 2, the optimization problem is formulated as

$$\begin{aligned} \begin{aligned} \min _{\overset{\phi _{1},\phi _{2},\dots ,}{\phi _{m},\phi _{r}}}~&P_{nci}=\lim _{\overset{x_j\rightarrow \lambda _j,}{\forall j}}\sum _{i=1}^{m}P_{i} \left( \frac{x_{1}}{\phi _{1}},\frac{x_{2}}{\phi _{2}},\dotsc , \frac{\lambda _{bd_i}E_{s}}{\phi _{r}E_{r}}\right) \\ \text {s.t.}~~&\phi _{r}^{\min } \le \phi _{r} \le 1, \phi _{i}^{\min } \le \phi _{i} \le 1~\forall i,\\&~~\phi _{r}NE_{r}+\sum _{i=1}^{m}\phi _{i}E_{s} \le E_{t}, \end{aligned} \end{aligned}$$

(33)

where N is assumed to be the number of the relays, used to convey NCI in the system. The target function in (33) can be simplified using (32) as

$$\begin{aligned} \begin{aligned} \min _{\phi _{1},\phi _{2},\dots ,\phi _{m},\phi _{r}}~&P'_{nci}=\sum _{i=1}^{m}\frac{A_{ii}}{\phi _{i}}+ \sum _{i=1}^{m}\sum _{j \ne i}\frac{A_{ij}\phi _{j}}{\phi _{i}\phi _{r}}+\sum _{i=1}^{m}\frac{B_{i}}{\phi _{r}}. \\ \end{aligned} \end{aligned}$$

(34)

with

$$\begin{aligned} \begin{aligned} A_{ii}=&\frac{\lambda _{i}(2^{v_i}-1)}{E_s}; ~~B_{i}=\frac{\lambda _{bd_i}(2^{v_i}-1)}{E_{r}};~~\\ A_{ij}=&\frac{h\left( \frac{2^{v_i}-1}{E_s}\right) (2^{v_i}-1)\lambda _{i} \lambda _{bd_i}}{E_{r}\lambda _{j}}, ~\forall i\ne j. \end{aligned} \end{aligned}$$

(35)

Note that the terms $A_{ii}$, $B_i$ and $A_{ij}$ are positive.

4.3 Distributed Power Allocation with SCK

Given the transmission powers of other sources and the relay, the optimal response of source $s_i$ can be calculated as

$$\begin{aligned} \begin{aligned} \mathcal {B}^{\star }(\phi _{-i},\phi _{r})&=\arg ~\min _{\phi _{i}} P'_{nci}(\phi _{-i},\phi _{r}) \\&=\left[ \left( \frac{A_{ii}\phi _{r}+\sum _{j \ne i}A_{ij}\phi _{j}}{\sum _{j \ne i}\frac{A_{ji}}{\phi _{j}}}\right) ^{\frac{1}{2}}\right] _{\phi _{i}^{\min }}^{1}\\ \end{aligned} \end{aligned}$$

(36)

where $[x]_{a}^b=\min \{\max \{x,a\},b\}$.

Since the function $P'_{nci}$ is nonconvex, it is difficult to achieve the optimal solution in a distributed fashion, we propose a distributed simultaneous iterative greedy algorithm (SIGA): Given the interference generated by other sources and power of the relay, all sources update their transmission powers simultaneously according to (36), and then the remain power is equally allocated to each relay. The process of SIGA is described in Algorithm 1.

4.4 Distributed Iterative Asynchronous Update

We introduce how to perform SIGA in a distributed fashion here. It is possible to assume that relay $r_{n}$ obtains SCK $\{\lambda _1,\lambda _2,\dotsc ,\lambda _m,\lambda _{bd_i},\forall i\}$ and the rate of each source by channel estimation and feedback. We also assume the source $s_i$ knows only $\lambda _i$, $\lambda _{bd_i}$ and $v_i$. Source $s_i$ can update its power with $\lambda _i,v_i$ and $\lambda _{bd_i}$ if it obtains $\vartheta =\phi _r/h\left( \frac{2^{v_i}-1}{E_r}\right) -\lambda _{bd_i}\sum _{j=1}^m\frac{\phi _{j}}{\lambda _j}$ and $\psi =\sum _{j=1}^m (2^{v_j}-1) h\left( \frac{2^{v_j}-1}{\rho }\right) \frac{\lambda _{bd_j}\lambda _j}{\phi _j}$ according to (36), since

$$\begin{aligned} \begin{aligned}&A_{ii}\phi _{r}+\sum _{j \ne i}A_{ij}\phi _{j}=h\left( \frac{2^{v_i}-1}{E_r}\right) \frac{\lambda _i(2^{v_i}-1)}{E_s}\vartheta \\&\quad -h\left( \frac{2^{v_i}-1}{E_r}\right) (2^{v_i}-1)\lambda _{bd_i}\phi _i /(E_r\lambda _i) \end{aligned} \end{aligned}$$

(37)

and

$$\begin{aligned} \begin{aligned} \sum _{j \ne i}\frac{A_{ji}}{\phi _{j}}=\frac{\psi }{\lambda _i}-h\left( \frac{2^{v_i}-1}{E_r}\right) (2^{v_i}-1)\lambda _{bd_i}/\phi _i. \end{aligned} \end{aligned}$$

(38)

The updating process of the algorithm is as follows

• (1) Initialize $\phi _{i} ~\forall i$ and $\phi _r$.

• (2) Relay $r_n$ broadcasts $\lambda _{bd_i}$ in equation (6).

• (3) Relay $r_n$ broadcasts two terms $\vartheta$ and $\psi$.

• (4) If source $s_i$ receives the two terms without error, it returns an ACK signal to the relay, and update its power allocation. Otherwise, its transmit power keeps invariant.

• (5) Relay $r_n$ updates $\vartheta$ and $\psi$ according to ACKs from sources. It is feasible since relay $r_n$ knows $\lambda _i,v_i, \lambda _{bd_i}\forall i$.

• (6) Repeat (3), (4) and (5) until SIGA converges.

4.5 Network Overhead Analysis

We assume a general n source destination pair and m relay network. SIGA is also assumed to converge after k iterations. Before relay $r_n$ broadcasts term $\lambda _{bd_i}=\sum _{i=1}^{m}\lambda _{r_{ij}}+\lambda _{d_i}$ according to equation (6) in this paper, relay $r_n$ requires to collect channel state parameters $\lambda _{r_{ij}}$ for $i = 1,.., m$ and $\lambda _{bd_i}$. The network overhead is $m+1$ float numbers. Then relay $r_n$ broadcasts two terms $\vartheta$ and $\psi$ at every iteration. In addition, every source returns an ACK signal including $\phi _i$. Thus the total overhead is $n+2$ float numbers at every iteration. Finally, the relay $r_n$ broadcasts $\phi _r$ to every relay at the cost of a float number. Thus we obtain the total network overhead is $m+2+k(n+2)$ float numbers.

5 The Extended SIGA

Note that the above SIGA doesn’t consider SI in a practical network. In the next section, we will extend SIGA to scenarios considering both NCI and SI. We show a simple example with 3 source-destination pairs and 8 relays in Fig. 4. It shows that SI are sent in a point-to-point channel or MAC. The dotted lines denote a single or multiple hop network for simplicity, and all links are assumed to experience Rayleigh fading. In Fig. 4, $Y_i$ denotes the received signals at relay $r_i$, $a_{xiyj}$ is the channel gain from node $x_i$ to node $y_j$, $|a_{xiyj}|^2$ follows an exponential distribution with the parameter $\lambda _{xiyj}$, source $s_i$ transmits with power $E_s\phi _i$ and the additive noise power is normalized as 1. We also assume these nodes to send SI with decode-and-forward (DF) [23]. Then, $P_{si}$ is defined as the outage probability caused by SI, which in the high SNR regime is expressed as

$$\begin{aligned} \begin{aligned} P_{si}=1-\prod (1-P_{si}^{d_i})=\sum P_{si}^{d_i}, \end{aligned} \end{aligned}$$

(39)

where $P_{si}^{d_i}$ denotes the probability of event that destination $d_i$ can’t obtain enough SI. Two cases can be discussed.

Fig. 4

A realistic network example with 3 source-destination pairs

Case 1): Point-to-Point Channel

In this case, source $s_2$’s SI from source $s_1$ and $s_3$ are conveyed in a point-to-point channel. The outage probability $P_{si}^{d_2}$ can be expressed as

$$\begin{aligned} \begin{aligned} P_{si}^{d_2}=&1-\left( 1-\text {Pr}(I(X_1;Y_5)<v_1)\right) \\&\cdot \left( 1-\text {Pr}(I(X_3;Y_8)<v_3)\right) \left( 1-P_{r_5}\right) \left( 1-P_{r_8})\right) \\ =&\text {Pr}(I(X_1;Y_5)<v_1)+\text {Pr}(I(X_3;Y_8)<v_3)+P_{r_5}+P_{r_8}\\ =&\text {Pr}\left( |a_{s1r5}|^2<\frac{2^{v_1}-1}{E_s \phi _1}\right) +\text {Pr}\left( |a_{s3r8}|^2<\frac{2^{v_3}-1}{E_s \phi _3}\right) \\&+P_{r_5}+P_{r_8} \\ =&\frac{(2^{v_1}-1)\lambda _{s1r5}}{E_s\phi _1}+\frac{(2^{v_3}-1)\lambda _{s3r8}}{E_s\phi _3}+P_{r_5}+P_{r_8} \end{aligned} \end{aligned}$$

(40)

where $P_{r_5}$ and $P_{r_8}$ denote the outage probability that information from relay $r_5$ and $r_8$ are conveyed to destination $d_2$ unsuccessfully with rate $v_1$ and $v_3$, respectively. Both $P_{r_5}$ and $P_{r_8}$ are a constant if these nodes conveying SI transmit with a fixed power when DF protocol is employed.

Case 2): MAC

Source $s_1$’s SI are conveyed in a MAC such that the probability $P_{si}^{d_1}$ in the high SNR using Lemma 1.1 in [5] is³

$$\begin{aligned} \begin{aligned} P_{si}^{d_1}=&1-\text {Pr}\left( I(X_{2},X_{3};Y_7)\ge v_{2}+v_3,\right. \\&\left. I(X_{2};Y_7|X_3)\ge v_{2},I(X_{3};Y_7|X_2)\ge v_{3}\right) +P_{r_7}\\ =&\text {Pr}(I(X_{2};Y_7|X_3)< v_{2})+\text {Pr}(I(X_{3};Y_7|X_2)<v_{3})+P_{r_7}\\ =&\text {Pr}\left( |a_{s2r7}|^2<\frac{2^{v_2}-1}{E_s \phi _2}\right) +\text {Pr}\left( |a_{s3r7}|^2<\frac{2^{v_3}-1}{E_s \phi _3}\right) \\&+P_{r_7}\\&\quad =\frac{(2^{v_2}-1)\lambda _{s2r7}}{E_s\phi _1}+\frac{(2^{v_3}-1)\lambda _{s3r7}}{E_s\phi _3}+P_{r_7} \end{aligned} \end{aligned}$$

(41)

where $P_{r_7}$ is the probability that information with rate $v_2+v_3$ from $r_7$ to $d_1$ are forwarded with error, and is also a constant as $P_{r_5}$ and $P_{r_8}$ in (40).

It has been derived that the system outage probability $P_o=P_{nci}+P_{si}$. When $P'_{nci}$ in (34) is used to obtain $P'_{o}=P'_{nci}+P_{si}$ instead of $P_o$, $P'_{o}$ is a similar function as $P'_{nci}$ such that the best response in (36) can still be performed using a simply modification. Therefore SIGA is extended to the networks considering both SI and NCI.

In this section, numerical results are shown to validate our derivations. In Figs. 5 and 6, we show the outage probability performance achieved by SIGA and its convergence without SI in a two hop network with 6 sources. They are used to prove the accurate of (23) and (32).

In Fig. 6, SIGA is shown to be convergent by computer simulations. However it is difficult for us to prove the convergence of SIGA by using theoretical analysis. It is very interesting to prove its convergence by using theoretical analysis in our future works.

Fig. 5

System outage probability in a system with 6 sources, not considering SI

Fig. 6

Convergence properties in the scenario of 6 sources

We set the maximum total system power $E_t=7\text {SNR}\times N_0$, maximum source power $E_s=\text {SNR}\times N_0$ and maximum relay $r_1$ power $E_r=3\text {SNR}\times N_0$. Other parameters in the system with 6 sources are shown in Table 2. In Fig. 5, the simulation results agree well with the derived analytical and simplified results in (23) for both equal-power scheme and SIGA in the high SNR. Thus, it is valid to simplify the system outage probability using (32). The figure also shows that SIGA achieves about 5dB gain in SNR over the equal power scheme at the system outage probability of $10^{-3}$, and it approaches the optimal power allocation scheme obtained using an exhaustive method for (33). Moreover, Fig. 6 shows that SIGA can converge within 4 iterations.

Table 2 Statistic channel parameters in a system with 6 sources

Figure 7 and Table 3 show the system outage probability⁴ for the multiple hop network shown in Fig. 4 with parameters in Table 4, considering both NCI and SI. The maximum total power is set to be $E_t=7\text {SNR}\times N_0$, the maximum source power is $E_s=\text {SNR}\times N_0$ and the maximum relay $r_1$ power is $E_r=2\text {SNR}\times N_0$. Rate $v_1$, $v_2$ and $v_3$ are 0.4, 0.1 and 0.075, respectively. For simplicity, the system is assumed to operate in a full-duplex mode.

Fig. 7

System outage probability in a system shown in Fig. 4, considering SI

Fig. 8

Power factor profile versus $\lambda _{r2r3},\lambda _{r3r4}~\text {and}~\lambda _{r4d3}$ in Fig. 4 when SNR=40dB

Table 3 Outage probability comparison with the optimal scheme SNR=40dB

In Fig. 7, we show system outage probability performance in the scenario of $\lambda _{r2r3}=\lambda _{r3r4}= \lambda _{r4d3}=0.5,~\text {and}~ 20$, respectively. It shows that SIGA always achieves performance gain over the equal power scheme in differen channel conditions. The exhaustion algorithm achieves the optimal solution by using exhaustive search. It is observed that algorithm SIGA proposed in our manuscript achieve some performance gain over the Newton method [28], and is closed to the exhaustion algorithm.

Figure 8 shows curves of $(\phi ,\phi _r)$ versus $\lambda _{r2r3}=\lambda _{r3r4}= \lambda _{r4d3}$ when SNR=40dB. When $\lambda _{r2r3}=\lambda _{r3r4}= \lambda _{r4d3}=0.5$, where channels from $r_2$ to $d_i, i=1,2,3$ are similar, source $s_3$ should transmit with the minimum power since $v_3$ and $\lambda _{s3r1}$ both are the smallest. It is clear that power of $s_3$ should increase if channels from $r_2$ to $d_3$ become worse, i.e., $\lambda _{r2r3}=\lambda _{r3r4}= \lambda _{r4d3}$ is larger. It is because the outage probability of $s_3$ dominates system outage probability, and should be decreased by allocating more power to $s_3$. If $\lambda _{r2r3}=\lambda _{r3r4}= \lambda _{r4d3}$ is further worsen, the outage probability of $s_3$ should be improved by decreasing interference from $s_1$ and $s_2$ instead of increasing $s_3$’s power because $s_3$’s power had arrived at its maximum one. All these are validated in Fig.8. In Fig.9, we show the outage probability of each source in the system shown in Fig.4 when $\lambda _{r2r3}=\lambda _{r3r4}=\lambda _{r4d3}=1$. Equal power scheme degrades the outage probability performance of source $s_1$. A suitable power allocation scheme will improve the performance of $s_1$ at the cost of degrading the outage probability performance of source $s_2$ and $s_3$ by decreasing the powers of source $s_2$ and $s_3$. If the outage probability performance of each source is approximated the same, we can say that the fairness of system is guaranteed. It is clear that SIGA guarantees the fairness of the system in Fig.9, giving each source that communicates with its destination at a similar outage probability.

We also compare SIGA with the optimal power allocation scheme obtained from an exhaustive search in the interval $\phi _1,\phi _2, \phi _3 \in (0,1]$ where $\phi _r=(E_t-\sum \phi _i E_s)/4E_r$ in Table 3. Interestingly, the simulation results show SIGA can approach the optimal power scheme, and it achieves a large performance gain over the equal power scheme.

We show system outage probability of 3 source-destination pair network and 6 source-destination pair network by changing number of relay. The maximum total power is set to be $E_t = 7$SNR$\times N_0$ where SNR=45dB. The maximum source power is $E_s=$SNR$\times N_0$. The topology of 3 source-destination pairs is shown in Fig. 4 in this paper. The maximum relay power is $Er = 2$SNR$\times N_0$. Rate $v_1$, $v_2$ and $v_3$ are 0.4, 0.1 and 0.075, respectively. Static channel parameters are $\lambda _{r2}\lambda _{r3} = \lambda _{r3r4} = \lambda _{r4d3} =$0.5 and Table 4 in our manuscript. For the topology of 6 source-destination pairs, the maximum relay power is $E_s = 3$SNR$\times N_0$. Rates of every source and static channel parameters are shown in Table 2 in this paper. The simulation results are showed in Fig. 10. SIGA approaches the exhaustion algorithm, and achieves a large performance gain over equal power allocation in two topology networks. It is reasonable that system outage probability increases as number of relays increases. We define a system outage if any of sources suffers from an outage, and thus system outage probability of 3 source destination pair network is higher than one of 6 source destination pair network.

Fig. 9

Outage Probability of each source, λ_r2r3 = λ_r3r4 = λ_r2d3 = 1 in the system shown in Fig. 4

Fig. 10

System outage probability versus Number of relay where SNR = 45dB

Table 4 Statistic channel parameters in Fig. 6

6 Conclusion

In this paper, we approximate the expression of the system outage probability for a general network with NAFNC and propose a distributed power allocation scheme to minimize the system outage probability. The approximated system outage probability agrees well with the corresponding simulation results. Moreover, the performance of distributed algorithm approaches that of the optimal power allocation scheme, requiring only SCK at transmitters, and thus it is adequate for a fast varying fading system.

Appendices

Appendix A

Lemma 1

If $f_{2}(w)=\frac{t_{u}t_{v}h(\delta )}{t_{p}w+t_{v}h(\delta )}$ where $t_{u},t_{v},t_{p} \in \mathbb {R}^{+}$, then

$$\begin{aligned} \begin{aligned}&\lim _{h(\delta ) \rightarrow 0}\frac{1}{h(\delta )}\left( e^{(t_{u}+t_{v})h(\delta )}\int _{0}^{\infty }f_{2}(w)e^{-t_{u}w}dw \right) \\&\quad =\left( -c-\ln \left( \frac{t_{u}t_{v}}{t_{p}}h(\delta )\right) \right) \frac{t_{u}t_{v}}{t_{p}}, \end{aligned} \end{aligned}$$

(42)

where $c\approx 0.577$ is Euler Lorenzo Mascheroni constant.

Proof

Expression of exponential integral is shown as

$$\begin{aligned} \begin{aligned} E_{1}(\alpha )&=\int _{\alpha }^{\infty }\frac{1}{w}e^{-w}dw =-c-\ln (\alpha )+\sum _{k=1}^{\infty }\frac{(-1)^{k+1}\alpha ^{k}}{kk!}. \end{aligned} \end{aligned}$$

(43)

Therefore,

$$\begin{aligned} \begin{aligned}&\lim _{h(\delta ) \rightarrow 0} \frac{1}{h(\delta )}\left( e^{(t_{u}+t_{v})h(\delta )}\int _{0}^{\infty }f_{2}(w)e^{-t_{u}w}dw \right) \\&\quad =\lim _{h(\delta ) \rightarrow 0}\left( 1+\mathcal {O}(h(\delta ))\right) \left( \int _{0}^{\infty }\frac{e^{-t_{u}w}}{w+h(\delta )t_{v}t_{p}^{-1}}dw\right) \frac{t_{u}t_{v}}{t_{p}} \\&\quad =\lim _{h(\delta ) \rightarrow 0} \left( \int _{t_{u}t_{v}t_{p}^{-1}h(\delta )}^{\infty } \frac{1}{w}e^{-w}dw\right) \frac{t_{u}t_{v}}{t_{p}}\\&\quad =\lim _{h(\delta ) \rightarrow 0} E_{1}\left( \frac{t_{u}t_{v}}{t_{p}}h(\delta ) \right) \frac{t_{u}t_{v}}{t_{p}} \\&\quad =\left( -c-\ln \left( \frac{t_{u}t_{v}}{t_{p}}h(\delta )\right) \right) \frac{t_{u}t_{v}}{t_{p}}. \end{aligned} \end{aligned}$$

(44)

The lemma follows. $\square$

Lemma 2

If $k\in \mathcal {N}$, $\lambda _{i}\in \mathcal {R}^+$, $1 \le i \le k$, and $\lambda _{i}\ne \lambda _{j}$ for any $i\ne j$, then

$$\begin{aligned} \begin{aligned} \sum _{i=1}^{k}\frac{\lambda _{i}^{l}}{\prod _{j \ne i}(\lambda _{j}-\lambda _{i})}=0, \end{aligned} \end{aligned}$$

(45)

where $0 \le l \le k-2$ and $l \in \mathcal {N}$.

Proof

We first show a linear equation as

$$\left( {\begin{array}{*{20}c} {\lambda _{1}^{0} } & {\lambda _{2}^{0} } & \ldots & {\lambda _{k}^{0} } \\ {\lambda _{1}^{1} } & {\lambda _{2}^{1} } & \ldots & {\lambda _{k}^{1} } \\ \vdots & \vdots & \ddots & \vdots \\ {\lambda _{1}^{{k - 2}} } & {\lambda _{2}^{{k - 2}} } & \ldots & {\lambda _{k}^{{k - 2}} } \\ {\lambda _{1}^{{k - 1}} } & {\lambda _{2}^{{k - 1}} } & \ldots & {\lambda _{k}^{{k - 1}} } \\ \end{array} } \right)X = \left( {\begin{array}{*{20}c} 0 \\ 0 \\ \vdots \\ 0 \\ {( - 1)^{{k + 1}} } \\ \end{array} } \right)$$

(46)

and then equivalently transform the linear equation as

(47)

Clearly, the solution of the above linear equation is

$$\begin{aligned} \begin{aligned} x_{i}=\left( \prod _{j \ne i}(\lambda _{j}-\lambda _{i}) \right) ^{-1} \end{aligned} \end{aligned}$$

(48)

Substitute (48) into (46), we have

$$\begin{aligned} \begin{aligned} \sum _{i=1}^{k}\frac{\lambda _{i}^{l}}{\prod _{j \ne i}(\lambda _{j}-\lambda _{i})}=0. \end{aligned} \end{aligned}$$

(49)

Thus, the lemma holds. $\square$

Lemma 3

If $k\in \mathcal {N}$, $k\ge 2$ and $t_{u},t_{v},t_{i}\in \mathbb {R}^{+}~ \forall i$, then

$$\begin{aligned} \begin{aligned}&\lim _{h(\delta ) \rightarrow 0}\frac{1}{h(\delta )}\int _{0}^{\infty }\frac{(-1)^{k+1}t_{v}^{k}h^{k}(\delta )}{\prod _{i=1}^{k} \left( t_{i}w+t_{v}h(\delta )\right) }t_{u}e^{-t_{u}w}dw\\&\quad =\left( \sum _{i=1}^{k}\frac{t_{i}^{k-2}\ln t_{i}}{\prod _{j \ne i}(t_{j}-t_{i})}\right) t_{u}t_{v} \end{aligned} \end{aligned}$$

(50)

Proof

We have

$$\begin{aligned} \begin{aligned}&\lim _{h(\delta ) \rightarrow 0}\frac{1}{h(\delta )}\int _{0}^{\infty }\frac{(-1)^{k+1}t_{v}^{k}h^{k}(\delta )}{\prod _{i=1}^{k} \left( t_{i}w+t_{v}h(\delta )\right) }t_{u}e^{-t_{u}w}dw\\&\quad = \lim _{h(\delta ) \rightarrow 0}\frac{t_{u}t_{v}}{\prod _{i=1}^{k}t_{i}}\sum _{i=1}^{k}\int _{0}^{\infty }\frac{\prod _{j \ne i}(t_{i}^{-1}-t_{j}^{-1})^{-1}}{w+t_{v}h(\delta )t_{i}^{-1}}e^{-t_{u}w}dw\\&\quad =\lim _{h(\delta ) \rightarrow 0}t_{u}t_{v}\left( \sum _{i=1}^{k}f_{3}(t_{i})\int _{0}^{\infty }\frac{1}{w+\frac{t_{v}h(\delta )}{t_{i}}}e^{-t_{u}w}dw\right) \\&\qquad \overset{(a)}{=}\lim _{h(\delta ) \rightarrow 0}t_{u}t_{v}\left( \sum _{i=1}^{k}f_{3}(t_{i})\left( -c-\ln \left( \frac{t_ut_v}{t_i}h(\delta )\right) +\mathcal {O}(h(\delta ))\right) \right) \\&\quad =G_{1}\sum _{i=1}^{k}f_{3}(t_{i})+\left( \sum _{i=1}^{k}\frac{t_{i}^{k-2}\ln t_{i}}{\prod _{j \ne i}(t_{j}-t_{i})}\right) t_{u}t_{v}\\&\qquad \overset{(b)}{=}\left( \sum _{i=1}^{k}\frac{t_{i}^{k-2}\ln t_{i}}{\prod _{j \ne i}(t_{j}-t_{i})}\right) t_{u}t_{v}, \end{aligned} \end{aligned}$$

(51)

where $G_{1}=-\left( c+\ln (t_{u}t_{v}h(\delta ))\right) t_{u}t_{v}h(\delta ))~\text {and}~ ~f_{3}(t_{i})=\frac{t_{i}^{k-2}}{\prod _{j \ne i}(t_{j}-t_{i})}$. In (51), please see (44) in Appendix A for equation (a), and the equation (b) holds since $\sum _{i=1}^{k}f_{3}(t_{i})=0$ in Lemma 2 in Appendix A. $\square$

Appendix B

Lemma 4

For $1 \le i \le M-1$, where $M \in \mathcal {N}$, and $t_i\ne t_{j}$ for any $i\ne j$, it assumes that $u,v,q_{i}$ are independent exponentially-distributed with parameters $t_{u},t_{v},t_{i}$, respectively. If $c\approx 0.577$ denotes Euler Lorenzo Mascheroni constant and $P_{e}{\mathop {=}\limits ^{{\Delta }}} \text {Pr}\left( \frac{uv}{u+v+\sum _{i=1}^{M-1}q_{i}+\delta }<h(\delta )\right)$, then

$$\begin{aligned} \begin{aligned}&\lim _{\delta \rightarrow 0}\frac{1}{h(\delta )}P_{e}=\left\{ \begin{array}{rl} &{}\quad t_{u}+t_{v}-f_{1}(t_1),~~~~~~~~~~~~M = 2\\ &{}\quad t_{u}+t_{v}-\sum _{i=1}^{M-1}f_{1}(t_{i})+\\ {} &{}\left( \sum _{l=2}^{M-1}\sum _{1 \le k_{1} \le \cdots \le k_{l} \le M-1}\right. \\ &{}\qquad \left. \sum _{s=1}^{l}\frac{t_{k_s}^{l-2}\ln t_{k_s}}{\prod _{j \ne s}^{l}(t_{k_j}-t_{k_s})}\right) t_{u}t_{v},~ M \ge 3. \end{array} \right. \end{aligned} \end{aligned}$$

(52)

where $f_{1}(t_{i})=\frac{t_{u}t_{v}}{t_{i}}\left( c+\ln \frac{\lambda _{u}\lambda _{v}h(\delta )}{\lambda _{i}}\right)$, $\delta \rightarrow 0^+$, and $h(\delta )$ is continuous function at $\delta =0$.

Proof

Let $w=u-h(\delta )$. Hence the probability density function (PDF) of w is

$$\begin{aligned} f(w)=t_{u}e^{-t_{u}(w+h(\delta ))},-h(\delta ) \le w \le \infty \end{aligned}$$

(53)

We have

$$\begin{aligned} \begin{aligned}&\lim _{\delta \rightarrow 0 }\frac{1}{h(\delta )}\text {Pr}\left( \frac{uv}{u+v+\sum _{i=1}^{M-1}q_{i}+\delta }<h(\delta )\right) \\&\quad =\lim _{\delta \rightarrow 0}\frac{1}{h(\delta )}\text {Pr}\left( uv<(u+v)h(\delta )+\sum _{i=1}^{M-1}q_{i}h(\delta )+\delta h(\delta ) \right) \\&\quad =\lim _{\delta \rightarrow 0}\frac{1}{h(\delta )}\text {Pr}\left( (u-h(\delta ))v<uh(\delta )+\sum _{i=1}^{M-1}q_{i}h(\delta )+\delta h(\delta ) \right) \\&\quad =\lim _{\delta \rightarrow 0}\frac{1}{h(\delta )}\text {Pr}(u\le h(\delta )) + G_{2} \\&\quad =\frac{1}{h(\delta )}(1-e^{-t_{u}h(\delta )})+G_{2}, \end{aligned} \end{aligned}$$

(54)

where

$$\begin{aligned} \begin{aligned} G_{2}=&\lim _{\delta \rightarrow 0}\frac{1}{h(\delta )}\text {Pr}\left( v<\frac{(u+\sum _{i=1}^{M-1}q_{i}+\delta )h(\delta )}{u-h(\delta )},u>h(\delta )\right) \\ =&\lim _{\delta \rightarrow 0}\frac{1}{h(\delta )}\text {Pr}\left( v<\frac{(u+\sum _{i=1}^{M-1}q_{i}+\delta )h(\delta )}{w},w>0\right) \\ =&\lim _{\delta \rightarrow 0} \frac{1}{h(\delta )}\int \dots {\int _{\begin{array}{c} {v<G_{3}}\\ {w>0 q_{i}>0,\forall i} \end{array}}}f(v)f(w)\prod _{i=1}^{M-1}f(q_{i})dvdw\prod _{i=1}^{M-1}dq_{i}\\ =&\lim _{\delta \rightarrow 0} \frac{1}{h(\delta )}\int \cdots \int \left( 1-e^{-t_{v}G_{3}}\right) \prod _{i=1}^{M-1}f(q_{i})f(w)dw\prod _{i=1}^{M-1}dq_{i} \\ =&\lim _{\delta \rightarrow 0} \frac{1}{h(\delta )}\left( \int _{0}^{\infty }\dots \int _{0}^{\infty } f(w)\prod _{i=1}^{M-1}f(q_{i})dw\prod _{i=1}^{M-1}dq_{i}\right. \\&\left. -\int _{0}^{\infty } \dots \int _{0}^{\infty }e^{-t_{v}G_{3}} f(w)\prod _{i=1}^{M-1}f(q_{i})dw\prod _{i=1}^{M-1}dq_{i}\right) \\ =&\frac{1}{h(\delta )}e^{-t_{v}h(\delta )}-\lim _{\delta \rightarrow 0}\frac{1}{h(\delta )} t_{u}e^{-(t_{u}+t_{v})h(\delta )}\times \\&\int _{0}^{\infty }\prod _{i=1}^{M-1}\left( \frac{t_{i}}{t_{i}+t_{v}h(\delta )w^{-1}}\right) e^{-t_{u}w-t_{v}\left( \frac{\delta h(\delta )+h(\delta )^2}{w}\right) }dw, \end{aligned} \end{aligned}$$

and

$$\begin{aligned} G_{3}=h(\delta )+\frac{\left( \sum _{i=1}^{M-1}q_{i}+\delta +h(\delta )\right) h(\delta )}{w}. \end{aligned}$$

(55)

Let $f_{2}(w)=t_{u}w+t_{v}\frac{\delta h(\delta )+h^2(\delta )}{w}$. Hence

$$\begin{aligned} \begin{aligned}&\lim _{\delta \rightarrow 0}\frac{1}{h(\delta )}P_{e}=\lim _{\delta \rightarrow 0}\frac{1}{h(\delta )}\text {Pr}\left( \frac{uv}{u+v+\sum _{i=1}^{M-1}q_{i}+\delta }<h(\delta )\right) \\&\quad =\lim _{\delta \rightarrow 0}\frac{1}{h(\delta )}\left( 1-e^{-(t_{u}+t_{v})h(\delta )}\int _{0}^{\infty }t_{u}e^{-f_{2}(w)} dw\right) \\&\qquad +\lim _{\delta \rightarrow 0}\frac{1}{h(\delta )} t_{u}e^{-(t_{u}+t_{v})h(\delta )} \times \\&\qquad \int _{0}^{\infty } \left( 1-\prod _{i=1}^{M-1}\left( \frac{t_{i}}{t_{i}+t_{v}h(\delta )w^{-1}}\right) \right) e^{-f_{2}(w)}dw. \end{aligned} \end{aligned}$$

(56)

Let $\delta h(\delta )+h^{2}(\delta )=0$ since $\delta h(\delta )+h^{2}(\delta )=\mathcal {O}(\delta ^{2})$. According to Lemma 1.2 in [5], we get

$$\begin{aligned} \begin{aligned} \lim _{\delta \rightarrow 0}\frac{1}{h(\delta )}P_{e}&=t_{u}+t_{v}+\lim _{h(\delta ) \rightarrow 0}\frac{1}{h(\delta )} t_{u}e^{-(t_{u}+t_{v})h(\delta )} \times \\&\quad \int _{0}^{\infty }\left( 1-\prod _{i=1}^{M-1}\left( \frac{t_{i}}{t_{i}+t_{v}h(\delta )w^{-1}}\right) \right) e^{-t_{u}w}dw. \end{aligned} \end{aligned}$$

(57)

With Lemma 1, 3 in Appendix A and the following equation

$$\begin{aligned} \begin{aligned}&1-\prod _{i=1}^{M-1}\left( \frac{t_{i}}{t_{i}+t_{v}h(\delta )w^{-1}}\right) \\&\quad =\sum _{l=1}^{M-1}\sum _{1 \le k_{1} \dots \le k_{l} \le M-1} \frac{(-1)^{l+1}(t_{v}h(\delta ))^{l}}{\prod _{i=1}^{l}(t_{k_i}w+t_{v}h(\delta ))}, \end{aligned} \end{aligned}$$

(58)

we get the results in (52). $\square$

C Proof of Theorem 1

Proof

This theorem is completed with two steps. We first prove there exists $\lim _{\forall t_{i} \rightarrow t_{a}}f(t_{1},t_{2},\dots \,t_{k})$, and then calculate the limit with a given convergence direction.

In (50), the left term is assumed to be $\zeta _{1}(t_{1},t_{2},\dots ,t_{k})$ and the right term is $\zeta _{2}(t_{1},\lambda _{2},\dots ,t_{k})$. Clearly, $\zeta _{1}(t_{1},t_{2},\dots ,t_{k})$ is continuous such that $\lim _{\Delta _{i}\rightarrow 0, \forall i}\zeta _{1}(t_{a}+\Delta _{1},t_{a}+\Delta _{2},\dots ,t_{a}+\Delta _{k})=\zeta _{1}(t_{a},t_{a},\dots ,t_{a})$. Using (50), we have $\lim _{\Delta _{i}\rightarrow 0, \forall i}\zeta _{2}(t_{a}+\Delta _{1},t_{a}+\Delta _{2},\dots ,t_{a}+\Delta _{k})=\lim _{\Delta _{i}\rightarrow 0, \forall i}\zeta _{1}(t_{a}+\Delta _{1},t_{a}+\Delta _{2},\dots ,t_{a}+\Delta _{k})=\zeta _{1}(t_{a},t_{a},\dots ,t_{a})$. Therefore, $\lim _{\forall i,~ t_i\rightarrow t_a}f(t_1,t_2 ,\ldots ,t_k)$ converges to a finite constant. Next we assume that $t_{i}=t_{a}+i\triangle$ and calculate the limit as

$$\begin{aligned} \begin{aligned} \lim _{\forall t_{i} \rightarrow t_{a}}f(\mathbf{t} )&=\lim _{\forall t_{i} \rightarrow t_{a}}\sum _{i=1}^{k}\frac{t_{i}^{k-2}\ln t_{i}}{\prod _{j \ne i}(t_{j}-t_{i})} \\&=\lim _{\triangle \rightarrow 0}\left( \sum _{i=1}^{k}\frac{(t_{a}+i\triangle )^{k-2}\ln (t_{a}+i\triangle )}{\prod _{j \ne i}(j-i)}\right) /\triangle ^{k-1} \\&=\frac{1}{(k-1)t_{a}}\sum _{i=1}^{k}\frac{i^{k-1}}{\prod _{j\ne i}(j-i)}\\&=\frac{1}{(k-1)(k-1)!t_{a}}\sum _{i=0}^{k-1}{k-1 \atopwithdelims ()i}(i+1)^{k-1}(-1)^{i}, \end{aligned} \end{aligned}$$

(59)

where the second equation is obtained by differentiating numerator and denominator of the fraction for $k+1$ times according to L’hospital rule [22]. Then we have

$$\begin{aligned} \begin{aligned} \sum _{i=0}^{j}{j \atopwithdelims ()i}(i+1)^{j}(-1)^{i}&=\frac{d^{j}}{dt^{j}}\sum _{i=0}^{j}{j \atopwithdelims ()i}e^{(i+1)t}(-1)^{i}\bigg |_{t=0}\\&=(-1)^j\frac{d^{j}}{dt^{j}}\left( \sum _{i=0}^{j}{j \atopwithdelims ()i} \left( e^{t}\right) ^i(-1)^{j-i}\right) e^t\bigg |_{t=0} \\&=(-1)^{j}\frac{d^{j}}{dt^{j}}\left( e^{t}(e^{t}-1)^{j}\right) \bigg |_{t=0}\\&=(-1)^{j}\frac{d^{j}}{dt^{j}}\left( t^{j}+\mathcal {O}(t^{j+1})\right) \bigg |_{t=0} =(-1)^{j}j!, \end{aligned} \end{aligned}$$

(60)

where $i,j\in \mathcal {N}$ and $i\le j$. With (59) and , the theorem follows. $\square$

D Proof of Theorem 2

Proof

Without loss of generality, let $i=1$. Considering $\sum _{i=1}^k f_3(t_i)=0$ in Lemma 3 in Appendix A, we get

$$\begin{aligned} \begin{aligned} f(\mathbf{t} )&=\sum _{i=2}^{k}\frac{t_{i}^{k-2}\ln t_i}{\prod _{j\ne i}(t_{j}-t_{i})}-\left( \sum _{i=2}^{k}\frac{t_{i}^{k-2}}{\prod _{j \ne i}(t_{j}-t_{i})}\right) \ln t_{1}\\&=\sum _{i=2}^{k}\frac{t_{i}^{k-2}(\ln t_{i}-\ln t_{1})}{\prod _{j \ne i}(t_{j}-t_{i})}, \end{aligned} \end{aligned}$$

(61)

and then differentiate (61) for variable $t_{1}$ as

$$\begin{aligned} \begin{aligned}&\frac{\partial f(\mathbf{t} )}{\partial t_{1}} =\sum _{i=2}^{k}\frac{t_{i}^{k-2}}{\prod _{j \ne i}(t_{j}-t_{i})}\left( \frac{\ln t_{i}-\ln t_{1}}{t_{i}-t_{1}}-\frac{1}{t_{1}}\right) \\&\quad =\sum _{i=1}^{k} \frac{t_{i}^{k-2}}{\prod _{j \ne i}(t_{j}-t_{i})}\lim _{t_{k+1}\rightarrow t_{1}}\left( \frac{\ln t_{i}-\ln t_{k+1}}{t_{i}-t_{k+1}}\right) \\&=\lim _{t_{k+1}\rightarrow t_{1}}\sum _{i=1}^{k}\left( \frac{t_{i}^{k-2}\ln t_{k+1}}{\prod _{j \ne i}(t_{j}-t_{i})(t_{k+1}-t_{i})}\right. -\\&\quad \left. \frac{t_{i}^{k-2}\ln t_{i}}{\prod _{j \ne i}(t_{j}-t_{i})(t_{k+1}-t_{i})}\right) \\&=-\lim _{t_{k+1}\rightarrow t_{1}}\sum _{i=1}^{k+1}\frac{t_{i}^{k-2}\ln t_{i}}{\prod _{j \ne i}(t_{j}-t_{i})}, \end{aligned} \end{aligned}$$

(62)

where the second equation holds since $\lim _{t_{k+1} \rightarrow t_{1}}\frac{\ln t_{k+1}-\ln t_{1}}{t_{k+1}-t_{1}}=\frac{1}{t_{1}}$. Construct a function $g(x)=x^{k-1}\ln x$ and assume there exist $k+1$ points $(t_{i},g(t_{i}))$ for $1\le i \le k+1$. The Lagrange interpolation polynomial of g(x) is expressed as

$$\begin{aligned} \begin{aligned} L_{k+1}(g,x)=\sum _{i=1}^{k+1}g(t_{i})\frac{\prod _{j\ne i}(x-t_{j})}{\prod _{j\ne i}(t_{i}-t_{j})}. \end{aligned} \end{aligned}$$

(63)

It is shown that

$$\begin{aligned} \begin{aligned} L_{k+1}(g,0^+)=\prod _{l=1}^{k+1}t_{l}\sum _{i=1}^{k+1}\frac{t_{i}^{k-2}\ln t_{i}}{\prod _{j \ne i}(t_{j}-t_{i})}. \end{aligned} \end{aligned}$$

(64)

Define $t_{\min }\rightarrow 0^+$ and $t_{\max }=\max (\mathbf{t} )$. The error in Lagrange interpolation is

$$\begin{aligned} \begin{aligned} R(g,0^+)&=g(0^+)-L_{k+1}(g,0^+)\\&=\frac{(-1)^{k+1}g^{(k+1)}(\varepsilon )}{(k+1)!}\prod _{i=1}^{k+1}t_{i}\\&=\frac{(-1)^k}{(k+1)k\varepsilon ^2}\prod _{i=1}^{k+1}t_{i} \end{aligned} \end{aligned}$$

(65)

where $\varepsilon \in [t_{\min },t_{\max }]$ and $g^{(k+1)}$ is the $(k+1)$-th-order derivative of function g. With (64) and (65), we obtain

$$\begin{aligned} \begin{aligned} \sum _{i=1}^{k+1}\frac{t_{i}^{k-2}\ln t_{i}}{\prod _{j \ne i}(t_{j}-t_{i})}&=\frac{1}{\prod _{i=1}^{k+1}t_{i}}\left( g(0^+)-R(g,0^+)\right) \\&=\frac{(-1)^{k+1}}{(k+1)k\varepsilon ^2}, \end{aligned} \end{aligned}$$

(66)

where $g(0^+)=\lim _{x \rightarrow 0^+}x^{k+1}\ln x=0$.

Considering (62) and (66), the theorem holds. $\square$