WIXLIB

3are given in Section 7.2R ELATED W ORKCloud computing has been intensively investigated basedon off-the-shelf cloud infrastructures, such as resources/trafficoptimization of backhaul networks [16], services admissioncontrol [17] and scheduling [18], and pricing strategies ofusing commerce cloud services [19], [20], etc. However, existing cloud computing models are designed for traditional webapplications, rather than future Internet applications runningon various mobile and sensor nodes.Due to the emerging development of mobile Internet, morerecent works show great interests in dealing with mobileapplications in the context of cloud computing. Some stateof-art literature [3], [21] in mobile cloud computing (MCC)reveal that the energy issue is one of the major challenges. Theissue of energy efficiency in future computing has also beenextended to the sensor cloud computing. Alamri et al. in [22]provide a comprehensive survey of sensor cloud architecture,approaches and applications. Perera et al. in [23] proposea middleware design for IoT and balance the computationand communication energy between sensor nodes and cloudservers. Yuriyama et al. in [24] propose the concept of virtualsensors by collecting different vertical application data intoa single horizontal platform which can behave as a sensornode to reduce extra communication between networks. Thereare also sensor cloud applications in body sensor networks[25] and truck monitoring [26], etc. Although various sensorcloud schemes have been developed to increase bandwidthefficiency, the sensor nodes are usually assumed as datacollecting points and there is lack of understanding of theirprocessing capability and the potential benefits of being acomputing node.As a contrary, edge computing [27], [28] has been considered to provide computing, storage, and networking servicesbetween end devices and traditional Cloud Computing datacenters, typically, but not exclusively located at the edge ofnetwork. A comparable concept has also been proposed byCisco with the name of fog computing [29]. Since mobilesensor nodes now rival many PCs in terms of computationalpower [6], they have the opportunity to talk directly toone another when possible and handle much of their owncomputational tasks. Moreover, an emerging wave of sensorapplications, requires mobility support and geo-distributionin addition to location awareness and low latency. In ourpreliminary study [30], we have already developed a prototypeto connect an On-board diagnostics (OBD) sensor device tothe cloud via smart phone, where the data analysis engine canbe deployed in either smart phone or cloud, depending on thesize of the processing data and service requirements. A similarconcept of crowd computing [31] has also been proposed tobring together the strengths of crowdsourcing, automation andmachine learning.In this paper, our contribution is to further leverage thecomputation capability of sensor nodes into computing andconsider a joint optimization of both computation and communication energy across mobile wireless sensor nodes to transferand process sensor data and disseminate results to appropriateparties. To the best of our knowledge, this is the first work thatconsiders sensor node as a service and realizes cooperativecomputing in MWSN.3S YSTEM M ODELANDE NERGY F ORMULA -TIONIn this section, we introduce the application model, its execution on sensor node and transmission over wireless channel.Specifically, the energy consumption of both computation andcommunication are formulated.3.1Application ModelWe consider the cooperative computing in which eachsensor node can execute lightweight applications with the helpof peer sensor nodes. In order to characterize an application,a canonical model [32] that captures the essentials of atypical application is considered and can be abstracted intothe following two parameters: Input data size L: the total number of data bits as the inputof an application. Such input data can be partitioned andoffloaded to a peer sensor node for remote processing andexecution [33]. Application completion deadline T : the maximum number of time slots that an application must be completed.t is the discrete time index ranging from t 1 to t T .It is worth noting that an application is a program thatperforms a computation on an input file, such as calculating thenumber of violate data from a period of history record. Similarto the model applied in MapReduce [34], we consider that anapplication can be breakable into tasks which do not exhibitdependencies across partitions of its input. We assume thatall sensor nodes are capable of executing a same applicationwithout need to transfer executable files for operation, thusonly the input partitions are transmitted to other sensor nodesfor parallel executions. Although there are cases that sometasks cannot be broken into smaller pieces and can only beexecuted on a single node due to the dependencies in its input,there are still concurrency benefits when many such tasks areexecuted in batches.The energy consumption of an application is highly relatedto these two parameters. For example, with a large size of inputdata and stringent completion deadline, a sensor node mayconsume extensive energy. In the following, we denote suchan application as A(L, T ) and use it to characterize the energyconsumption of computation and communication, respectively.3.2Computation Energy ConsumptionThe energy consumption of computation is directly determined by the CPU workload of an application. Accordingto [35], the workload can be measured by the number ofrequired CPU cycles, which is related to the input data sizeand computation complexity, and is defined asW LX ,(1)

4where W is the total number of required CPU cycles, L isthe input data size and X is the computation algorithm. It isnoted that with a same size of input data, the required cycledemands often vary greatly, which depend on the nature ofapplications [36], e.g., applying an input data to calculate theaverage and factorial show distinct computation complexities.In the existing literature [36]–[38], X has been shown as arandom variable and can be modeled by a Gamma distributionwhich is commonly used to model service times [39], and hasbeen shown to work well in characterizing the distribution ofCPU cycle demands [32], [37].Although a number of factors consume CPU power, suchas short circuit power and dynamic power, etc., the energyconsumption is dominated by dynamic power which can beminimized by configuring the clock frequency of the chip viathe Dynamic Voltage Scaling (DVS) technology2 [40]. As aresult, the total energy consumption of computation is givenbyWWXXEc c (w) κfw2 ,(2)w 1w 1where c is the computation energy per operation cycle, κis the effective switched capacity determined by the chiparchitecture and fw is the clock-frequency which is scheduledin the next CPU cycle given the number of w CPU cycleshave been completed.A careful reader may notice that the CPU can reduce itsenergy consumption by scheduling low clock frequency. However, as a practical implementation, the application has to meeta completion deadline. Without deadlines, there is no particularreason to complete any given task by a certain time. We usethe soft deadline to characterize probabilistic performance, thatis, the statistical CPU scheduling model [32] which assumesthe application completion needs to meet its deadline with theprobability p by allocating Wp CPU cycles. The parameter p isthe application completing probability (ACP). In other words,the probability of an application requires no more than theallocated Wp should satisfy FW (Wp ) P r[W Wp ] p.This soft real-time scheduling integrated with DVS has beenshown its effectiveness in saving energy without substantiallyaffecting application performance [36].According to (1), since W is a linear function of X, we 1 1can obtain Wp LFX(p), where FX(p) is the inversecumulative distribution function of X. Therefore, the totalenergy consumption can be derived assome constants µ 0 and ν 0. It is noted that with w ,the probability goes to 0, which means it is unlikely that anapplication cannot be completed with a large number of CPUcycles.Theorem 3.1 [32]: For the optimal clock-frequency schedulingPWinp each CPU cycle (fw ) and the deadline requirement( w 11/fw T ), the minimum computation energy canbe derived asEc Wpκ X c[F (w)]1/3 }3 , and also has Ec L3 . 2{T w 1 WSimplifying the above result, we have the optimal computationenergy asKL3.(4)Ec T2where K is a constant factor determined by κ and p. The resulttells that allocating a smaller size of input data or relaxing thedeadline can achieve better computational energy efficiency,which means that a sensor node can prefer to execute delaytolerant applications or offload more tasks to peer node, inorder to save its own computation energy.3.3Communication Energy ConsumptionWhen a sensor node considers to offload its tasks to a peernode, the energy consumption is determined by the number ofbits being transmitted over wireless channel.The energy consumption of communication is determinedby the current draw of the electrical circuits that implementsthe physical communication layer. In practice, it includes idle,transmit and receive modes. According to the specificationsof IEEE 802.11n [41] or IEEE 802.15.4 [42], [43], the energyconsumption of a wireless sensor node is dominated by thetransmit or receive modes, and has their costs are approximately the same. So we consider the communication energyincluding both transmission and reception of processing tasks,and do not consider the small output results3 from the node.The communication cost is characterized by the empiricaltransmission energy model [45], and the required energy Et totransmit L bits is governed by a convex monomial function4Et ρLn.g(5)cwhere FW(w) is the complementary cumulative distributionfunction (CCDF) that the application has not completed afterw CPU cycles. Since the Gamma distribution is exponentiallyctailed, the CCDF can be assumed as FW(w) µe νw forwhere ρ denotes the energy coefficient, g denotes channel stateand n denotes the order of monomial with value 1 n 5.According to [45], the choice of n depends on the bit schedulerpolicy. With an increasing value of n, the scheduler moreprefers to transmit equal number of bits at every time slotregardless of the channel state. However, in this paper, weconsider the optimal case of n 1 which is called one-shotpolicy [47], in which the transmission only depends on thechannel state and is completed in one time slot. There are2. DVS is commonly used to save CPU energy by adjusting the speedbased on required cycle demands. It exploits an important characteristicof Complementary Metal Oxide Semiconductor (CMOS)-based processors:When operation is at low voltage, the clock frequency scales as a linearfunction of the voltage supply. The energy consumed per cycle is proportionalto the square of the voltage.3. This is a reasonable assumption for sensor computing where most ofsensor based applications come with simple results of warning or imagedetection indication [44], etc.4. Although the monomial cost does not hold for operation at capacity inAWGN channel, there is a practical modulation scheme to well approximateby a monomial [46].Ec κWpXcFW(w)fw2 ,(3)w 1

5several reasons for applying this scenario: First, for energyconstrained sensor node, it may not be desirable to splita single data across multiple time slots because of extraenergy consumed by a large overhead associated with eachslot. Second, since we impose a deadline to complete anapplication, the transmission time should be relatively smallcompared to T , such that the time offset between local andremote executions can be negligible. Third, in MWSN, thetransmission time over the air should be minimized to avoidchannel fluctuation caused by node mobility. In order to ensurethe optimal performance of the policy, the scheduler shouldbe opportunistic, that is, to offload tasks to a peer node withgood channel quality. The scheduling policy has been provedits effectiveness in combating channel fading [6].4 E NERGY O PTIMIZATIONC OMPUTINGFORC OOPERATIVEOur interest is to find an optimal partition to minimizethe total energy consumption of processing an applicationgiven that a target completion deadline T is satisfied by usingcooperative computing, and can be formulated asmin Ecl (ll , t) Et (lr , gl,r ) Er (lr , gr,l ) Ecr (lr , t)ll ,lr{z} {z} local energy costs.t.remote energy costll lr Lt T.(6) Ecl and Ecr denote the local and remote computationenergy consumption, and Et and Er denote transmission andreception energy consumption, respectively. ll and lr are partitioned input data size for local andremote processing. A symmetric channel is assumed betweenlocal and remote sensor nodes and has channel gain gl,r gr,l .A completion deadline T is considered to ensure Quality-asService.Theorem 4.1: The optimal input data partition to minimizethe total energy consumption of processing an applicationA(L, T ) in MWSN, is given byLβLβ , lr ,(7)26αL26αLThe corresponding minimum total energy consumption isll Etotal (ll , lr ) αL3βLβ2 .4212αL(8)where α TK2 , β g2ρ, K denotes the computationl,rcoefficient, ρ denotes communication coefficient of wirelesschannel and gl,r is the channel gain.Proof : See Appendix A. In general, we find that the minimum total energy consumption can be achieved by optimally partitioning, offloading andexecuting the input data via cooperative computing, which canbe determined by the application profile, hardware configurations of sensor nodes and wireless channel conditions. In thefollowing, we further investigate the individual behaviors ofthe optimal partition and analyze how the system parametersaffect the overall performance.Proposition 4.2: The size difference of the optimal inputdata between local and remote executions isdif f (L, T, K, ρ, gl,r ) 2ρT 2.3gl,r KL(9)β. UsingProof : The result follows (7) and has dif f 3αL2ρKα T 2 and β gl,r into the result leads to (9). In essence, we can observe that the optimal partition highlydepends on system parameters. Specifically, the local executionis preferable when (9) tends to increase (i.e., small data sizeL, long completion deadline T , high transmission cost ρ, lowcomputation cost K or high channel loss gl,r ). Otherwise, theremote execution is preferable.Result 4.3: By defining the application processing speedas υ TL , we have the equivalent energy optimal computingrulesq 2ρ if 0 υ 3Kg Local computing, l,r qq2ρ 2ρ υ Cooperative computing, if3Kgl,r3Kgl,r q Cloud computing, 2ρif υ3Kgl,r(10)Proof : According to (7), since L2 ll L, we shouldβhave 0 6αL L2 for data offload. Thus, the lower boundof application processing speed can be achieved assL2ρ .(11)T3Kgl,rβ L2 , only the local computing is applied. Furwhen 6αLthermore, considering the cloud computing case where sensornodes only collect and transmit input data to an enterprisecloud server via gateway for execution, we obtain the upperbound condition of using cooperative computing from (5) and(8) assαL3β2L2ρ Etotal (ll , lr ) Et .412αLT3Kgl,r(12) We observe that when the application prefers cooperativecomputing, it can always achieve better energy efficiency thanthe local computing case. Moreover, the cloud computing isonly applied when high processing speed is required.Proposition 4.4: For cooperative computing, the boundperformance of computation to communication energy ratioof local and remote nodes areKgl,r 2ErEcl υ c .Et4ρEr(13)Proof : See Appendix B. The result tells that the proposed optimal solution can bestachieve the local computation energy and have the minimalenergy ratio. Assuming the application processing speed canbe closed to its lower bound in (11), the local computationenergy can be achieved as close as 1/6 of transmission energy,which is promising to show the advantage of using cooperativecomputing in MWSN. Such ratio can be higher, depends onthe preference of application processing strategy and system

6According to (8) and (15), the expected value of the optimalenergy consumption is Z 32αLρ2 r2aE [Etotal ] 2λπ ρLra re λπr dr43αL0Expected total energy comsuption (Etotal) (µJ)69.5Simulation resultNumerical analysis69Z Z 2αL3 λπr2redr ρLra 1 e λπr dr 2λπ[40Z 0 2 2a 1ρ r λπr 2edr] 3αLq 0 32 αL a 1ρLa!! a 1 1 ρ a! a , if a is odd4λ3αL(λπ)2 2 (λπ) 2 αL3 ρL( a2 a)! ρ2 a! a ,if a is even43αL(λπ)268.5path loss a 468path loss a 367.5path loss a 2(λπ)(16)6711.52Density of nodes (λ)2.5Fig. 2. Comparison of optimal energy consumption between simulation and numerical analysis: L 1024 bits,T 20 ms, ρ 0.006 and K 10 10parameters. Moreover, the cooperative computing can alsohelp reduce the remote computation energy. Especially, withfewer offloading bits, the remote computation energy decreasesat a faster pace than the communication energy. The upperbounded is govern by the system parameters and maximumnumber of bits can be offloaded. The result is useful whenselfish nature is imposed to individuals, because reducing theenergy consumption for helping nodes can largely improvetheir willingness of cooperation.In addition to the individual performance, we also providean analytical result to characterize the average performanceof the optimal solution. We assume that sensor candidates arerandomly located in space according to a Poisson point processwith density λ. An application initial node (IN) will choosethe best cooperation node (CN) to achieve the minimum totalenergy among all available candidates. A network with ahigher density of sensor nodes can have better choices to selectCN.We consider a simple channel model where gi,j betweenthe nodes i and j is modelled as gi,j 1/dai,j , where di,jis the distance between the nodes i and j, a is the pathloss exponent and usually characterized as an integer valuea 2. Given the identical system parameters (i.e., K andρ), the selected CN distance to achieve the minimum Etotalwill be as close as possible to the IN. We let r be a randomvariable of the selected CN distance to the IN, and r denote thedistance between the closest CN and the IN. The probabilitydistribution function of r is given byPr[r r] 1 Pr[r r] 1 Pr[Nr 0] 1 e λπr ,2(14)where Nr is the number of CN within distance r from theIN. The probability density function (pdf) of the selected CNdistance is2f (r) 2λπre λπr , r 0(15)Q(a 1)/2where !! is the double factorial and have a!! i 1(2i 1). Fig. 2 illustrates the optimal energy comparison of thesimulation result and numerical analysis (16) under differentpath-loss exponents. We can learn from the result is that withan increasing value of λ, there is a better chance to select awell positioned sensor node to improve the energy efficiencyof the proposed solution. Moreover, with a higher loss ofthe channel, the optimal solution tends to local computing,which increases the energy consumption. In the following, wefocus on a multi-node scenario and design energy efficient CNselection strategies.5 E NERGY E FFICIENT C OOPERATION N ODES ELECTION S TRATEGIES IN MWSNIn this section, we consider a more general network settingwhere multiple nodes co-exist and cooperate with each otherby acting as CN in cooperative computing.We are interested in finding a strategy that each applicationinitial node (IN) determines which node to select as the CNfor the maximal energy efficiency in the multi-node environment. It is noted that CN selections affect the overall energyconsumption, since the optimal energy cost depends upon theapplication requirement, sensor hardware configuration andchannel condition of the selected CN. In the following, wesummarize the system parameters and assumptions for themulti-node environment. The network consists of a set of nodes N {1, ., n

applications, rather than future Internet applications running on various mobile and sensor nodes. Due to the emerging development of mobile Internet, more recent works show great interests in dealing with mobile applications in the context of cloud computing. Some state-of-art literature [3], [21] in mobile cloud computing (MCC)