{'fraction_non_alphanumeric': 0.035534221976655844, 'fraction_numerical': 0.011326749084881552, 'mean_word_length': 4.439331329827198, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Queueing Analysis of Dynamic Power Management Schemes for Mobile Devices

In this paper, we analyze a queueing system under the dyadic server control, workload control and delivery deadlines of data blocks. From the viewpoint of efficient power management for the wireless interface of a smart mobile device, we first focus on deriving the mean length of an arbitrary cycle time and then investigate the mean energy expenditure during the cycle. Some numerical examples are shown with respect to several control parameters. We conduct simulations to evaluate the proposed analytic energy consumption models. Experiments are also performed by implementing a test program on an off-the-shelf smartphone. Our results can serve as quantitative guidelines for the efficient power management of wireless interfaces in mobile devices.


I. INTRODUCTION A. BACKGROUND AND MOTIVATION
Smart mobile devices play important roles in daily life because they are the dominant media through which users connect Internet services [1]. In this field, battery power management has always been a major concern because it is one of the most crucial resources for mobile devices [2]. However, the power needs of high-end smart mobile devices cannot be met with the performance of modern batteries, and the discrepancy is increasing every year [3].
To satisfy the higher power efficiency of mobile devices, many hardware-level or firmware-level solutions have been proposed [4], [5]. Most of these works tried to reduce the power consumption of individual hardware modules [6]- [8]. However, the wasteful use of high-power hardware modules by software applications may vastly increase the power consumption of a mobile device [9], [10]. Therefore, there is a great demand for applications that can efficiently support power management by restricting the reckless use of high power modules.
The associate editor coordinating the review of this manuscript and approving it for publication was Yi Zhang. In particular, efficient power managements is required for the wireless interface (WI), which is one of the most power-consuming modules in a mobile device [11]. 1 To efficiently manage the power of WI modules, dynamic power management (DPM) is widely adopted. According to the operation state of the WI, DPM systems support multiple power modes, such as active modes (e.g., transmit, receive, and idle modes) and inactive modes (e.g., sleep mode and powered off) [12]. Generally, an active-mode WI consumes much more power than an inactive-mode WI, even when in idle mode. Switching the WI to an inactive mode whenever it does not have any data to send or receive is an essential scheme to reduce its energy expenditure. Therefore, most DPM systems fundamentally employ a timeout-based shutdown policy.
However, the required overhead energy and boot/cooldown time for turning on/off the WI are not negligible [13]. Therefore, there is a tradeoff between the wakeup overhead incurred by turning the WI on/off frequently and the power conserved by turning the WI off when in idle mode, which is also an active mode, for some amount of time. To achieve this tradeoff, multiple sleep modes are employed in most upto-date DPM systems [15], [16]. 2 There is a DPM scheme that provides two sleep modes: deep sleep and light sleep. In other words, in addition to a deep sleep mode, in which power consumption is very low the consuming power is very low but the wakeup overhead is high, there is a light sleep mode, in which power consumption is relatively high but the wakeup overhead is lower than that in the deep sleep mode. 3 To reduce the wakeup overhead in a DPM scheme, we need to restrict active/inactive mode transitions efficiently. A delayed wakeup method can be a simple solution. In the suspended wakeup method, the WI will awaken only after waiting some amount of time following a transmit request instead of being activated immediately. Then, any forthcoming transmit requests submitted during the suspended time will be transmitted all at once during the next incoming WI activation. However, the method described above has two main problems. One is the overflow of the transmission queue due to increased amounts of pending data for transmission; the other is the tediously protracted delay in transmitting data.
In previous studies conducted by our research group [17], [18], a carpool-based suspended wakeup scheme was proposed that turns on the WI when either of the following two events occurs: (a) the total size of the pending data blocks exceeds the predefined workload threshold, or (b) the waiting time of any data blocks queued for the transmission exceeds the predefined time threshold (i.e., the deadline). After being activated once, the WI transmits all the pending data blocks until no data blocks are left in the transmission queue. These previously studies empirically verified that this carpool-based scheme consumes less power than the legacy DPM system and does not violate spatial or temporal constraints. However, analytical results were not provided for the scheme.
There are two main reasons that it is highly desirable to build analytic models of power consumption for power management schemes such as the legacy DPM, enhanced DPM, and carpool-based suspended wakeup schemes The first reason is that analytic models can present quantitative guidelines for the efficient power management of the WI, for example, by predicting the expected energy consumption according to various environmental parameters. The second is that an analytic power consumption model can be exploited to determine the optimal solution for various system parameter settings.

B. ANALYTICAL STUDIES ON ENERGY CONSUMPTION MODELS
Several studies have been performed on the analytic energy consumption models. Okamura and Dohi [19] proposed an analytical method to find out the optimal timeout interval to minimize energy consumption. They employed the legacy DPM method for general embedded systems (such as the hard disk drive or CPU) rather than the WI. The work in [19] considered the MAP/G/1 queueing model with vacations. Jiang et al. [20] developed an analytic energy consumption model considering the legacy DMP for the WI module using semi-Markovian control processes and proposed a solution to determine the optimal timeout interval by utilizing the developed energy consumption model. Luiz et al. [21] found the optimal timeout interval and the optimal threshold data rate for the WI under the DPM method with a timeout-based shutdown policy. They proposed an energy model to maximize the performance (i.e., response time) and minimize energy consumption; however, they did not analyze the multiple sleep modes or the carpool-based suspended wakeup scheme. Moreover, the power variations among various operating modes (i.e., Tx mode, Rx mode, and idle mode) and real-time data with delivery deadlines were not investigated.
Most previous studies focused on the optimal timeout interval to reduce energy consumption under the legacy DPM method. However, enhanced schemes such as the DPM with multiple sleep modes (i.e., the enhanced DPM) and the carpool-based suspended wakeup scheme should also be analyzed. Real-time data, which have delivery deadlines, should also be considered because most smartphone applications are subject to real-time constraints.

C. CONTRIBUTIONS
We present mathematical energy consumption models according to dynamic power management techniques, including the legacy DPM scheme and the carpool-based suspended wakeup scheme established on top of the legacy DPM method. In the Appendix, we also present analytic models of the enhanced DPM and carpool-based suspended wakeup scheme established on top of the enhanced DPM. The proposed analytic models further consider real-time characteristics (i.e., the delivery deadline for a data block queued for transmission).
The operational behavior of our system can be modeled with a queueing system that has the dyadic server control (i.e., the D-policy and deadline policy), activation/deactivation delays, and idle timeout periods. Some queueing studies have addressed the D-policy, but no study has simultaneously considered the above operational behaviors. For more details on the analysis of D-policy queues and dyadic policies, readers may reference [23]- [25]. The preliminary version of this study has been presented as a conference paper [22]. This paper features the following major contributions: 1) We modeled a complex queuing system that has the dyadic server control for the carpool-based suspended wakeup scheme, which was presented in our previous study [17]. 2) We derived the expected energy expenditure for delivering data blocks by exploiting the presented queueing system. 3) We provided numerical examples by varying several system parameters. VOLUME 8, 2020 Our theoretical results may support the design for an energy optimization scheme under the operating characteristics of the complex queueing system, and our findings will be exploited in quantitative guidelines for the efficient power management of WIs.
The remainder of this paper is organized as follows. Section 2 presents our system model, and we analyze the queueing system for the carpool-based scheme in Section 3. The analysis of the power consumption is provided in Section 4, in which we derive the expectation of energy expenditure per data delivery. We conduct a performance evaluation in Section 5, including illustrations of several numerical examples, simulation results, and experimental measurements by implementations, and the conclusions are presented in Section 6. In the Appendix, we analyzed the enhanced DPM scheme for efficient power management.

II. SYSTEM MODEL
In this paper, we employ the system model presented in [17]. A mobile device embeds one WI and connects to the Internet through the nearest wireless access point. The WI employs the legacy DPM method, in which the WI operates in either active mode(including transmit mode, receive mode, and idle mode) or inactive mode. Fig. 1 shows a diagram of the dynamic power modes and their transitions. The legacy DPM scheme employs the timeout-based shutdown policy, in which an activated WI is autonomously deactivated if it continues to be in idle mode for longer than the predefined time (i.e., the idle timeout value). The deactivated WI is immediately activated (i.e., awoken from sleep mode) by an event such as a Tx or Rx request. Activating or deactivating the WI requires some delay time while consuming the maximum power. We assume that the activation/deactivation delay time is constant. To reduce the wakeup overhead, a carpool-based suspended wakeup scheme was proposed in our previous study [17], in which the deactivated WI wakes up only if one of the predefined trigger conditions is met, instead of being activated immediately. Then, any forthcoming transmit requests submitted during the suspended period will be transmitted all at once during the next incoming WI activation. The wakeup triggering conditions are as follows: 1. The delivery deadline of any pending Tx data blocks in the Tx queue will be missed. 2. The total size of pending Tx data blocks in the Tx queue will cause an overflow. 3. Any other events trigger the activation of the WI. Fig. 2 shows a flow diagram of the system operation of the carpool-based suspended wakeup scheme. For clarity, let us state some important concepts regarding the terms in the general queueing literature. Hereafter, we refer to the WI, data blocks, and the size of a data block as the server, customers, and service time of a customer, respectively. We assume that the arrival process of a customer is a Poisson process with the rate λ, the service time follows an exponential distribution with the parameter µ, and the delivery deadlines of data blocks are exponentially distributed with the parameter η. The notations for the analysis are summarized in Table 1. In Table 1, the time unit is second.  The horizontal red bars indicate the given deadlines of each customer. The idle server waits until one of the two conditions is met and is then activated. The two cases are described as follows. Case A shows that the idle server is activated because the accumulated workload during an idle period (i.e. the total sum of the service times of the three customers in Fig. 2) exceeds the predetermined workload threshold D before the deadline is missed. Case B demonstrates that the idle server is activated because the deadline of a waiting customer is passed before the accumulated workload exceeds D. The system operates in the following succession regardless of cases A and B: idle period, activation delay, busy period, idle timeout period, and deactivation delay. Therefore, we define a cycle as the length from the start of an arbitrary idle period to the end of the deactivation delay. We also assume that if a customer arrives during the idle timeout period, the server starts its service immediately.

III. ANALYSIS OF THE QUEUEING SYSTEM
In this section, we focus on deriving the mean length of an arbitrary cycle E(C). As mentioned before, a cycle consists of the same elements in the same order regardless of cases A and B (see Fig. 2). Therefore, We assume that the activation delay ( ) and the deactivation delay ( ) are both constant with separate values. Therefore, we need to find the expected lengths of the idle period, the busy period, and the idle timeout period.
The expected lengths of the idle period and the busy period are, by the total expectation theorem, as follows: (2) In (2) and (3), the probability that an arbitrary cycle is Case A or Case B can be obtained by Theorem 1. Theorem 1: In an M/M/1 queueing system under the D-policy and deadline policy, the probabilities of Case A and Case B are as follows: In Case A, the busy period always starts because the workload exceeds the threshold D (and the deadlines of every waiting customers are not missed). During an idle period, if the service time of the first customer is greater than, the server immediately starts its busy period with a probability of e −µD . To start a busy period with two waiting customers during an idle period, the first customer's service time should be less than or equal to D, while the second customer's service time should be greater than D − x, and the second customer must arrive before the deadline of the first customer: To start a busy period with n waiting customers during an idle period, the sum of the foremost n − 1 customers' service times (x) should be less than or equal to D, the nth customer's service time should be greater than D − x, and the customer must arrive before any of the deadlines of (n − 1) waiting customers are missed. This probability is expressed as By considering all possible cases, After simplification, we obtain (4). Because events A and B are mutually exclusive, we have (5 VOLUME 8, 2020 Proof: From the proof of Theorem 1, Pr(N A = n) is obviously the expression in (6). In Case B, the idle server is always activated by passing the deadline of a waiting customer before the accumulated workload exceeds D. To start a busy period with the first customer, the service time of the first customer must be less than or equal to D, and his/her deadline should be set before the second customer arrives. This probability is (1 − e −µD ) η λ+η . To start a busy period with two waiting customers during the idle period in Case B, the sum of the first and second customer's service time should be less than or equal to D, and one of the deadlines of these two customers should be set before the third customer arrives. This probability can be derived as follows: By considering the event that there are n customers at the start of the busy period, we can derive After simplification, we have (7). Note that (5) can also be calculated by using (7) with Pr(B) = ∞ n=1 Pr(N B = n). Corollary 2: The conditional expected lengths of the idle period for Case A and Case B are Proof: Let us consider Case A with n customers at the beginning of the activation delay. In this case, the idle period is the sum of the interarrival times of every customer who arrives when the server is idle (see Fig. 2(a)). Therefore, by using the memoryless property of the exponential distribution, the conditional expected time length of the idle period is the sum of the following: 1) Interarrival time of the first customer 1/λ, 2) Interarrival time of the second customer 1/(λ + η), . . .

3)
Interarrival time of the nth customer 1/(λ + (n − 1)η). Note that the expected minimum length of two or more exponential distributions is a reciprocal of the sum of parameters.
In Case B, the idle period is slightly but definitely different from that in Case A. In Case B, the mean length of the idle period is the sum of n customers' interarrival times and the length of the exponential distribution with the parameter λ + nη. This is because the server activates when the deadline of any customer is missed before the sum of their service times exceeds D (see Fig. 2(b)). By the definition of conditional expectation, we finally have (8) and (9).
From (8) and (9), we can rewrite (2) as follows: An arbitrary busy period is a delay cycle with an initial delay of the accumulated service time during an idle period. The initial delays for Case A and Case B are E(N A )E(S) and E(N B )E(S), respectively [25], [26]. In this paper, we assume that the service time distribution is an exponential distribution with the rate µ, E(S) = 1/µ. Therefore, the expected length of the busy period in each case is From (10) and (11), (3) becomes To complete (1), we now need to determine the expected length of the idle timeout period T p because the length of this period is not a constant but rather a random variable. Fig. 4 shows a sample path of the workload during the idle timeout period. After a busy period ends, the server has an idle timeout period with a time length of T . If a customer arrives during T , the server immediately starts its service until there is no customer in the system; this process is exactly the same as the busy period of an ordinary M /M /1 queue. If no customer arrives during T , the server deactivates. The expected length of the idle timeout period can be obtained from Theorem 2.

Theorem 2: The expected length of the idle timeout period for an M/M/1 queue is as follows:
. (12) Proof: Let us define Q 0 as the event in which no customer arrives during T and Q c 0 as the complementary event of Q 0 . By conditioning the number of arrivals during T , we can obtain the mean length of the idle timeout period T p . If no customer arrives during T , the conditional expectation of T p is obviously T ; otherwise, the conditional expectation is the sum of the following: (i) the interarrival time, which is less than T , (ii) the busy period of an ordinary M/M/1 queue Fig. 3), and (iii) the expected value of T p . Therefore, After simplification, we have (12).

IV. ANALYSIS OF POWER CONSUMPTION
In this section, we derive the amount of energy expended per cycle and the mean time length for data delivery per cycle U . Let us define γ t as the energy expenditure (J , joules) per unit time during a time period t, and generally, γ > γ = γ B p > γ T γ I p . From Corollary 2 and Theorem 2, (13) Note that the fourth term on the right-hand side of (13) is not simply E(T p )γ T p because T p is composed of some time lengths that need different types of energy expenditure.
The energy expenditure during an idle timeout period γ (T p ) can be obtained by the same argument in Theorem 2 as follows: After simplification, we have Let us denote T U p as the data delivery time during the idle timeout period within the cycle; then T U p can be obtained as follows: Because U is the sum of the expected length of the busy period and T U p , We finally have the total energy expenditure per delivery of a data block 4 ψ = /U from (13) and (16).

V. PERFORMANCE EVALUATION A. ANALYTICAL RESULTS
In this section, we illustrate simple numerical examples and then discuss the computational results.
We assume that = 2 s, = 1 s, γ I p = 0.1728 mW, γ = γ = 997.2 mW, γ B p = 997.2 mW and γ T = 169.2 mW, which were also employed in [17]. Fig. 5 shows multiple graphs of the energy expended per data delivery (i.e., ψ) for varying parameters under the abovementioned conditions. In each graph in Fig. 5, the dashed line depicts the result of M/M/1 queue under the legacy DPM system, and the solid line shows the result of the carpool-based suspended wakeup scheme established on top of the legacy DPM system. We can see that the carpool-based suspended wake up scheme (i.e., the D-policy and deadline policy) is much more efficient than the legacy DPM policy from an energy conservation perspective.
In Fig. 5(a), we varied D while keeping λ = 0.3, µ = 0.5, η = 0.05, and T = 2. As we expected, ψ decreases as D (i.e., the size of the Tx queue) increases. This is because an increase in D may allow more data blocks awaiting transmission to stay in the transmit queue before the WI is activated, which increases the effect of our carpool policy. Note that the slope gradually decreases as D increases, and almost becomes saturated when D is greater than 14.
In Fig. 5(b), we varied the delivery deadline while keeping λ = 0.3, µ = 0.5, T = 2, and D = 10. ψ decreases as the delivery deadline of each data block increases. This is because an increase in deadline may allow the data blocks awaiting transmission to stay longer in the transmit queue. Fig. 5(a) and Fig. 5(b) show that ψ under the legacy DPM scheme is a constant because D and deadline cannot affect the system performance.
In Fig. 5(c), we varied λ while keeping µ = 0.5, η = 0.05, T = 2, and D = 10. As λ increases, the energy expended per data delivery (i.e., ψ) decreases because the WI takes less time in its idle mode. In the idle mode, the WI is active; thus, the WI consumes a large amount of energy but does not transmit any data.
In Fig. 5(d), we varied T while keeping λ = 0.3, µ = 0.5, η = 0.05, and D = 10. As T increases, power consumption decreases.   Our system is a versatile M/M/1 queue; therefore, we can obtain the results for various systems as special cases by setting several system parameters as follows:  (11). Therefore, we tried to provide refined mathematical results for rapid calculations. This is one of the main contributions of this paper.

B. SIMULATIONS
For a practical performance evaluation, we conducted simulations with practical power consumption parameters, by referring to the data sheet of an off-the-shelf Wi-Fi module as shown in Table 2 [27]. For the simulation, the same assumptions and system parameters used in the Analytical Results section are employed. We assume that the WI's transmission speed is 11 Mbps, the wakeup time (i.e., the activation delay) is 2.0 s, the deactivation delay is 1.0 s, and the idle timeout T is 2.0 s. The size of a data block is set to 1.75 MB, and the data transmission requests occur as a Poisson process with a rate λ. The energy expended per data delivery is measured over the total simulation time of 3,600 s. Legacy DPM stands for the legacy dynamic power management scheme introduced in the System Model section, and carpool refers to the carpool-based suspended wakeup scheme illustrated in Fig. 2. We used MATLAB v.8.5 as a simulation tool, and each simulation was repeated 1,000 times and averaged. Fig. 7(a) shows the average energy expended per data delivery while varying the Tx queue size when λ is 0.3 and the delivery deadline is 20 s. As we expected, the energy expended per data delivery in carpool decreases as the Tx queue size increases, which is similar to the analytical results  shown in Fig. 5(a). Fig. 7(b) shows the average energy expended per data delivery while varying the delivery deadline length when Tx queue size is 20MB, and λ is 0.3. As we expected, the energy expended per data delivery in carpool decreases as the delivery deadline length increases, which is similar to the analytical results shown in Fig. 5(b).
To show the results with a different traffic arrival model, we conducted simulations where the traffic occurs by following the flash crowds traffic model, which is suitable for emulating a burst of traffic [28], and we added the results to Fig. 8. Fig. 8(a) shows the average energy expended per data delivery while varying the flash crowds outbreak interval where the flash duration is 150 s, flash peak (i.e., maximum Tx request arrival rate) is 0.6, the maximum queue size is 100 MB, and the delivery deadline of each data block is set to 20 s. As flash crowds occur more often, carpool shows less energy expenditure than legacy DPM. Fig. 8(b) shows

C. EXPERIMENTAL MEASUREMENTS
For the experimental measurements, we implemented a test program on a test bed, which consisted of an off-the-shelf smartphone, a Wi-Fi access point, and a server, as shown in Fig. 9. The smartphone was embedded with a 2.2 GHz 64-bit Snapdragon 820 quad-core processor, 4 GB of memory, an 802.11ac Wi-Fi module, and a 2,800 mAh battery, and the phone operated on the Android platform. The test application was developed in JAVA. To obtain more accurate results, we did not execute any applications beyond the test program and system-related processes, and we disabled all wireless interface modules of the smartphone other than Wi-Fi during the experiment.
The total energy expended during 1,800 s was measured as the percentage of the battery capacity of the smartphone for legacy DPM and carpool. The requests for data transmission occurred following a Poisson process with a rate λ. The experiments were repeated 10 times for each scenario, and the results were averaged.

VI. CONCLUSION
In this paper, queueing analyses for the legacy DPM, enhanced DPM, and carpool-based suspended wakeup schemes were proposed. For the efficient power management of the WI, we derived theoretical results that can support the power optimization for a complex queueing system that is operated under the dyadic server control, workload control and delivery deadlines of data blocks. We derived all the results in the exact and refined form with system parameters for practical uses and rapid calculations. The results derived can be exploited to provide quantitative guidelines for the efficient power management of the WI. To evaluate the proposed analytic energy consumption models, simulations and experiments on an off-the-shelf smartphone were also conducted. In some performance evaluations, it is shown that the carpool-based suspended wakeup scheme reduces the energy expended per data delivery by up to 30% compared to legacy schemes (i.e., the legacy DPM or enhanced DPM schemes).

APPENDIX
In this section, we introduce an enhanced DPM that provides two sleep modes and present an analytic power consumption model using queueing theory. We also present an analytic power consumption model of the carpool-based delayed wakeup scheme established on top of the enhanced DPM. To achieve a tradeoff between wakeup overhead and energy conservation, multiple sleep modes are introduced into the DPM scheme [15], [16]. Fig. 11 illustrates a diagram for the dynamic power modes and their transitions in the enhanced DPM with multiple sleep modes. The WI in an active mode (i.e., Tx, Rx or Idle modes) switches to the light_sleep mode if it continues to be in idle mode longer than light_idle_TIMEOUT. The mode transition from active mode to light_sleep mode requires a certain time (i.e., the light_deactivation delay), which is far smaller than the heavy_deactivation delay. We considered an extended idle timeout period with two phases. Fig. 12 illustrates a sample path of the idle timeout period in the enhanced DPM. From the same argument of Theorem 1 and Section IV, we can obtain (17)- (20) corresponding to (12), (14), (15), and (16).  γ (T p ) = e −λT 1 · e −λT 2 (T 1 γ T 1 + 1 γ 1 + T 2 γ T 2 )  Fig. 13 shows multiple graphs of the energy expended per data delivery for varying parameters. T 1 = 0.5, T 2 = 1.5, and other parameters are the same as those for Fig. 5. The dashed line depicts the results for the enhanced DPM system, and the solid line shows the results for the carpool-based suspended wakeup scheme established on top of the enhanced DPM system. The results also show similar trends to those shown in Fig. 5.
The power expended in the light_sleep mode is lower than that in the active mode but higher than that in the deep_sleep mode. The WI in the light_sleep mode is immediately activated whenever any Tx/Rx event occurs, which requires a light_Activation delay. The light_Activation delay is far smaller than the deep_Activation delay. The WI in the light_sleep mode switches to the deep_sleep mode if it continues to be in idle mode longer than idle_TIMEOUT. The behavior in the deep_sleep mode is the same as that in the legacy DPM.