# Queue Size Distribution on a New ND Policy Geo/G/1 Queue and Its Computation Designs

Authors: Rongxiu Wang
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

This paper examines a new ND policy in the discrete-time Geo/G/1 queue. Under this ND policy, the idle server restarts its service when the N and D policies are simultaneously satisfied. By two classifications of the customers, the probability-generating function and the probabilistic analysis, the steady-state queue size distributions at a departure time and an arbitrary timet+ are studied. Finally, the theoretical results are applied to the power-saving problem of a wireless sensor network. To improve model universality and numerical slowness, some computation designs are carried out. Under the N, D, and two ND policies, the numerical experiments are presented to obtain the optimal policy thresholds and the corresponding minimum power consumptions are compared.


---

## Body

## 1. Introduction

In this work, we introduce a new ND policy in the discrete-time Geo/G/1 queue, obtain the steady-state queue size distribution, and conduct some computation designs in the minimum power consumption of a wireless sensor network. Under the new ND policy (called the ND policy 1), when the number of the customers in the queueing system reaches at leastN and, at the same time, the sum of the service time periods of all waiting customers is greater than a given nonnegative integer D, the idle server begins to offer its service for the waiting customers.Recently, for the ND-policy discrete-time Geo/G/1 queue, Gu et al. [1] and Lan and Tang [2] obtained the steady-state queue size distribution at an arbitrary time and its stochastic decomposition. In the above two published papers, since the service time periods of the customers who arrive during the server idle period are assumed to be independent of each other, the genuine D-policy is not actually implemented. For this flaw in [1, 2], Liu et al. [3] revisited the ND policy considered in [1, 2] (called the ND policy 2) in the discrete-time Geo/G/1 queue, obtained the main queueing measures, and applied the theoretical results to the power-saving optimization of a wireless sensor node. Under the ND policy 2, either of the N and D policies is first satisfied and then the service will restart. In this case, frequent setup may cause a high setup power consumption. Hence, the ND policy 2 may be ineffective when the setup power consumption is much larger than the holding power consumption of the data packet (customer) in a busy cycle. If we adopt the ND policy 1 presented by this work, which begins service when the N and D policies are satisfied at the same time, then a lower setup power consumption can be caused. The reason is that relative to the ND policy 2 in [3], the ND policy 1 can decrease the setup number of the radio server. Thus, for a high setup power consumption, the ND policy 1 will consume less power than the ND policy 2 in [3]. This motivates us to study the queue size distribution of the discrete-time queue with the ND policy 1 for the power-saving optimization of a wireless sense node.It should be noted that this work and Liu et al. [3] are two different research studies. Above all, from the definitions of two ND policies mentioned above, the ND policies considered in both research studies are different. Next, in both research studies, the expression and the concrete analysis of the same queueing measure are different. It is seen from this work and [3] that our discussion and mathematical derivation are more difficult and complex than those in [3]. Finally, in both research studies, the computation designs and the optimization comparison in the power-saving control of a sensor node are different. Numerically, the study in [3] only used the geometrically distributed transmission time to compare the superiority of the optimal N policy, D policy, and ND policy 2, while our comparison utilized arbitrary probability distributions and presented an optimization procedure for the optimal ND policy.The contributions of this paper are threefold. First, this study provides a new ND policy in the Geo/G/1 queue. Furthermore, our theoretical results agree with those in the existing N policy and genuine D policy queues (see Remark1), which shows our work has studied the genuine D policy. Second, as far as known to the author, for the existing papers on the discrete-time queues with the N policy and genuine D policy, the queue size distribution obtained in this work is new. It is useful and important when a power consumption function is constructed to analyze the optimal ND policy at a minimum power value. Third, this research conducts some computation designs for arbitrarily distributed transmission time periods, presents a concrete optimization procedure, and numerically compares the minimum power consumption of a wireless sensor node based on the optimal N policy, D policy, ND policy 1, and ND policy 2. It is easy and practical for the network practitioners to understand and use these results.Common methods in the queueing models include the imbedded Markov chain [4], the supplementary variable [5], the theory of matrix-geometric solution [6, 7], and the probability decomposition [1, 2]. These approaches are used to analyze the queue size distribution based on the assumption of independent and identically distributed (i.i.d.) service time periods. However, in the discrete-time queues involving the D policy, the service time periods of the customers who arrive during the idle period are not independent while the service time periods of the customers who arrive during the busy period are independent (see Section 3). This property of the service time periods makes the stochastic decomposition of the steady-state queue size [8] not hold. Therefore, the above approaches become too complicated to be solved especially when they are used to deal with the queue size distribution of the D policy queues. As far as known to the author, no papers with the D-policy queues were found by means of the above methods. Lately, Gu et al. [1] and Lan and Tang [2] applied a probability decomposition method to obtain the queue size distributions in the discrete-time Geo/G/1 queues with the ND policy 2. But, they avoided the dependence of the service time periods of the customers who arrive during the idle period, and the D policy they considered was not a genuine D policy, which was pointed out by Liu et al. [3, 9].Our analysis method is based on the difference of the service time periods of the customers arriving during the idle and busy periods. By two classifications of the customers, the probability-generating function and the probabilistic analysis, the steady-state queue size distributions at a departure time and an arbitrary timet+ are studied, which cannot usually be obtained by the common methods mentioned above. The results for two special cases (see Remark 1) and numerical experiments show that our analysis method is effective and available for the complex discrete-time queues involving the genuine D policy and this method operates in the continuous situation as well.The rest of this paper is organized as follows: Section2 presents the model description and some notations. In Sections 3 and 4, based on some preliminaries, we analyze the queue size distribution. In the energy-saving problem of a wireless sensor network, Section 5 conducts some computation designs and then numerically compares the superiority of the optimal N, D, and two ND policies at a minimum power consumption. Conclusions are drawn in Section 6.


## 2. Model Description and Some Notations

The model discussed in this paper is under theLAS-DA (late arrival system with delayed access) setup [10]. That is to say, a potential arrival can only take place in t−,t,t=0,1,2,…, and a potential departure can only occur in t,t+,t=1,2,…, where t− represents the instant immediately before t and t+ represents the instant immediately after t. We do not permit a departure at such a time point for a customer who has just arrived at the instant previously to an empty system. The various time epochs involved in our model can be viewed through a self-explanatory figure (see Figure 1). The detailed description of the model is given as follows:(1)
The interarrival time periods of customers, denoted byτi,i=1,2,…, are independent and geometrically distributed with probability mass function (PMF) Prτi=k=p1−pk−1,k≥1, and probability-generating function (PGF) τz=pz/1−1−pz,z≤1.(2)
The service time periods,Sn,n=1,2,…, are independent and identically distributed (i.i.d.) with PMF sx=PrSn=x,x=1,2,…,s0=0 and PGF Sz=∑x=1∞sxzx,z≤1. The mean service time ES and the second moment ES2 are finite. The customers are served based on their arriving order. The server can serve only one customer at a time. A customer that arrives and finds the server busy must wait in the queue until the server is available. All the customers arriving at the system are assumed to be eventually served, i.e., the traffic intensity ρ=pES<1.(3)
The idle server resumes its service if the following two conditions are simultaneously met (ND policy 1): (i) at leastN customers accumulate in the system and (ii) the service time backlog (i.e., the sum of the service times) of all waiting customers exceeds a given nonnegative integer D.Figure 1
Various time epochs in a late arrival system with delayed access.WhenN=1, the ND policy 1 becomes the pure D policy, and when D+1≤N, we always get the pure N policy. Hence, we discuss the case of 1≤N≤D+1,whereN=1,2,…andD=0,1,2,… so that the N policy and D policy both control the startup of the server. We use some notations as follows:Xz=∑iziPrX=i,z≤1: the PGF of random variable XEX: the mean of random variable XCkj,0≤j≤k: Ckj=k!/j!k−j!x¯=1−x,0<x<1: the complementary value for an arbitrary real number x∑k=ij=0, if i>j: the sum is equal to zero if the subscript i exceeds the superscript jSkx=PrS1+S2+⋯+Sk≤x,1≤k≤x: the distribution function of the k-fold convolution of service time with itself S0x=1,x≥0,Skx=0,k>x≥1skx=PrS1+S2+⋯+Sk=x,1≤k≤x: the probability mass function (PMF) of the k-fold convolution of service time with itself s1x=sx,skx=0,k>x≥1Sk−1D−SkD=PrS1+S2+⋯+Sk−1≤D<S1+S2+⋯+Sk,k≥2: the probability that the threshold value D is first exceeded by the service time of the kth customerQN,D: the number of the customers at the start of a busy periodΦN,D: the service time backlog of all waiting customers at the start of a busy period


## 3. Preliminaries

For convenience of analysis, we define the idle period, denoted byIN,D, as the time length that starts when the system becomes empty and terminates when the idle server starts to serve customers. The busy period, denoted by BN,D, represents the time length which starts when the idle period completes and ends when the system is empty. The sum of the busy period and the next idle period is defined as the busy cycle, denoted by CN,D.In the model description, although the service time periods in the idle and busy periods are assumed to be i.i.d., the D policy determines that the service time periods of the customers who arrive during the idle period,S1,S2,…,SQN,D, are conditionally dependent. In fact, when QN,D=k,k=N+1,N+2,…,D+1, we have ∑i=1k−1Si≤D<∑i=1kSi, and when QN,D=N, we get ∑i=1NSi>D. Here, two inequations show the above conditional dependence. This makes the queue size distribution not be derived by the stochastic decomposition of the queue size [8], and the analysis is difficult by the common methods.To get the queue size distribution, we denote the customer who arrives during the idle period as IC and express the customer who arrives during the busy period as BC. Through this classification, we will derive the PGF and mean of the queue size distribution. Above all, we study the queue size and service time backlog at the start of a busy period and the idle and busy periods.


### 3.1. The Queue Size at the Start of a Busy Period

At the start of a busy period, we havekN+1≤k≤D+1 customers if and only if the D is exceeded by the kth customer and this occurs with probability Sk−1D−SkD (see the notations in Section 2). The busy period starts with N customers if and only if the sum of the service time periods of these N customers is larger than or equal to D+1. Thus, the PMF and PGF of QN,D are, respectively, given by(1)PrQN,D=k=Sk−1D−SkD,k=N+1,N+2,…,D+1,1−SND,k=N,(2)QN,Dz=∑k=ND+1PrQN,D=kzk=zN−1−z∑k=NDzkSkD,z≤1.From (2), the first and second moments of QN,D are, respectively, obtained as(3)EQN,D=dQN,Dzdz|z=1=N+∑k=NDSkD,(4)EQN,DQN,D−1=d2QN,Dzdz2|z=1=NN−1+2∑k=NDkSkD.


### 3.2. The Service Time Backlog at the Start of a Busy Period

The service time backlog isx≥D+1 at the start of a busy period if and only if the sum of the service time periods of the N customers is equal to x, or the sum of the service time periods of the first kN≤k≤D customers is n,n=k,k+1,…,D, and the D is exceeded by the next customer. Summing for all possible k and n yields the PMF of ΦN,D as(5)PrΦN,D=x=sNx+∑k=ND∑n=kDsknsx−n,x=D+1,D+2,…,which gives the PGF of ΦN,D as(6)ΦN,Dz=∑x=D+1∞zxsNx+∑k=ND∑x=D+1∞zx∑n=kDsknsx−n,where the second term of right hand side (RHS) in (6) can be expressed as(7)∑k=ND∑x=D+1∞zx∑n=kDsknsx−n=∑k=ND∑x=D+1∞zx∑n=kxsknsx−n−∑n=D+1xsknsx−n=∑k=ND∑x=D+1∞zxsk+1x−∑k=ND∑n=D+1∞zn∑x=n∞zx−nsknsx−n=∑k=ND∑x=D+1∞zxsk+1x−Sz∑k=ND∑n=D+1∞znskn.Putting (7) into (6) yields(8)ΦN,Dz=∑x=D+1∞zxsNx+∑k=N+1D+1∑x=D+1∞zxskx−Sz∑k=ND∑n=D+1∞znskn=∑x=D+1∞zxsD+1x+1−Sz∑k=ND∑n=D+1∞znskn=SzD+1+1−Sz∑k=ND∑n=D+1∞znskn.Now, using (8), we get the first and second moments of ΦN,D as(9)EΦN,D=dΦN,Dzdz|z=1=ESN+∑k=NDSkD,(10)EΦN,DΦN,D−1=d2ΦN,Dzdz2|z=1=ESS−1N+∑k=NDSkD+ESDD+1ES−2∑k=ND∑n=D+1∞nskn.


### 3.3. The Idle Period

Under the ND policy 1, ifQN,D=n,N+1≤n≤D+1, then the idle period IN,D=τ1+τ2+⋯+τn with probability Sn−1D−SnD. If QN,D=N, then the idle period IN,D=τ1+τ2+⋯+τN with probability 1−SND. Thus, we easily get the PGF and mean of the idle period as follows:(11)IN,Dz=∑n=N+1D+1τznSn−1D−SnD+τzN1−SND=QN,Dτz,(12)EIN,D=ddzIN,Dz|z=1=1pN+∑k=NDSkD,where τz=pz/1−p¯z stands for the PGF of interarrival time periods τi,i≥1.


### 3.4. The Busy Period and Busy Cycle

DefineLς as the departure point queue size of the last departing IC during the busy period (excluding this departing IC) and Bς as the remaining busy period initiating with Lς customers during the busy period. Then, the busy period BN,D is written as(13)BN,D=ΦN,D+Bς.DenoteBi,i≥1, as i.i.d. random variables and represent the busy period initiating with a customer in the classical Geo/G/1 queue with the PGF Bz=Sp¯z+pzBz and mean EB=ES/1−ρ. Then, according to the Galton–Watson branching process approach [11] (an effective method to analyze the busy period when the service time periods of the customers are independent random variables), the remaining busy period Bς can be decomposed as Bς=B1+B2+⋯+BLς.Thus, from the conditional mean,(14)EzBN,D|ΦN,D=i,Lς=j=ziEzB1+B2+⋯+Bj=ziBzj,j≥0,i≥j.We have the busy period PGF as(15)BN,Dz=∑j=0∞∑i=j∞EzBN,D|ΦN,D=i,Lς=jPrΦN,D=i,Lς=j=∑i=0∞ziPrΦN,D=i∑j=0iBzjCijpjp¯i−j=∑i=0∞ziPrΦN,D=ip¯+pBzi=ΦN,Dp¯z+pzBz,which leads to the mean busy period(16)EBN,D=ddzBN,Dz|z=1=ρp1−ρN+∑k=NDSkD.Using (12) and (16), we get the mean busy cycle as(17)ECN,D=EIN,D+EBN,D=1p1−ρN+∑k=NDSkD.From (12), (16), and (17), the server is idle with probability 1−ρ and busy with probability ρ.


## 3.1. The Queue Size at the Start of a Busy Period

At the start of a busy period, we havekN+1≤k≤D+1 customers if and only if the D is exceeded by the kth customer and this occurs with probability Sk−1D−SkD (see the notations in Section 2). The busy period starts with N customers if and only if the sum of the service time periods of these N customers is larger than or equal to D+1. Thus, the PMF and PGF of QN,D are, respectively, given by(1)PrQN,D=k=Sk−1D−SkD,k=N+1,N+2,…,D+1,1−SND,k=N,(2)QN,Dz=∑k=ND+1PrQN,D=kzk=zN−1−z∑k=NDzkSkD,z≤1.From (2), the first and second moments of QN,D are, respectively, obtained as(3)EQN,D=dQN,Dzdz|z=1=N+∑k=NDSkD,(4)EQN,DQN,D−1=d2QN,Dzdz2|z=1=NN−1+2∑k=NDkSkD.


## 3.2. The Service Time Backlog at the Start of a Busy Period

The service time backlog isx≥D+1 at the start of a busy period if and only if the sum of the service time periods of the N customers is equal to x, or the sum of the service time periods of the first kN≤k≤D customers is n,n=k,k+1,…,D, and the D is exceeded by the next customer. Summing for all possible k and n yields the PMF of ΦN,D as(5)PrΦN,D=x=sNx+∑k=ND∑n=kDsknsx−n,x=D+1,D+2,…,which gives the PGF of ΦN,D as(6)ΦN,Dz=∑x=D+1∞zxsNx+∑k=ND∑x=D+1∞zx∑n=kDsknsx−n,where the second term of right hand side (RHS) in (6) can be expressed as(7)∑k=ND∑x=D+1∞zx∑n=kDsknsx−n=∑k=ND∑x=D+1∞zx∑n=kxsknsx−n−∑n=D+1xsknsx−n=∑k=ND∑x=D+1∞zxsk+1x−∑k=ND∑n=D+1∞zn∑x=n∞zx−nsknsx−n=∑k=ND∑x=D+1∞zxsk+1x−Sz∑k=ND∑n=D+1∞znskn.Putting (7) into (6) yields(8)ΦN,Dz=∑x=D+1∞zxsNx+∑k=N+1D+1∑x=D+1∞zxskx−Sz∑k=ND∑n=D+1∞znskn=∑x=D+1∞zxsD+1x+1−Sz∑k=ND∑n=D+1∞znskn=SzD+1+1−Sz∑k=ND∑n=D+1∞znskn.Now, using (8), we get the first and second moments of ΦN,D as(9)EΦN,D=dΦN,Dzdz|z=1=ESN+∑k=NDSkD,(10)EΦN,DΦN,D−1=d2ΦN,Dzdz2|z=1=ESS−1N+∑k=NDSkD+ESDD+1ES−2∑k=ND∑n=D+1∞nskn.


## 3.3. The Idle Period

Under the ND policy 1, ifQN,D=n,N+1≤n≤D+1, then the idle period IN,D=τ1+τ2+⋯+τn with probability Sn−1D−SnD. If QN,D=N, then the idle period IN,D=τ1+τ2+⋯+τN with probability 1−SND. Thus, we easily get the PGF and mean of the idle period as follows:(11)IN,Dz=∑n=N+1D+1τznSn−1D−SnD+τzN1−SND=QN,Dτz,(12)EIN,D=ddzIN,Dz|z=1=1pN+∑k=NDSkD,where τz=pz/1−p¯z stands for the PGF of interarrival time periods τi,i≥1.


## 3.4. The Busy Period and Busy Cycle

DefineLς as the departure point queue size of the last departing IC during the busy period (excluding this departing IC) and Bς as the remaining busy period initiating with Lς customers during the busy period. Then, the busy period BN,D is written as(13)BN,D=ΦN,D+Bς.DenoteBi,i≥1, as i.i.d. random variables and represent the busy period initiating with a customer in the classical Geo/G/1 queue with the PGF Bz=Sp¯z+pzBz and mean EB=ES/1−ρ. Then, according to the Galton–Watson branching process approach [11] (an effective method to analyze the busy period when the service time periods of the customers are independent random variables), the remaining busy period Bς can be decomposed as Bς=B1+B2+⋯+BLς.Thus, from the conditional mean,(14)EzBN,D|ΦN,D=i,Lς=j=ziEzB1+B2+⋯+Bj=ziBzj,j≥0,i≥j.We have the busy period PGF as(15)BN,Dz=∑j=0∞∑i=j∞EzBN,D|ΦN,D=i,Lς=jPrΦN,D=i,Lς=j=∑i=0∞ziPrΦN,D=i∑j=0iBzjCijpjp¯i−j=∑i=0∞ziPrΦN,D=ip¯+pBzi=ΦN,Dp¯z+pzBz,which leads to the mean busy period(16)EBN,D=ddzBN,Dz|z=1=ρp1−ρN+∑k=NDSkD.Using (12) and (16), we get the mean busy cycle as(17)ECN,D=EIN,D+EBN,D=1p1−ρN+∑k=NDSkD.From (12), (16), and (17), the server is idle with probability 1−ρ and busy with probability ρ.


## 4. The Steady-State Queue Size at an Arbitrary Timet+

In our discrete-time ND policy Geo/G/1 queue with LAS-DA, the steady-state queue size PGFL˜N,Dz at an arrival time is equal to the queue size PGF Πz at a departure time. By the BASTA (Bernoulli arrivals see time averages) property, L˜N,Dz is equal to the queue size PGF LN,Dz at an arbitrary time t+. Hence, we have(18)L˜N,Dz=Πz=LN,Dz,z≤1.LetpIC and pBC represent the probabilities that an arbitrary customer is an IC and a BC, respectively; then pIC=EQN,D/pECN,D=1−ρ and pBC=1−pIC=ρ.DenoteΠICz (ΠBCz) as the steady-state queue size PGF at the departure time of an arbitrary IC (BC); then, conditioning on the customer type, we get(19)LN,Dz=Πz=pICΠICz+pBCΠBCz=1−ρΠICz+ρΠBCz.Hence, as long as we obtain the steady-state queue size PGFsΠICz and ΠBCz at the departure time, the steady-state queue size PGF LN,Dz at an arbitrary time t+ is also derived.


### 4.1. Steady-State Queue Size at the Departure Time of an Arbitrary BC

Defineς as the departure time of the last IC during the busy period and Lς as the queue size just after ς. Then, Lς is the number of BCs arriving during ΦN,D. Therefore, the PGF and mean of Lς are, respectively, obtained as(20)Lςz=ΦN,Dp¯+pz,ELς=pEΦN,D.Since the queue size process during the busy period afterς can be considered as that during the busy period of the Geo/G/1 queue which starts with Lς BCs, from the decomposition property of the Geo/G/1 queue with generalized vacations (see Takagi [12]), we have(21)ΠBCz=ΠGeo/G/1z⋅Lς−z=ΠGeo/G/1z⋅1−Φp¯+pzpEΦN,D1−z,where ΠGeo/G/1z=1−ρ1−zSp¯+pz/Sp¯+pz−z is the queue size PGF of the classic Geo/G/1 queue and Lς−z=1−Lςz/1−zELς=1−ΦN,Dp¯+pz/pEΦN,D1−z is the PGF of the backward recurrence time of the discrete-time renewal process generated by i.i.d. Lς’s.


### 4.2. Steady-State Queue Size at the Departure Time of an Arbitrary IC

Under the steady-state condition, the queue size at the departure time of an arbitrary IC depends on whether this IC is the last customer arriving during the idle period.Case (a). If an arbitrary IC is the last customer arriving during the idle period (with probability 1/EQN,D), then at the departure time, the queue size left behind by this IC is exactly equal to the number of BCs that arrive during ΦN,D. Hence, the queue size PGF at the departure time of this IC is(22)ΦN,Dp¯+pzEQN,D.Case (b). If an arbitrary IC is not the last customer arriving during the idle period, we consider the case that this IC is the kth customer arriving during the idle period and the service time backlog including itself is x, with probability skx/EQN,D, where k=1,2,…,N−1,x=k,k+1,…,D or k=N,N+1,…,D,x=k,k+1,…,D or k=1,2,…,N−1,x=D+1,D+2,…. In this case, at the departure time, the queue size left behind by this IC is the sum of the following two quantities:(1)
The number of the BCs arriving duringx.(2)
The number of the ICs arriving during the remaining idle period after this IC’s arrival, which is exactly equal to one of the following three quantities:(i)
The number of customersQN−k,D−x at the start of a busy period under the N−kD−x policy 1 if k=1,2,…,N−1,x=k,k+1,…,D(ii)
The number of customersQ1,D−x at the start of a busy period under the D−x policy if k=N,N+1,…,D,x=k,k+1,…,D(iii)
The number of customersQN−k,N−k−1 at the start of a busy period under the N−k policy if k=1,2,…,N−1,x=D+1,D+2,…Hence, the queue size PGF at the departure time of this IC becomes(23)∑k=1N−1∑x=kDp¯+pzxQN−k,D−xzskxEQN,D+∑k=ND∑x=kDp¯+pzxQ1,D−xzskxEQN,D+∑k=1N−1∑x=D+1∞p¯+pzxQN−k,N−k−1zskxEQN,D,where QN−k,D−xz=zN−k−1−z∑n=N−kD−xznSnD−x,QN−k,N−k−1z=zN−k, and Q1,D−xz=z−1−z∑n=1D−xznSnD−x.Using (22) and (23), we get the probability-generating function (PGF) of the steady-state queue size at the departure time of an arbitrary IC as(24)ΠICz=ΦN,Dp¯+pzEQN,D+1EQN,D∑k=1N−1∑x=D+1∞skxp¯+pzxQN−k,N−k−1z+∑k=ND∑x=kDskxp¯+pzxQ1,D−xz+∑k=1N−1∑x=kDskxp¯+pzxQN−k,D−xz,where QN−k,N−k−1z, Q1,D−xz, and QN−k,D−xz are given in (23).


### 4.3. Steady-State Queue Size at an Arbitrary Timet+

After substituting (21) and (24) into (19), we get the PGF of the steady-state queue size at an arbitrary time t+ as(25)LN,Dz=ρ1−ρ1−zSp¯+pzSp¯+pz−z⋅1−ΦN,Dp¯+pzpEΦN,D1−z+1−ρEQN,DΦN,Dp¯+pz+∑k=1N−1∑x=kDskxp¯+pzxQN−k,D−xz+∑k=ND∑x=kDskxp¯+pzxQ1,D−xz+∑k=1N−1∑x=D+1∞skxp¯+pzxQN−k,N−k−1z,where QN−k,D−xz, Q1,D−xz, and QN−k,N−k−1z are given in (23).


### 4.4. Mean Queue Size

It follows from (19) that the mean steady-state queue size at an arbitrary time t+ is(26)ELN,D=1−ρELIC+ρELBC,where ELIC and ELBC are the mean steady-state queue sizes at the departure time of the IC and the BC, respectively.From (21), (9), (10), and (3), it is easy to obtain(27)ELBC=dΠBCzdz|z=1=ρ+p2ESS−121−ρ+pEΦN,DΦN,D−12EΦN,D=ρ+p2ESS−12ρ1−ρ+ρDD+12EQN,D−p∑k=ND∑n=D+1∞nsknEQN,D.Similarly, using (24) and (3) and noting that EQN−k,D−x=N−k+∑n=N−kD−xSnD−x, EQN−k,N−k−1=N−k,andEQ1,D−x=1+∑n=1D−xSnD−x, we have(28)ELIC=ρ+pEQN,D∑k=1N−1∑x=kDxskx+∑k=ND∑x=kDxskx+∑k=1N−1∑x=D+1∞xskx+1EQN,D∑k=1N−1∑x=kDskxN−k+∑n=N−kD−xSnD−x+∑k=1N−1∑x=D+1∞N−kskx+∑k=ND∑x=kDskx1+∑n=1D−xSnD−x.In (28), using ∑n=10=0 (see the notations in Section 2), we have(29)∑k=1N−1∑x=kDxskx+∑k=ND∑x=kDxskx=∑k=1D∑x=kDxskx,(30)∑k=1N−1∑x=kDskxN−k+∑k=1N−1∑x=D+1∞N−kskx+∑k=ND∑x=kDskx=∑k=1N−1N−kSkD+∑k=1N−1N−k1−SkD+∑k=NDSkD=NN−12+∑k=NDSkD,(31)∑k=1N−1∑x=kDskx∑n=N−kD−xSnD−x+∑k=ND∑x=kDskx∑n=1D−xSnD−x=∑k=1N−1∑n=N−kD−k∑x=kD−nskxSnD−x+∑k=ND∑n=1D−k∑x=kD−nskxSnD−x=∑k=1N−1∑n=N−kD−kSn+kD+∑k=ND∑n=1D−kSn+kD=∑k=1N−1SND+SN+1D+SN+2D+⋯+SDD+∑k=ND−1Sk+1D+Sk+2D+⋯+SDDhere,whenk=D,∑n=1D−k=0=N−1SND+SN+1D+SN+2D+⋯+SDD+SN+1D+2SN+2D+3SN+3D+⋯+D−NSDD=∑k=NDk−1SkD.Thus, after utilizing (29)–(31) in (28), we get(32)ELIC=ρ+pEQN,D∑k=1D∑x=kDxskx+∑k=1N−1∑x=D+1∞xskx+1EQN,DNN−12+∑k=NDkSkD.Also, it is easy to find that(33)ρ2DD+12EQN,D−ρpEQN,D∑k=ND∑n=D+1∞nskn+∑k=1D∑x=kDxskx+∑k=1N−1∑x=D+1∞xskx=ρ2DD+12EQN,D−ρpEQN,D∑k=1D∑x=k∞xskx=0.Finally, by substituting (27), (32), and (3) into (26) and using (33), we obtain the mean steady-state queue size at an arbitrary time t+ as(34)ELN,D=ρ+p2ESS−121−ρ+1−ρN+∑k=NDSkDNN−12+∑k=NDkSkD+pN+∑k=NDSkD∑k=1D∑n=kDnskn+∑k=1N−1∑n=D+1∞nskn.Remark 1.
(two special cases). In (34), we have the following cases:(1)
WhenD=N−1, noting that ∑k=ij=0,i>j (see the notation in Section 2) and(35)∑k=1D∑n=kDnskn+∑k=1N−1∑n=D+1∞nskn=ESNN−12,we get the mean queue size of the N policy Geo/G/1 queue as(36)ELN=ρ+p2ESS−121−ρ+N−12,which agrees with the result in Corollary 2 of [13].(2)
WhenN=1, noting that ∑k=ij=0,i>j (see the notation in Section 2), we get the mean queue size of the D policy Geo/G/1 queue as(37)ELD=ρ+p2ESS−121−ρ+1−ρ∑k=1DkSkD+p∑k=1D∑n=kDnskn1+∑k=1DSkD,which is identical to the result by Liu et al. [3] (setting N=D+1 in equation (34) of [3]).


## 4.1. Steady-State Queue Size at the Departure Time of an Arbitrary BC

Defineς as the departure time of the last IC during the busy period and Lς as the queue size just after ς. Then, Lς is the number of BCs arriving during ΦN,D. Therefore, the PGF and mean of Lς are, respectively, obtained as(20)Lςz=ΦN,Dp¯+pz,ELς=pEΦN,D.Since the queue size process during the busy period afterς can be considered as that during the busy period of the Geo/G/1 queue which starts with Lς BCs, from the decomposition property of the Geo/G/1 queue with generalized vacations (see Takagi [12]), we have(21)ΠBCz=ΠGeo/G/1z⋅Lς−z=ΠGeo/G/1z⋅1−Φp¯+pzpEΦN,D1−z,where ΠGeo/G/1z=1−ρ1−zSp¯+pz/Sp¯+pz−z is the queue size PGF of the classic Geo/G/1 queue and Lς−z=1−Lςz/1−zELς=1−ΦN,Dp¯+pz/pEΦN,D1−z is the PGF of the backward recurrence time of the discrete-time renewal process generated by i.i.d. Lς’s.


## 4.2. Steady-State Queue Size at the Departure Time of an Arbitrary IC

Under the steady-state condition, the queue size at the departure time of an arbitrary IC depends on whether this IC is the last customer arriving during the idle period.Case (a). If an arbitrary IC is the last customer arriving during the idle period (with probability 1/EQN,D), then at the departure time, the queue size left behind by this IC is exactly equal to the number of BCs that arrive during ΦN,D. Hence, the queue size PGF at the departure time of this IC is(22)ΦN,Dp¯+pzEQN,D.Case (b). If an arbitrary IC is not the last customer arriving during the idle period, we consider the case that this IC is the kth customer arriving during the idle period and the service time backlog including itself is x, with probability skx/EQN,D, where k=1,2,…,N−1,x=k,k+1,…,D or k=N,N+1,…,D,x=k,k+1,…,D or k=1,2,…,N−1,x=D+1,D+2,…. In this case, at the departure time, the queue size left behind by this IC is the sum of the following two quantities:(1)
The number of the BCs arriving duringx.(2)
The number of the ICs arriving during the remaining idle period after this IC’s arrival, which is exactly equal to one of the following three quantities:(i)
The number of customersQN−k,D−x at the start of a busy period under the N−kD−x policy 1 if k=1,2,…,N−1,x=k,k+1,…,D(ii)
The number of customersQ1,D−x at the start of a busy period under the D−x policy if k=N,N+1,…,D,x=k,k+1,…,D(iii)
The number of customersQN−k,N−k−1 at the start of a busy period under the N−k policy if k=1,2,…,N−1,x=D+1,D+2,…Hence, the queue size PGF at the departure time of this IC becomes(23)∑k=1N−1∑x=kDp¯+pzxQN−k,D−xzskxEQN,D+∑k=ND∑x=kDp¯+pzxQ1,D−xzskxEQN,D+∑k=1N−1∑x=D+1∞p¯+pzxQN−k,N−k−1zskxEQN,D,where QN−k,D−xz=zN−k−1−z∑n=N−kD−xznSnD−x,QN−k,N−k−1z=zN−k, and Q1,D−xz=z−1−z∑n=1D−xznSnD−x.Using (22) and (23), we get the probability-generating function (PGF) of the steady-state queue size at the departure time of an arbitrary IC as(24)ΠICz=ΦN,Dp¯+pzEQN,D+1EQN,D∑k=1N−1∑x=D+1∞skxp¯+pzxQN−k,N−k−1z+∑k=ND∑x=kDskxp¯+pzxQ1,D−xz+∑k=1N−1∑x=kDskxp¯+pzxQN−k,D−xz,where QN−k,N−k−1z, Q1,D−xz, and QN−k,D−xz are given in (23).


## 4.3. Steady-State Queue Size at an Arbitrary Timet+

After substituting (21) and (24) into (19), we get the PGF of the steady-state queue size at an arbitrary time t+ as(25)LN,Dz=ρ1−ρ1−zSp¯+pzSp¯+pz−z⋅1−ΦN,Dp¯+pzpEΦN,D1−z+1−ρEQN,DΦN,Dp¯+pz+∑k=1N−1∑x=kDskxp¯+pzxQN−k,D−xz+∑k=ND∑x=kDskxp¯+pzxQ1,D−xz+∑k=1N−1∑x=D+1∞skxp¯+pzxQN−k,N−k−1z,where QN−k,D−xz, Q1,D−xz, and QN−k,N−k−1z are given in (23).


## 4.4. Mean Queue Size

It follows from (19) that the mean steady-state queue size at an arbitrary time t+ is(26)ELN,D=1−ρELIC+ρELBC,where ELIC and ELBC are the mean steady-state queue sizes at the departure time of the IC and the BC, respectively.From (21), (9), (10), and (3), it is easy to obtain(27)ELBC=dΠBCzdz|z=1=ρ+p2ESS−121−ρ+pEΦN,DΦN,D−12EΦN,D=ρ+p2ESS−12ρ1−ρ+ρDD+12EQN,D−p∑k=ND∑n=D+1∞nsknEQN,D.Similarly, using (24) and (3) and noting that EQN−k,D−x=N−k+∑n=N−kD−xSnD−x, EQN−k,N−k−1=N−k,andEQ1,D−x=1+∑n=1D−xSnD−x, we have(28)ELIC=ρ+pEQN,D∑k=1N−1∑x=kDxskx+∑k=ND∑x=kDxskx+∑k=1N−1∑x=D+1∞xskx+1EQN,D∑k=1N−1∑x=kDskxN−k+∑n=N−kD−xSnD−x+∑k=1N−1∑x=D+1∞N−kskx+∑k=ND∑x=kDskx1+∑n=1D−xSnD−x.In (28), using ∑n=10=0 (see the notations in Section 2), we have(29)∑k=1N−1∑x=kDxskx+∑k=ND∑x=kDxskx=∑k=1D∑x=kDxskx,(30)∑k=1N−1∑x=kDskxN−k+∑k=1N−1∑x=D+1∞N−kskx+∑k=ND∑x=kDskx=∑k=1N−1N−kSkD+∑k=1N−1N−k1−SkD+∑k=NDSkD=NN−12+∑k=NDSkD,(31)∑k=1N−1∑x=kDskx∑n=N−kD−xSnD−x+∑k=ND∑x=kDskx∑n=1D−xSnD−x=∑k=1N−1∑n=N−kD−k∑x=kD−nskxSnD−x+∑k=ND∑n=1D−k∑x=kD−nskxSnD−x=∑k=1N−1∑n=N−kD−kSn+kD+∑k=ND∑n=1D−kSn+kD=∑k=1N−1SND+SN+1D+SN+2D+⋯+SDD+∑k=ND−1Sk+1D+Sk+2D+⋯+SDDhere,whenk=D,∑n=1D−k=0=N−1SND+SN+1D+SN+2D+⋯+SDD+SN+1D+2SN+2D+3SN+3D+⋯+D−NSDD=∑k=NDk−1SkD.Thus, after utilizing (29)–(31) in (28), we get(32)ELIC=ρ+pEQN,D∑k=1D∑x=kDxskx+∑k=1N−1∑x=D+1∞xskx+1EQN,DNN−12+∑k=NDkSkD.Also, it is easy to find that(33)ρ2DD+12EQN,D−ρpEQN,D∑k=ND∑n=D+1∞nskn+∑k=1D∑x=kDxskx+∑k=1N−1∑x=D+1∞xskx=ρ2DD+12EQN,D−ρpEQN,D∑k=1D∑x=k∞xskx=0.Finally, by substituting (27), (32), and (3) into (26) and using (33), we obtain the mean steady-state queue size at an arbitrary time t+ as(34)ELN,D=ρ+p2ESS−121−ρ+1−ρN+∑k=NDSkDNN−12+∑k=NDkSkD+pN+∑k=NDSkD∑k=1D∑n=kDnskn+∑k=1N−1∑n=D+1∞nskn.Remark 1.
(two special cases). In (34), we have the following cases:(1)
WhenD=N−1, noting that ∑k=ij=0,i>j (see the notation in Section 2) and(35)∑k=1D∑n=kDnskn+∑k=1N−1∑n=D+1∞nskn=ESNN−12,we get the mean queue size of the N policy Geo/G/1 queue as(36)ELN=ρ+p2ESS−121−ρ+N−12,which agrees with the result in Corollary 2 of [13].(2)
WhenN=1, noting that ∑k=ij=0,i>j (see the notation in Section 2), we get the mean queue size of the D policy Geo/G/1 queue as(37)ELD=ρ+p2ESS−121−ρ+1−ρ∑k=1DkSkD+p∑k=1D∑n=kDnskn1+∑k=1DSkD,which is identical to the result by Liu et al. [3] (setting N=D+1 in equation (34) of [3]).


## 5. Computation Designs in the Optimal Power Control of a WSN

Consider a wireless sensor network (WSN) [14] used in the battlefield conditions for a military purpose, which is responsible for the intelligence on enemy troop movements, damage, casualties, and so on. This WSN is comprised of a sink node and a number of sensor nodes, in which the sensor nodes behave as both data packets originator and packets router and finally send packets to a sink node for further handling. The sensor nodes are installed with some energy-limited batteries, a radio server, and a sensing unit. Because these sensor nodes are employed in the secret or hostile places, it is usually impossible to recharge or replace their batteries. Therefore, it is very important for the long lifetime of a WSN to achieve a good power-saving scheme.This kind of WSN can be modelled as the discrete-time threshold policy queues because its protocols are operated according to a unit of slot, the transmission time of each packet is a random variable, and the power consumption can be rationally controlled by the threshold policy queues [3, 14, 15]. Here, our aim is to numerically compare the optimal power-saving policy that minimizes the power consumption under the N, D, and two ND policies.For this purpose, we denote the following:EBN,D≡ the mean time length that the radio server is busy handling data packetsEIN,D≡ the mean time length that the radio server is idleECN,D≡ the mean time length that the radio server is during a busy cycle, which is the sum of EIN,D and EBN,DELN,D≡ the mean number of data packets in the steady stateIn addition, we consider the following power consumption elements and average power consumption functions, whose definitions are identical to those by Jiang et al. [15]:es≡ setup power consumption per busy cycleel≡ holding power consumption per unit time for each data packeteb≡ power consumption of the busy radio server per unit timeei≡ power consumption of the idle radio server per unit timeUnder the ND policy 1, the average power consumption per unit time is(38)A1N,D=ebEBN,DECN,D+eiEIN,DECN,D+esECN,D+ehELN,D=ebρ+ei1−ρ+esp1−ρN+∑k=NDSkD+ehρ+p2ESS−121−ρ+pN+∑k=NDSkD∑k=1D∑n=kDnskn+∑k=1N−1∑n=D+1∞nskn+1−ρN+∑k=NDSkDNN−12+∑k=NDkSkD,1≤N≤D+1.Remark 2.
In (38), EIN,D, EBN,D, and ECN,D are given by (12), (16), and (17), respectively, and ELN,D is presented by (34). Also, in Section 5, skn denotes the probability that the sum of the transmission time periods of k data packets is equal to n and SkD is the probability that the sum of the transmission time periods of k data packets does not exceed D.
Under the ND policy 2, the average power consumption per unit time (see equation (66) in [3]) is(39)A2N,D=ebρ+ei1−ρ+esp1−ρ1+∑k=1N−1SkD+ehρ+p2ESS−121−ρ+p∑k=1N−1∑n=kDnskn1+∑k=1N−1SkD+1−ρ∑k=1N−1kSkD1+∑k=1N−1SkD,1≤N≤D+1.
Under the pure N and D policies, the average power consumptions per unit time, denoted byANN and ADD, respectively, can be expressed as ANN=A1N,N−1=A2N,∞ and ADD=A11,D=A2D+1,D.


### 5.1. Rewriting for the Mean Queue Size

In order to accelerate numerical operation speed and avoid numerical errors, we rewrite the mean queue size in (34) as the expression that does not involve the series.In (34), noting that 1≤N≤D+1 and ∑k=ij=0 if i>j (see the notations in Section 2), we get(40)∑k=1D∑n=kDnskn−∑k=1N−1∑n=kDnskn=∑k=ND∑n=kDnskn,∑k=1D∑n=kDnskn+∑k=1N−1∑n=D+1∞nskn=∑k=1D∑n=kDnskn+∑k=1N−1∑n=k∞nskn−∑n=kDnskn=ESNN−12+∑k=ND∑n=kDnskn.Then, the mean queue size in (34) is rewritten as follows:(41)ELN,D=ρ+p2ESS−121−ρ+1N+∑k=NDSkD×NN−12+p∑k=ND∑n=kDnskn+1−ρ∑k=NDkSkD.Correspondingly, the average power consumption functionA1N,D in (38) becomes(42)A1N,D=ebρ+ei1−ρ+esp1−ρN+∑k=NDSkD+ehρ+p2ESS−121−ρ+1N+∑k=NDSkDNN−12+p∑k=1D∑n=kDnskn+1−ρ∑k=NDkSkD,1≤N≤D+1.Remark 3.
Relative to (38), equation (42) is an expression that does not involve the series. It can avoid numerical errors and greatly accelerate the computation speed. Therefore, for all numerical computations in Section 5, equation (38) is replaced by equation (42).


### 5.2. Expressions onSkD1≤k≤D and skn1≤k≤n for an Arbitrarily Distributed Transmission Time

Since all numerical experiments in [3] were conducted only for the geometrically distributed transmission time, the conclusion obtained is very inadequate. It is important for the network designers and practitioners to carry out numerical illustrations and comparisons in the case of an arbitrarily distributed transmission time. For this purpose, we have to find the expressions of SkD1≤k≤D and skn1≤k≤n in (39) and (42) for an arbitrarily distributed transmission time.From the notations in Section2, we know that(43)SkD=Pr∑j=1kSj≤D,k=1,2,…,D,SkD=0,k≥D+1,S0D=1,skn=Pr∑j=1kSj=n,k=1,2,…,n,skn=0,k≥n+1.Hence, it is difficult for an arbitrarily distributed transmission time to compute the values ofSkD1≤k≤D and skn1≤k≤n. This is due to the computational difficulties in the convolution summation of the discrete-time distribution.If the transmission/service time periods follow a common geometrical distribution,si=qq¯i−1,where0<q<1andi=1,2,3,…, then it is easy to find that SkD=∑i=kDCi−1k−1qkq¯i−k,k=1,2,…,D, and skn=Cn−1k−1qkq¯n−k,1≤k≤n.For an arbitrary discrete distribution of i.i.d. transmission time periodsSn,n≥1, it seems difficult to compute SkD1≤k≤D and skn1≤k≤n. However, from the results by Alfa [16] and Latouche and Ramaswami [17], we can also find an effective method to compute the values of SkD1≤k≤D and skn1≤k≤n. As three lemmas, we give the following results.Lemma 1 (see Theorem 2.1 in Alfa [16]).
If the probability distribution of the discrete random variableX is PrX=i=ai,i=1,2,…,n, then X follows a discrete n-dimensional phase-type distribution PHdα,T with parameters(44)α=a1,a2,…,an,T=01×n−10In−10n−1×1,where In−1 denotes an identity matrix of dimension n−1 and 01×n−1 and 0n−1×1 are row and column vectors of ones of dimensions n−1, respectively.Lemma 2 (see Alfa [16]).
Suppose that random variablesX and Y are independent, X obeys a discrete n-dimensional phase-type distribution PHdα,T, and Y follows a discrete m-dimensional phase-type distribution PHdβ,S; then, X+Y obeys a discrete n+m-dimensional phase-type distribution PHdγ,C with parameters(45)γ=α,α0β,C=TT0β0m×nS,T0=1n−T1n,where α0 denotes the probability that X locates the absorbing state at the initial time and 1n is a column vector of ones of dimension n.Remark 4.
Our aim is to find the phase-type distribution of the sum of i.i.d. transmission time periodsS1,S2,…,Sn with an arbitrary discrete distribution. Since it is impossible that the transmission time locates the absorbing state at the initial time, the initial probability of transmission time α0 is taken as zero in the following numerical experiments.Lemma 3 (see Theorem 2.5.3 by Latouche and Ramaswami [17]).
Suppose that the random variableZ obeys a discrete phase-type distribution PHdα,T; then, the probability distribution of Z is(46)PrZ=0=α0,PrZ=k=αTk−1T0,k=1,2,…,PrZ≤k=1−αTk1,where 1 is a column vector of ones.In what follows, we use the three lemmas mentioned above to derive two computation expressions onSkD1≤k≤D and skn1≤k≤n. To make our method easy to understand, we assume that the i.i.d. transmission time periods Si,i≥1, have an arbitrary discrete distribution as s2=0.3,s3=0.55,ands5=0.15. Then, three steps for computing SkD1≤k≤D and skn1≤k≤n are presented as follows:Step I. According to Lemma 1, the transmission time S1 follows a discrete phase-type distribution PHdα1,T1 with parameters(47)α1=0,0.3,0.55,0,0.15,T1=01×40I404×1,T10=10000.Step II. According to Lemma 2, S1+S2 follows a discrete phase-type distribution PHdα2,T2 with parameters(48)α2=0,0.3,0.55,0,0.15,01×5,T2=T1T10α105×5T1,T20=05×1T10.Similarly, from Lemma2, T10α1=00.30.5500.1500000000000000000000, and T20α1=05×5T10α1, we know that S1+S2+S3 also obeys a discrete phase-type distribution PHdα3,T3 with parameters(49)α3=0,0.3,0.55,0,0.15,01×5,01×5=0,0.3,0.55,0,0.15,01×10,T3=T2T20α105×10T1=T1T10α1T1T10α1T1,T30=05×105×1T10,⋮.By induction,S1+S2+⋯+Skk≥2 follows a discrete phase-type distribution PHdαk,Tk with parameters αk=0,0.3,0.55,0,0.15,01×5k−1,(50)Tk=12⋮k−1kT1T10α1T1T10α1⋱⋱T1T10α1T1,Tk0=12⋮k−1k05×105×1⋮05×1T10.Step III. By Lemma 3, SkD1≤k≤D and skn1≤k≤n are given as follows:(51)SkD=PrS1+S2+⋯+Sk≤D=1−αkTkD15k,skn=PrS1+S2+⋯+Sk=n=αkTkn−1Tk0.Similarly, for other i.i.d. transmission time periodsSi,i≥1, with an arbitrary discrete distribution, the corresponding expressions of SkD1≤k≤D and skn1≤k≤n can also be derived by the three lemmas mentioned above.In finding the optimal policy thresholdN∗,D∗ of AiN,D,i=1,2, it is not easy to analytically prove that the functions A1N,D and A2N,D are convex or unimodal because they are not linear and very complicated. Therefore, we will numerically determine the optimal threshold N∗,D∗ of AiN,D,i=1,2. According to the optimization theory of the dynamic programme (for details, see [18]), we can develop an effective procedure to numerically get the optimal threshold N∗,D∗ of AiN,D,i=1,2. In fact, for a given positive integer N, the optimal value D∗N of the threshold D, so as to minimize AiN,D, is given by(52)D∗N=minD≥N−1|AiN,D+1−AiN,D>0.That is,D∗N is the first nonnegative integer D that makes the inequality AiN,D+1−AiN,D>0 hold. Thus, a numerical procedure to find the optimal threshold N∗,D∗ of N,D, so as to minimize AiN,D,i=1,2, can be presented as follows:Step 1. For a given distribution of the i.i.d. transmission time periods Si,i≥1, derive the expressions of SkD1≤k≤D and skn1≤k≤n by Lemmas 1–3 and Steps I, II, and III.Step 2. Set N=1. Compute D∗N and AiN,D∗N by using (39), (42), and (52), respectively.Step 3. Set N=N+1. Compute D∗N and AiN,D∗N by using (39), (42), and (52), respectively.Step 4. When AiN+1,D∗N+1>AiN,D∗N, stop. The optimal threshold N∗,D∗ of N,D, so as to minimize AiN,D,i=1,2, is N,D∗N. Or else, go to Step 2.Remark 5.
LetNN∗ and DD∗ denote the optimal policy thresholds of the power consumption functions ANN and ADD,i=1,2; then, NN∗ and DD∗ are, respectively, determined by(53)NN∗=minN≥1|A1N+1,N−A1N,N−1>0,DD∗=minD≥0|A11,D+1−A11,D>0.


### 5.3. A Numerical Example

A numerical example is presented to illustrate how the designer or practitioner of a wireless sensor network can use the above results to make decisions regarding the optimal policyN∗,D∗ that minimizes the average power consumption. We assume the following:(i)
The data packets arrive according to a Bernoulli process at a ratep=0.2(ii)
The transmission time obeys an arbitrary discrete-time distribution:s2=0.3,s3=0.55,ands5=0.15(iii)
es=300, eh=3, eb=500, and ei=100Through a MATLAB code based on the results and procedure in Section5.2, the average power consumption A1N,D is shown in Figure 2 for the Geo/G/1 queue with the ND policy 1 and varying values of N and D. Under the ND policy 1, a minimum power consumption per unit time of 353.3288 is achieved at N∗=4 and D∗=9. The average power consumption A2N,D is shown in Figure 3 for the Geo/G/1 queue with the ND policy 2 and varying values of N and D. Under the ND policy 2, a minimum power consumption per unit time of 353.3232 is achieved at N∗=4 and D∗=11.Figure 2
Power consumptionA1N,D for varying values of N and D under the ND policy 1.Figure 3
Power consumptionA2N,D for varying values of N and D under the ND policy 2.


### 5.4. Numerical Comparison of the Optimal Power-Saving Policies

To illustrate the power-saving effectiveness and superiority of the N, D, and two ND policies, a comparison on the minimum power consumptions is numerically conducted in the following two cases:Case 1: we select the power consumption elements ases=300, eh=3, eb=500, and ei=100, fix ρ=0.1,0.3,0.5,0.7,0.9, and vary the thresholds N and D.Case 2: we selectρ=0.5, eb=500, and ei=100, fix es,eh=200,5, 300,5, 400,5, 400,3, and 400,1, and vary the thresholds N and D.Also, the arrival of data packets is generated according to a Bernoulli process. Three transmission time distributions with the same meanES=3 are used. They are one geometric distribution and two arbitrary distributions:(i)
Geometric:si=1/32/3i−1,i≥1(ii)
Arbitrary:s2=0.3,s3=0.55,ands5=0.15(iii)
Arbitrary:s1=0.25,s3=0.5,ands5=0.25In the above two cases, the optimal policies and their minimum power consumptions forANN, ADD, A1N,D, and A2N,D are reported in Tables 1 and 2.Table 1
Optimal power-saving policies and the minimum power consumptions forANN,ADD, A1N,D, and A2N,D (es=300, eh=3, eb=500, and ei=100).
Transmission time distributionOptimal power-saving policy minimum power consumptionρ=0.1ρ=0.3ρ=0.5ρ=0.7ρ=0.9Geometric:si=1/32/3i−1,i≥1NN∗24442ANNN∗146.3222230.9071313.2500395.1167484.9000DD∗48985ADDD∗146.6365231.1753313.2500394.8030484.2750N∗,D∗(2, 2)(4, 4)(3, 9)(2, 8)(1, 5)A1N∗,D∗146.3012230.9067313.1790394.7942484.2750N∗,D∗(3, 10)(4, 13)(5, 11)(5, 9)(4, 5)A2N∗,D∗146.3072230.8580313.1228394.7665484.2726Arbitrary:s2=0.3s3=0.55s5=0.15NN∗24442ANNN∗146.3128230.7979312.8250393.7283478.0150DD∗591095ADDD∗146.2917230.8546312.8542393.6823477.8253N∗,D∗(1, 5)(4, 3)(4, 9)(3, 9)(1, 5)A1N∗,D∗146.2917230.7979312.8199393.6768477.8253N∗,D∗(6, 5)(4, 11)(4, 12)(4, 10)(6, 5)A2N∗,D∗146.2917230.7919312.8216393.6748477.8253Arbitrary:s1=0.25s3=0.5s5=0.25NN∗24442ANNN∗146.3148230.8214312.9167394.0278479.5000DD∗591095ADDD∗146.4114230.9451312.9561393.9156479.1813N∗,D∗(2, 2)(4, 4)(4, 8)(3, 9)(1, 5)A1N∗,D∗146.3027230.8213312.8833393.9020479.1813N∗,D∗(3, 5)(4, 11)(5, 11)(5, 9)(5, 5)A2N∗,D∗146.2824230.8064312.8848393.9012479.1812Table 2
Optimal power-saving policies and the minimum power consumptions forANN,ADD, A1N,D, and A2N,D (ρ=0.5, eb=500, and ei=100).
Transmission time distributionOptimal power-saving policy minimum power consumptiones=200eh=5es=300eh=5es=400eh=5es=400eh=3es=400eh=1Geometric:si=1/32/3i−1, i≥1NN∗33458ANNN∗314.7222317.5000320.0000315.1667308.5000DD∗5681121ADDD∗314.5833317.5000319.9242315.1429308.5000N∗,D∗(2, 4)(3, 5)(3, 7)(4, 10)(7, 20)A1N∗,D∗314.4756317.3674319.7798315.0426308.4595N∗,D∗(3, 7)(4, 8)(4, 10)(5, 14)(9, 25)A2N∗,D∗314.3883317.2955319.7063315.0084308.4471Arbitrary:s2=0.3s3=0.55s5=0.15NN∗33458ANNN∗314.0139316.7917319.2917314.7417308.3583DD∗6891222ADDD∗313.9345316.8591319.2668314.7444308.3618N∗,D∗(1, 6)(3, 6)(3, 9)(4, 12)(8, 21)A1N∗,D∗313.9345316.7842319.2518314.7308308.3526N∗,D∗(3, 6)(3∞)(4, 10)(5, 13)(9, 23)A2N∗,D∗313.9144316.7917319.2249314.7097308.3561Arbitrary:s1=0.25s3=0.5s5=0.25NN∗33458ANNN∗314.1667316.9444319.4444314.8333308.3889DD∗6891222ADDD∗314.0968317.0280319.4317314.8401308.3925N∗,D∗(2, 4)(3, 5)(3, 7)(4, 10)(8, 20)A1N∗,D∗314.0634316.8786319.3726314.8006308.3744N∗,D∗(3, 6)(4, 8)(4, 10)(5, 13)(9, 23)A2N∗,D∗313.9987316.8810319.3091314.7697308.3731From Tables1 and 2, we see the following: (1) Under a same value of ρ (or es,eh) and an identical policy, four transmission time distributions with the same mean of 3 but different coefficient of variations have minor differences in the minimum power consumption. (2) Under the same value of ρ (or es,eh) and an identical transmission time distribution, two ND policies have less or equal power consumption by comparison with the N and D policies. Thus, two ND policies are superior to the N and D policies in decreasing the power consumption of a wireless sensor node. That is to say, two ND policies are more effective than the N and D policies in the power-saving problem of a WSN. (3) Under the same value of ρ(or es,eh) and an identical transmission time distribution, the power consumed by the ND policy 1 is larger, less than, or equal to that consumed by the ND policy 2 and vice versa (see Tables 1 and 2). This means that the superiority of two ND policies is uncertain and dependent on the traffic intensity, the power consumption elements es and eh, and the transmission time distribution. Therefore, in the power-saving design of a wireless sensor network, two ND policies should be adopted to control the sleep/wake-up mode of the radio server according to the concrete network parameter setting, such as the traffic intensity, the transmission time distribution, and the power consumption elements es and eh.It is expected that the data results in Tables1 and 2 are useful and helpful for the network designers and practitioners in the military and other related fields.


## 5.1. Rewriting for the Mean Queue Size

In order to accelerate numerical operation speed and avoid numerical errors, we rewrite the mean queue size in (34) as the expression that does not involve the series.In (34), noting that 1≤N≤D+1 and ∑k=ij=0 if i>j (see the notations in Section 2), we get(40)∑k=1D∑n=kDnskn−∑k=1N−1∑n=kDnskn=∑k=ND∑n=kDnskn,∑k=1D∑n=kDnskn+∑k=1N−1∑n=D+1∞nskn=∑k=1D∑n=kDnskn+∑k=1N−1∑n=k∞nskn−∑n=kDnskn=ESNN−12+∑k=ND∑n=kDnskn.Then, the mean queue size in (34) is rewritten as follows:(41)ELN,D=ρ+p2ESS−121−ρ+1N+∑k=NDSkD×NN−12+p∑k=ND∑n=kDnskn+1−ρ∑k=NDkSkD.Correspondingly, the average power consumption functionA1N,D in (38) becomes(42)A1N,D=ebρ+ei1−ρ+esp1−ρN+∑k=NDSkD+ehρ+p2ESS−121−ρ+1N+∑k=NDSkDNN−12+p∑k=1D∑n=kDnskn+1−ρ∑k=NDkSkD,1≤N≤D+1.Remark 3.
Relative to (38), equation (42) is an expression that does not involve the series. It can avoid numerical errors and greatly accelerate the computation speed. Therefore, for all numerical computations in Section 5, equation (38) is replaced by equation (42).


## 5.2. Expressions onSkD1≤k≤D and skn1≤k≤n for an Arbitrarily Distributed Transmission Time

Since all numerical experiments in [3] were conducted only for the geometrically distributed transmission time, the conclusion obtained is very inadequate. It is important for the network designers and practitioners to carry out numerical illustrations and comparisons in the case of an arbitrarily distributed transmission time. For this purpose, we have to find the expressions of SkD1≤k≤D and skn1≤k≤n in (39) and (42) for an arbitrarily distributed transmission time.From the notations in Section2, we know that(43)SkD=Pr∑j=1kSj≤D,k=1,2,…,D,SkD=0,k≥D+1,S0D=1,skn=Pr∑j=1kSj=n,k=1,2,…,n,skn=0,k≥n+1.Hence, it is difficult for an arbitrarily distributed transmission time to compute the values ofSkD1≤k≤D and skn1≤k≤n. This is due to the computational difficulties in the convolution summation of the discrete-time distribution.If the transmission/service time periods follow a common geometrical distribution,si=qq¯i−1,where0<q<1andi=1,2,3,…, then it is easy to find that SkD=∑i=kDCi−1k−1qkq¯i−k,k=1,2,…,D, and skn=Cn−1k−1qkq¯n−k,1≤k≤n.For an arbitrary discrete distribution of i.i.d. transmission time periodsSn,n≥1, it seems difficult to compute SkD1≤k≤D and skn1≤k≤n. However, from the results by Alfa [16] and Latouche and Ramaswami [17], we can also find an effective method to compute the values of SkD1≤k≤D and skn1≤k≤n. As three lemmas, we give the following results.Lemma 1 (see Theorem 2.1 in Alfa [16]).
If the probability distribution of the discrete random variableX is PrX=i=ai,i=1,2,…,n, then X follows a discrete n-dimensional phase-type distribution PHdα,T with parameters(44)α=a1,a2,…,an,T=01×n−10In−10n−1×1,where In−1 denotes an identity matrix of dimension n−1 and 01×n−1 and 0n−1×1 are row and column vectors of ones of dimensions n−1, respectively.Lemma 2 (see Alfa [16]).
Suppose that random variablesX and Y are independent, X obeys a discrete n-dimensional phase-type distribution PHdα,T, and Y follows a discrete m-dimensional phase-type distribution PHdβ,S; then, X+Y obeys a discrete n+m-dimensional phase-type distribution PHdγ,C with parameters(45)γ=α,α0β,C=TT0β0m×nS,T0=1n−T1n,where α0 denotes the probability that X locates the absorbing state at the initial time and 1n is a column vector of ones of dimension n.Remark 4.
Our aim is to find the phase-type distribution of the sum of i.i.d. transmission time periodsS1,S2,…,Sn with an arbitrary discrete distribution. Since it is impossible that the transmission time locates the absorbing state at the initial time, the initial probability of transmission time α0 is taken as zero in the following numerical experiments.Lemma 3 (see Theorem 2.5.3 by Latouche and Ramaswami [17]).
Suppose that the random variableZ obeys a discrete phase-type distribution PHdα,T; then, the probability distribution of Z is(46)PrZ=0=α0,PrZ=k=αTk−1T0,k=1,2,…,PrZ≤k=1−αTk1,where 1 is a column vector of ones.In what follows, we use the three lemmas mentioned above to derive two computation expressions onSkD1≤k≤D and skn1≤k≤n. To make our method easy to understand, we assume that the i.i.d. transmission time periods Si,i≥1, have an arbitrary discrete distribution as s2=0.3,s3=0.55,ands5=0.15. Then, three steps for computing SkD1≤k≤D and skn1≤k≤n are presented as follows:Step I. According to Lemma 1, the transmission time S1 follows a discrete phase-type distribution PHdα1,T1 with parameters(47)α1=0,0.3,0.55,0,0.15,T1=01×40I404×1,T10=10000.Step II. According to Lemma 2, S1+S2 follows a discrete phase-type distribution PHdα2,T2 with parameters(48)α2=0,0.3,0.55,0,0.15,01×5,T2=T1T10α105×5T1,T20=05×1T10.Similarly, from Lemma2, T10α1=00.30.5500.1500000000000000000000, and T20α1=05×5T10α1, we know that S1+S2+S3 also obeys a discrete phase-type distribution PHdα3,T3 with parameters(49)α3=0,0.3,0.55,0,0.15,01×5,01×5=0,0.3,0.55,0,0.15,01×10,T3=T2T20α105×10T1=T1T10α1T1T10α1T1,T30=05×105×1T10,⋮.By induction,S1+S2+⋯+Skk≥2 follows a discrete phase-type distribution PHdαk,Tk with parameters αk=0,0.3,0.55,0,0.15,01×5k−1,(50)Tk=12⋮k−1kT1T10α1T1T10α1⋱⋱T1T10α1T1,Tk0=12⋮k−1k05×105×1⋮05×1T10.Step III. By Lemma 3, SkD1≤k≤D and skn1≤k≤n are given as follows:(51)SkD=PrS1+S2+⋯+Sk≤D=1−αkTkD15k,skn=PrS1+S2+⋯+Sk=n=αkTkn−1Tk0.Similarly, for other i.i.d. transmission time periodsSi,i≥1, with an arbitrary discrete distribution, the corresponding expressions of SkD1≤k≤D and skn1≤k≤n can also be derived by the three lemmas mentioned above.In finding the optimal policy thresholdN∗,D∗ of AiN,D,i=1,2, it is not easy to analytically prove that the functions A1N,D and A2N,D are convex or unimodal because they are not linear and very complicated. Therefore, we will numerically determine the optimal threshold N∗,D∗ of AiN,D,i=1,2. According to the optimization theory of the dynamic programme (for details, see [18]), we can develop an effective procedure to numerically get the optimal threshold N∗,D∗ of AiN,D,i=1,2. In fact, for a given positive integer N, the optimal value D∗N of the threshold D, so as to minimize AiN,D, is given by(52)D∗N=minD≥N−1|AiN,D+1−AiN,D>0.That is,D∗N is the first nonnegative integer D that makes the inequality AiN,D+1−AiN,D>0 hold. Thus, a numerical procedure to find the optimal threshold N∗,D∗ of N,D, so as to minimize AiN,D,i=1,2, can be presented as follows:Step 1. For a given distribution of the i.i.d. transmission time periods Si,i≥1, derive the expressions of SkD1≤k≤D and skn1≤k≤n by Lemmas 1–3 and Steps I, II, and III.Step 2. Set N=1. Compute D∗N and AiN,D∗N by using (39), (42), and (52), respectively.Step 3. Set N=N+1. Compute D∗N and AiN,D∗N by using (39), (42), and (52), respectively.Step 4. When AiN+1,D∗N+1>AiN,D∗N, stop. The optimal threshold N∗,D∗ of N,D, so as to minimize AiN,D,i=1,2, is N,D∗N. Or else, go to Step 2.Remark 5.
LetNN∗ and DD∗ denote the optimal policy thresholds of the power consumption functions ANN and ADD,i=1,2; then, NN∗ and DD∗ are, respectively, determined by(53)NN∗=minN≥1|A1N+1,N−A1N,N−1>0,DD∗=minD≥0|A11,D+1−A11,D>0.


## 5.3. A Numerical Example

A numerical example is presented to illustrate how the designer or practitioner of a wireless sensor network can use the above results to make decisions regarding the optimal policyN∗,D∗ that minimizes the average power consumption. We assume the following:(i)
The data packets arrive according to a Bernoulli process at a ratep=0.2(ii)
The transmission time obeys an arbitrary discrete-time distribution:s2=0.3,s3=0.55,ands5=0.15(iii)
es=300, eh=3, eb=500, and ei=100Through a MATLAB code based on the results and procedure in Section5.2, the average power consumption A1N,D is shown in Figure 2 for the Geo/G/1 queue with the ND policy 1 and varying values of N and D. Under the ND policy 1, a minimum power consumption per unit time of 353.3288 is achieved at N∗=4 and D∗=9. The average power consumption A2N,D is shown in Figure 3 for the Geo/G/1 queue with the ND policy 2 and varying values of N and D. Under the ND policy 2, a minimum power consumption per unit time of 353.3232 is achieved at N∗=4 and D∗=11.Figure 2
Power consumptionA1N,D for varying values of N and D under the ND policy 1.Figure 3
Power consumptionA2N,D for varying values of N and D under the ND policy 2.


## 5.4. Numerical Comparison of the Optimal Power-Saving Policies

To illustrate the power-saving effectiveness and superiority of the N, D, and two ND policies, a comparison on the minimum power consumptions is numerically conducted in the following two cases:Case 1: we select the power consumption elements ases=300, eh=3, eb=500, and ei=100, fix ρ=0.1,0.3,0.5,0.7,0.9, and vary the thresholds N and D.Case 2: we selectρ=0.5, eb=500, and ei=100, fix es,eh=200,5, 300,5, 400,5, 400,3, and 400,1, and vary the thresholds N and D.Also, the arrival of data packets is generated according to a Bernoulli process. Three transmission time distributions with the same meanES=3 are used. They are one geometric distribution and two arbitrary distributions:(i)
Geometric:si=1/32/3i−1,i≥1(ii)
Arbitrary:s2=0.3,s3=0.55,ands5=0.15(iii)
Arbitrary:s1=0.25,s3=0.5,ands5=0.25In the above two cases, the optimal policies and their minimum power consumptions forANN, ADD, A1N,D, and A2N,D are reported in Tables 1 and 2.Table 1
Optimal power-saving policies and the minimum power consumptions forANN,ADD, A1N,D, and A2N,D (es=300, eh=3, eb=500, and ei=100).
Transmission time distributionOptimal power-saving policy minimum power consumptionρ=0.1ρ=0.3ρ=0.5ρ=0.7ρ=0.9Geometric:si=1/32/3i−1,i≥1NN∗24442ANNN∗146.3222230.9071313.2500395.1167484.9000DD∗48985ADDD∗146.6365231.1753313.2500394.8030484.2750N∗,D∗(2, 2)(4, 4)(3, 9)(2, 8)(1, 5)A1N∗,D∗146.3012230.9067313.1790394.7942484.2750N∗,D∗(3, 10)(4, 13)(5, 11)(5, 9)(4, 5)A2N∗,D∗146.3072230.8580313.1228394.7665484.2726Arbitrary:s2=0.3s3=0.55s5=0.15NN∗24442ANNN∗146.3128230.7979312.8250393.7283478.0150DD∗591095ADDD∗146.2917230.8546312.8542393.6823477.8253N∗,D∗(1, 5)(4, 3)(4, 9)(3, 9)(1, 5)A1N∗,D∗146.2917230.7979312.8199393.6768477.8253N∗,D∗(6, 5)(4, 11)(4, 12)(4, 10)(6, 5)A2N∗,D∗146.2917230.7919312.8216393.6748477.8253Arbitrary:s1=0.25s3=0.5s5=0.25NN∗24442ANNN∗146.3148230.8214312.9167394.0278479.5000DD∗591095ADDD∗146.4114230.9451312.9561393.9156479.1813N∗,D∗(2, 2)(4, 4)(4, 8)(3, 9)(1, 5)A1N∗,D∗146.3027230.8213312.8833393.9020479.1813N∗,D∗(3, 5)(4, 11)(5, 11)(5, 9)(5, 5)A2N∗,D∗146.2824230.8064312.8848393.9012479.1812Table 2
Optimal power-saving policies and the minimum power consumptions forANN,ADD, A1N,D, and A2N,D (ρ=0.5, eb=500, and ei=100).
Transmission time distributionOptimal power-saving policy minimum power consumptiones=200eh=5es=300eh=5es=400eh=5es=400eh=3es=400eh=1Geometric:si=1/32/3i−1, i≥1NN∗33458ANNN∗314.7222317.5000320.0000315.1667308.5000DD∗5681121ADDD∗314.5833317.5000319.9242315.1429308.5000N∗,D∗(2, 4)(3, 5)(3, 7)(4, 10)(7, 20)A1N∗,D∗314.4756317.3674319.7798315.0426308.4595N∗,D∗(3, 7)(4, 8)(4, 10)(5, 14)(9, 25)A2N∗,D∗314.3883317.2955319.7063315.0084308.4471Arbitrary:s2=0.3s3=0.55s5=0.15NN∗33458ANNN∗314.0139316.7917319.2917314.7417308.3583DD∗6891222ADDD∗313.9345316.8591319.2668314.7444308.3618N∗,D∗(1, 6)(3, 6)(3, 9)(4, 12)(8, 21)A1N∗,D∗313.9345316.7842319.2518314.7308308.3526N∗,D∗(3, 6)(3∞)(4, 10)(5, 13)(9, 23)A2N∗,D∗313.9144316.7917319.2249314.7097308.3561Arbitrary:s1=0.25s3=0.5s5=0.25NN∗33458ANNN∗314.1667316.9444319.4444314.8333308.3889DD∗6891222ADDD∗314.0968317.0280319.4317314.8401308.3925N∗,D∗(2, 4)(3, 5)(3, 7)(4, 10)(8, 20)A1N∗,D∗314.0634316.8786319.3726314.8006308.3744N∗,D∗(3, 6)(4, 8)(4, 10)(5, 13)(9, 23)A2N∗,D∗313.9987316.8810319.3091314.7697308.3731From Tables1 and 2, we see the following: (1) Under a same value of ρ (or es,eh) and an identical policy, four transmission time distributions with the same mean of 3 but different coefficient of variations have minor differences in the minimum power consumption. (2) Under the same value of ρ (or es,eh) and an identical transmission time distribution, two ND policies have less or equal power consumption by comparison with the N and D policies. Thus, two ND policies are superior to the N and D policies in decreasing the power consumption of a wireless sensor node. That is to say, two ND policies are more effective than the N and D policies in the power-saving problem of a WSN. (3) Under the same value of ρ(or es,eh) and an identical transmission time distribution, the power consumed by the ND policy 1 is larger, less than, or equal to that consumed by the ND policy 2 and vice versa (see Tables 1 and 2). This means that the superiority of two ND policies is uncertain and dependent on the traffic intensity, the power consumption elements es and eh, and the transmission time distribution. Therefore, in the power-saving design of a wireless sensor network, two ND policies should be adopted to control the sleep/wake-up mode of the radio server according to the concrete network parameter setting, such as the traffic intensity, the transmission time distribution, and the power consumption elements es and eh.It is expected that the data results in Tables1 and 2 are useful and helpful for the network designers and practitioners in the military and other related fields.


## 6. Conclusion

This paper studies the queue size distribution for the discrete-time Geo/G/1 queue with a new ND policy and its computation designs in the power-saving optimization of a wireless sensor node. Numerically, we illustrate the optimal policy thresholds and the minimum power consumptions under the N, D, and two ND policies. The numerical comparison illustrates that two ND policies are superior over the N and D policies from the viewpoint of the minimum power consumption. The superiority of two ND policies is dependent on the concrete network parameter setting. These results may be useful for the network practitioners in the related fields. In the future, the discrete-time queues involving the D policy and their applications will be our further works.



---

*Source: 6364352-2021-10-22.xml*