Ad Hoc Networks xxx (2011) xxx–xxx
Contents lists available at ScienceDirect
Ad Hoc Networks
journal homepage: www.elsevier.com/locate/adhoc
Wireless distributed computing in cognitive radio networks
Dinesh Datla ?, Haris I. Volos, S.M. Hasan, Jeffrey H. Reed, Tamal Bose
Wireless @ Virginia Tech, Blacksburg, VA 24061, United States
a r t i c l e
i n f o
a b s t r a c t
Individual cognitive radio nodes in an ad-hoc cognitive radio network (CRN) have to perform complex data processing operations for several purposes, such as situational awareness and cognitive engine (CE) decision making. In an implementation point of view, each cognitive radio (CR) may not have the computational and power resources to perform these tasks by itself. In this paper, wireless distributed computing (WDC) is presented as a technology that enables multiple resource-constrained nodes to collaborate in computing complex tasks in a distributed manner. This approach has several bene?ts over the traditional approach of local computing, such as reduced energy and power consumption, reduced burden on the resources of individual nodes, and improved robustness. However, the bene?ts are negated by the communication overhead involved in WDC. This paper demonstrates the application of WDC to CRNs with the help of an example CE processing task. In addition, the paper analyzes the impact of the wireless environment on WDC scalability in homogeneous and heterogeneous environments. The paper also proposes a workload allocation scheme that utilizes a combination of stochastic optimization and decision-tree search approaches. The results show limitations in the scalability of WDC networks, mainly due to the communication overhead involved in sharing raw data pertaining to delegated computational tasks. ? 2011 Elsevier B.V. All rights reserved.
Article history: Received 26 January 2011 Received in revised form 5 April 2011 Accepted 6 April 2011 Available online xxxx Keywords: Distributed computing Cognitive radio networks Cognitive engine Power and energy consumption Workload allocation
1. Introduction In ad-hoc cognitive radio networks (CRNs) that are comprised of ideal cognitive radios (iCR) [1], each iCR has to perform complex data processing operations for several purposes, such as situational awareness which includes identi?cation of the characteristics of signals and their sources, and cognitive engine decision making which includes learning and reasoning. The data processing operations include spectrum sensing [2]; signal detection, classi?cation [3] and feature extraction [4]; geo-location to identify location of malicious emitters; knowledge-base and case-base updates and searches; natural language processing; and computer vision. In the context of a cognitive
? Corresponding author. Tel.: +1 785 312 0818.
E-mail addresses: ddatla@vt.edu (D. Datla), hvolos@vt.edu (H.I. Volos), hasan@vt.edu (S.M. Hasan), reedjh@vt.edu (J.H. Reed), tbose@vt.edu (T. Bose). 1570-8705/$ - see front matter ? 2011 Elsevier B.V. All rights reserved. doi:10.1016/j.adhoc.2011.04.002
engine (CE), the following tasks are common: ?rst, estimating BER performance based on theoretical BER curves. CEs use those curves to evaluate hundreds of communication con?gurations and select a few to try over-the-air [5,6]. The BER curves can also be used to initialize an observations database, which stores information about the observed effectiveness of various communication methods when employed under different channel conditions, before the CE begins its ?rst operation [7]. Second, estimating con?dence intervals of observations in the database [7] requires estimation of the Beta distribution CDF which is computationally demanding. Third, CEs that employ casebase reasoning require searching and analyzing past cases [5,8]. Finally, general CE database maintenance requires a lot of computing resources. Such complex computational tasks, with high resource demands and stringent quality-of-service requirements, may cause a processing burden to resource-limited cognitive radio (CR) nodes and each CR node may not possess
Please cite this article in press as: D. Datla et al., Wireless distributed computing in cognitive radio networks, Ad Hoc Netw. (2011), doi:10.1016/j.adhoc.2011.04.002
2
D. Datla et al. / Ad Hoc Networks xxx (2011) xxx–xxx
the functionality and resources (computational and power) required to perform these tasks by itself. In battery and green solar powered radio networks, for instance, the ?nite power resources available to a radio node limit its individual computational and communication capabilities. Such power-constrained nodes may not meet the high power and energy demands set by complex computational tasks. In addition, the availability of resources varies with time and varies between radio nodes. The computational resources on each CR node may be engaged in executing tasks of varying workloads. While some CRs may be engaged in signal classi?cation, for instance, others may be involved in geo-location. These problems impose a challenge to the real-world implementation of CRNs using low-complexity and small form factor CRs. As an alternative to the traditional approach of local computing, multiple resource-constrained radio nodes can form a wireless distributed computing (WDC) network and collaborate on executing complex computational tasks in a distributed manner. This paper presents WDC as a technology that enables collaboration among CR nodes and opportunistic utilization of idle computational resources to perform complex mission-critical computational tasks with minimum power and energy consumption. In addition to CRNs, WDC can play a key role in software-de?ned tactical radio networks, wireless sensor networks (WSNs), smart phones, wireless cloud computing, wireless grids, and ubiquitous mobile computing systems. In software-de?ned radios, for instance, the computational resources dedicated for the execution of communications waveform software can be harnessed opportunistically to execute application software. WDC can potentially offer several bene?ts over local computing, including reduced energy and power consumption per node [9], reduced burden on the resources of individual nodes, enhanced computational capability of a radio network, and robustness. WDC networks can offer high performance computational services with the ability to perform complex tasks by utilizing the leveraged computational power of several radio nodes. However, the bene?ts of WDC are negated by the cost of communication between the distributed processes on collaborating radio nodes, which is a major concern in WDC network design and workload allocation. Existing distributed computing concepts proposed for wired networks [10–12] and WSNs [13–18] can be used as a basis for WDC research. However, they need to be signi?cantly adapted before being applied to WDC networks which operate in dynamic mobile wireless environments. WDC faces some unique challenges compared to traditional distributed computing. The underlying radio environment greatly in?uences and limits the ef?ciency (power and energy ef?ciency), performance (total makespan of application), and scalability of WDC networks with respect to range, node density, and computational load. Hence, WDC network design should take into consideration the interaction between the computational subsystem and the communication subsystem, as well as the interaction between the application layer and the underlying communication protocol layers. In traditional WSNs, the sensor nodes are static thereby simplifying several as-
pects of distributed computing system design. WDC, however, does not restrict itself to WSN-like scenarios and considers scenarios where the network comprises of heterogeneous mobile radio nodes with limited a priori knowledge of the wireless environment. This paper introduces the notion of WDC in CRNs with the help of a simple CE processing example. The paper also analyzes the impact of wireless environments on WDC network scalability and ef?ciency in terms of power and energy ef?ciency. WDC ef?ciency and performance is directly dependent on the allocation scheme employed to share the computational workload among the collaborating nodes. WDC ef?ciency is analyzed for two contrasting scenarios: ?rst, when simple uniform workload allocation is employed in homogeneous environments and, second, when adaptive workload allocation is employed in heterogeneous environments. In order to analyze WDC ef?ciency in heterogeneous environments, this paper proposes a stochastic decision-tree based workload allocation scheme for heterogeneous WDC networks. The system model for WDC performance analysis is presented in Section 2. WDC performance analysis, for both homogeneous and heterogeneous environments, is presented in Sections 3 and 4. The proposed workload allocation scheme is presented in Section 4. The application of WDC to CRNs is demonstrated with the help of a simple CE processing example in Section 5. The paper ends with concluding remarks in Section 6. 2. WDC Network System Model The WDC environment primarily consists of Nnodes wirelessly connected computational radio nodes, where each WDC node comprises of communication, computational, and power subsystems. The communication subsystem connects the computational subsystems on various collaborating nodes through wireless links and serves the distributed computing process in disseminating the computational workload, as well as enabling message passing between the computational processes on different nodes. WDC workload allocation can be viewed as a problem of mapping a given task graph to the communication graph such that the objective is optimized [19,20], as shown in Fig. 1. This section presents macroscopic power and energy consumption models of individual subsystems and the WDC network, which are derived from low level power
b12 F2 b24 F4 b46
F1
b13 F3 N2 b35 F5 b56 l12 N1 l14 l13 N4 l23 N3 l34
b25
F6 Task graph Communication graph
Fig. 1. Allocation of function blocks in task graph to nodes in communication graph.
Please cite this article in press as: D. Datla et al., Wireless distributed computing in cognitive radio networks, Ad Hoc Netw. (2011), doi:10.1016/j.adhoc.2011.04.002
D. Datla et al. / Ad Hoc Networks xxx (2011) xxx–xxx
3
consumption models [9,21]. WDC is analyzed for two scenarios which are described in this section. Task graph: The WDC application’s computational task is segmented into NFB software components, called function blocks (FBs), which are represented in the form of a directional acyclic task graph, as shown in Fig. 1. Vertex Fi 2 F in the task graph represents an abstraction of the ith FB, which can include resource requirements and computational cost. Interaction between Fi and Fk is represented by edge metric bik which denotes the amount of data passing (expressed in bits) that occurs between FBs while the WDC application is being executed and, possibly, other metrics such as tolerable latency. Data passing between FBs allocated to different WDC nodes occurs over the wireless link and occurs internally otherwise. In the case of a homogeneous computational task with independent FBs, it is assumed that a computational task constitutes NFB discrete FBs which do not communicate with each other. WDC network con?guration: A communication graph represents the set of all WDC nodes (graph vertices) denoted by Nj 2 N. The wireless link (graph edge) between Nj and Nl is denoted by Ljl 2 L. The nodes and links are abstracted by their capacity, resource availability and link quality. P jcpt and Ejcpt denote the power and energy available for computational purposes in Nj and are related to the total remaining power P jT and the channel conditions, as discussed in Sections 3.1 and 4.1. The WDC network forms a single-hop master-slave con?guration, where the WDC application service request with a total computational workload of NFB originates in the master node (N1) and the slave nodes (Nj where j – 1) collaborate in processing the WDC application. The master node internally processes N 1 FBs and delegates the remaining N 1 FBs to the slave FB1 FB2 nodes, where N 1 ? N FB ? N 1 . Upon processing the data, FB2 FB1 the slave nodes return processed data to the master node. Transmission scheme and scenarios: The WDC nodes communicate with each other via broadcast using an ideal coordinated MAC, such as TDMA with perfect synchronization. Two contrasting scenarios, namely scenarios 1 and 2, are analyzed in this paper. Scenario 1 which represents a simple homogeneous environment provides useful insight into WDC performance and scenario 2 is set in a generic heterogeneous environment that represents a practical WDC network. In scenario 1, the workload comprising of independent identical FBs is uniformly allocated to all WDC nodes, regardless of power constraints in each node, in a homogeneous operating environment (all nodes possess identical communication and computational subsystems) with identical link conditions between nodes characterized by large scale fading. In scenario 2, the computational workload is adaptively allocated to WDC nodes in a heterogeneous environment characterized by large and small scale fading. A ?xed BPSK transmission scheme is adopted for scenario 1, while scenario 2 employs a simple adaptive transmission scheme with power control and ON/OFF transmission, where data is transmitted only when the channel conditions are favorable for BPSK transmission. BPSK has been chosen for the simulations of scenario 1 in this paper in order to demonstrate the power bene?ts of
WDC. BPSK is the most robust and power-ef?cient modulation scheme among the PSK modulation schemes. Hence, a WDC system that employs BPSK would spend less power for communication purposes, thereby minimizing the communication overhead which impacts WDC ef?ciency. For scenario 2, the paper derives a statistical model for the transmitter power consumption when the communication subsystem operates at minimum power without any rate constraints. In such a scenario, BPSK, which is power optimal when rate is of no concern, becomes an immediate choice for the analysis. Computational power/energy consumption: In a heterogeneous environment, the energy consumption per FB and the power consumption while processing Fi on Nj is given by,
Eij ? Pij ? T ij ; cp FB FB where
T ij FB
?1? ?
3 aij fcp
Pij ?fcp ? cp
?
2 bij fcp
? cij f cp ? dij :
?2?
is the processing time per FB and 0 < fcp 6 fcpmax. Eq. (1) expresses the non-linear polynomial relationship between computational power consumption and processor’s clock frequency, denoted by P ij and fcp [9]. The coef?cients cp aij, bij, cij, and dij are all positive and empirically related to the processor model and the computational task being executed. In scenario 1, where each FB consumes Pcp watts of power, Ncycles processor clock cycles, TFB secs of processing time (depending on fcp), and EFB joules of energy, the total energy consumption is given by Ecp = EFB NFB = Pcp TFB NFB. Communication power/energy consumption: When Nj is transmitting to Nl, the transmitter and receiver power consumptions in Nj and Nl are denoted by Pjl and Plj respectx rx tively. The transmitter and receiver power/energy consumption for a given radio system can be expressed as a function of the communication range D, bandwidth B and the minimum required received signal-to-noise ratio cmin, as given by,
Ptx ? ?G1 cmin Dn B? ? G2 ; ? ? Etx ? Et ? T tx Et ? G1 cmin Dn B ; 1 2 Erx ? Er ? T rx Er ; 1 2
?3? ?4? ?5?
where G1 ; G2 ; Et ; Et ; Er and Er are constants that depend on 1 2 1 2 the transceiver characteristics and channel conditions, such as path loss and shadowing [9,21], and n denotes the path loss exponent. The receiver power consumption is assumed ?xed in this paper, although it can vary with the receiver parameters, such as decoding complexity, and channel conditions [22]. Transmission time is given by Ttx = NB/ Rtxout, where Rtxout denotes the radio transmission rate and NB is the total number of bits transmitted. It is assumed that, the reception time Trx = Ttx. The time it takes to successfully convey one bit of information to the receiver, denoted by Tbit, includes the delays imposed by the MAC and channel outages. In scenario 2, Tbit can be modeled as a random variable which varies according to the modulation scheme and channel outage probability. However, Tbit is assumed constant in this paper, which is a reasonable assumption considering the fact that only BPSK transmission is used with no rate control. Data
Please cite this article in press as: D. Datla et al., Wireless distributed computing in cognitive radio networks, Ad Hoc Netw. (2011), doi:10.1016/j.adhoc.2011.04.002
4
D. Datla et al. / Ad Hoc Networks xxx (2011) xxx–xxx
passing cost within a WDC node is assumed as zero. From a dynamic spectrum access radio perspective, it is worthwhile to consider the relationship between WDC power consumption and the spectrum band chosen for communication between the WDC nodes. The transmitter and receiver power consumption depends on the frequency of radio operation, as well as the operational bandwidth (as evident from Eq. (7) in [9]). Speci?cally, transmission at lower frequencies, say in the TV bands, would require lesser transmit power, while transmission at higher frequencies suffers from increased attenuation. In scenario 2, where the transmission scheme adapts according to the stochastic variations in link quality, the mean communication energy consumption per bit associated with link Ljl is given by Ejl ? Ejl ? Elj , where cmb txb rxb Ejl ? Et ? Pjl ? G2 ? T bit . Elj ? Er ? T bit , and P jl denotes tx tx 2 2 txb rxb mean transmitter power consumption. WDC network power/energy consumption: When performing a computational task in a distributed manner, each node in the WDC network consumes power for communication and computational processes. Instantaneous network power consumption is a time-varying parameter which depends on the communication traf?c at the particular instant. Since the network power consumption is important to assess how the power demand can be met with the available power supply, the peak network power consumption is considered in this paper. The WDC network power/energy consumption models are de?ned separately for scenarios 1 and 2, with the models for scenario 2 de?ned in Section 4. In scenario 1, assuming that the communication and computational processes in each node occur concurrently in order to comply with latency and buffering (buffering of large amount of data that ?ows between the computational and communication subsystems) constraints, the peak WDC network power consumption and master node’s total energy consumption are given by
In the latency reduction mode, the individual nodes operate at maximum rate (no dynamic voltage/frequency scaling) and the network achieves a Nnodes fold increase in computation latency. The power reduction mode is not considered in scenario 2 since it involves elaborate stochastic modeling of the relationship between computational and communication latency, which is outside the scope of this paper. WDC power and energy savings metrics: Under certain conditions, power and energy consumption savings can be achieved by executing a computation task in a distributed manner in a WDC network compared to local onboard processing of the same task. The master node power savings, network power savings and master node energy savings in a homogeneous environment are de?ned as
Pm v ? Ps ? P1 ; sa node Pnw ? Ps ? Pnw ; sav Em v ? Es ? E1 ; sa node
?9? ?10? ?11?
Pnw ? Nnodes ? Pnode ; where P node ? P cp ?fcpd ? ? P tx 6 P T : E1 node ? Pcp ?fcpd ? T FBd NFB1 ? Ett 1 ? Ecmb Nbits NFB2 6 ET ;
?6? ?7? ?8?
where TFBd = Ncycles/fcpd and Ett ? Et ? Er . The peak power 1 1 1 consumption and clock frequency in each WDC node are denoted by Pnode and fcpd respectively. Eq. (7) re?ects the fact that Ptx = max{Ptx, Prx}. N1 (master node with j = 1) consumes energy in order to process NFB1 FBs and transmit/receive data bits corresponding to NFB2 FBs, where the number of bits transmitted or received per FB is denoted by Nbits. The WDC network operates either in the power reduction mode or the computation latency reduction mode. The power reduction mode is appropriate when the latency requirement Ncycles/fcp is met by a single computing node, however its power consumption exceeds the power constraints. Assuming uniform workload allocation, each node processes in parallel at a lower clock rate of fcpd = fcp/Nnodes. It is also assumed that the communication latency is negligible compared to the computation latency.
where the total power and energy consumption (constrained by the node’s available power and energy supply) when a computation task is executed locally on a single node at a clocking rate of fcps, is given by Ps = Pcp(fcps) and Es = Pcp(fcps) TFBs NFB. Negative power savings (indication in favor of local processing) are achieved when operated in the latency reduction mode, say when fcps = fcpd. Es is the energy consumed in order to process NFB FBs on a single node which is constrained by total energy supply ET, and the time taken to process one FB in a node at a clock rate of fcps is given by TFBs = Ncycles/fcps. It is evident that the computational power savings achieved by WDC is negated by the communication overhead depending on the channel conditions, the underlying radio platform and the network topology. The savings are expressed as a percentage of the local processing consumption. Simulation parameters: Three processor power models, namely models 1, 2 and 3, are used in this paper. Processor model 1 refers to a StrongArm SA-1100 processor that performs 1024-point FFT with coef?cients a = 17.745 nW/ Hz3, b = 3.1472 lW/Hz2, c = 203.9 lW/Hz, d = 1.36 mW which are derived from experimental data [23–25]. Processor models 2 and 3 are hypothetical and are derived as follows. For analytical purposes, the cubic coef?cient a is dropped from consideration due to its relatively insigni?cant value. In order to achieve positive network power savings, expression on the right of Eq. (10) is evaluated the 2 2 as: b fcps ? N nodes fcpd ? c ?fcps ? N nodes f cpd ? > N nodes P tx . When operating in the power reduction mode, where fcpd = fcps/Nnodes, the condition for positive network savings is expressed as
b>
0 N2 nodes P cm ; 2 ?Nnodes ? 1? a2 fcpmax
?12?
where fcps = a fcpmax. Computation platforms that satisfy this condition can achieve power bene?ts from WDC. b is representative of the non-linearity in the processor power–frequency characteristics. Using Eq. (12), the b coef?cient of processor model 2 is determined for fcpmax = 206 MHz, Nnodes = 5, D = 10 m. The b coef?cient for
Please cite this article in press as: D. Datla et al., Wireless distributed computing in cognitive radio networks, Ad Hoc Netw. (2011), doi:10.1016/j.adhoc.2011.04.002
D. Datla et al. / Ad Hoc Networks xxx (2011) xxx–xxx
5
processor model 3 is determined as an arbitrary value that lies between the b coef?cient values of processor models 1 and 2. Processor models 2 and 3 have the same a, c and d coef?cients as processor model 1 but different values for b, where b = 48.778 lW/Hz2, 30 lW/Hz2 respectively. Effectively, we are employing processor models with varying degrees of non-linearity in their power-clock rate characteristics, which would help us in our analytical study. Using the radio hardware power consumption parameters and channel parameters de?ned in [9,23–27], G1 B = 6.3821 ? 10?11 W/m3 and G2 = 0.33 W. The following assumptions are made: path loss exponent n = 3, B = 30 khz, cmin = 10 dB (uncoded BPSK modulation for a target bit error rate of 10?3 which is appropriate for data communication), EFB = 0.5 J (default value), Tbit = 1/(32 kbps), and Nbits = 512 data points ? 32 bits per data point. 3. Scenario 1: WDC performance in homogeneous environments This section presents limitations in the availability of resources for computational purposes and the power/energy savings achieved by WDC over local computation in scenario 1. 3.1. Limits on resource availability A fundamental limitation of the computational capability of a WDC node arises when the computational process are executed concurrent with the transmission process in the node under power (or energy) supply constraint. Eq. (7) indicates the non-linear tradeoff between computational capability (expressed in terms of clock frequency) and communication range, where the maximum possible power consumption by computation processes in a node is given by Pcp (fcp) 6 Pcpt, where Pcpt = PT ? (G1 SNRmin Dn B) ? G2. The network’s computational capability degrades in harsh channel conditions. When Pcpt falls below the power required to meet a computation latency constraint Ncycles/fcp, the node can share its computational workload with other nodes in the WDC network and the network can operate in the power reduction mode. The minimum number of nodes required to meet the power and latency constraints can be derived from Eqs. (1) and (7) as
where EFB is not affected whether local processing or distributed processing is performed. 3.2.1. Power saving bene?ts and limitations The network power savings (Eq. (10)) is plotted for different network sizes in Fig. 2a. The savings are not plotted for processor model 1 since it exhibits a high negative power savings. As the network size increase, the reduction in the computational power consumption (due to lowering of the clock rate per node) is negated by an increase in the total network communication power consumption. This explains the trend observed in Fig. 2a. The network power savings increases until a certain value of Nnodes and thereafter decreases. No power savings is achieved from WDC when the communication overhead dominates over the computation power consumption, as in the case of the WDC network with 6 nodes where each node operates with processor model 2. This indicates that high power non-linear computation tasks (processor model 2) would bene?t from WDC while low power tasks (processor
25
Processor Model 2 Processor Model 3
Network power saving (%)
20
15
10
5
0
?5 2 2.5 3 3.5 4 4.5
nodes
5
5.5
6
Number of nodes N
(a)
25
Network power saving (%)
20
Processor Model 2, N Processor Model 3, N =2 =2 =3
15
nodes nodes nodes
b
fcp Nnodes
2
10
Processor Model 2, N
) Nnodes
fcp ? ?PT ? Ptx ? d? 6 0 Nnodes 2 b f cp P p?????????????????????????????????????????????? c2 ? 4 b?PT ? Ptx ? d? ? c ?c
Processor Model 3, Nnodes = 3
5
?13?
0
where PT > Ptx + d. The linear relationship between Nnodes and fcp, as well as Nnodes and D is evident from Eq. (13). 3.2. Power and energy savings in WDC networks The WDC network is operated in the power reduction mode for power savings calculations. It is assumed to operate in the latency mode for energy savings calculations,
?5 50 100 150 200 250 300 350 400 450 500
Communication range (meters)
(b)
Fig. 2. WDC network power savings for the different processor models versus: (a) network size with a range of D = 200 m, and (b) communication range with Nnodes = 2, 3.
Please cite this article in press as: D. Datla et al., Wireless distributed computing in cognitive radio networks, Ad Hoc Netw. (2011), doi:10.1016/j.adhoc.2011.04.002
6
D. Datla et al. / Ad Hoc Networks xxx (2011) xxx–xxx
models 1 and 3) will have to bear the overhead power consumption for communication purposes when executed in a distributed manner. The network power savings scales in a non-linear manner with communication range as shown in Fig. 2b. The savings is plotted for Nnodes = 2 (which represents a limiting scenario) and 3. The drop in power savings with D is attributed to the increase in communication overhead. Processor models 1 and 3 yield negative power savings since their power-clock rate characteristics are the least non-linear. 3.2.2. Energy saving bene?ts and limitations The master node’s energy savings varies with D and Nnodes as shown in Fig. 3a. The savings improve with an increase in the number of collaborative nodes due to decreased computational workload at the master node. However, for large Nnodes, the energy savings does not increase signi?cantly due to the consequent increase in the communication overhead imposed by transmission/
40 35
reception of data to/from slave nodes. The small variation of energy savings with distance is attributed to the low path loss. The decrease of energy savings with distance is attributed to the increasing transmitter power consumption at the master node. Fig. 3b shows the scalability of energy savings with computational task complexity (expressed in terms of EFB). For all computational workloads, a computational task with a high energy consumption of EFB > 0.2 J bene?ts from WDC under the given channel conditions. Thus, the breakpoint in favor of WDC occurs at EFB = 0.2 J. Furthermore, energy savings do not scale linearly with the workload. This is because, under a uniform load balancing scheme, higher workloads result in delegation of an increasing percentage of the total workload to the slave nodes. This, in turn, results in higher savings in computational energy consumption, but at the cost of an increasing communication overhead for the master node. It is also observed that the savings do not scale linearly with the energy complexity of the task.
Energy saving per node (%)
4. Scenario 2: WDC performance in heterogeneous environments This section presents statistical analysis of the power resources that are available for computational purposes, particularly when the computational and communication processes share from a common power source. In addition, for the purpose of energy savings analysis, a workload allocation algorithm for WDC networks that uses a combination of stochastic optimization and decision-tree search approaches is presented. This algorithm enables analysis of WDC performance in stochastic heterogeneous environments. 4.1. Limits on resource availability Unlike the case of deterministic homogeneous channels, the power available for computational purposes depends on the communication power consumption, which in turn is a random variable in heterogeneous stochastic channels. The derivations of the mean transmit power consumption and the density function of Pcpt are presented next. 4.1.1. Derivation of mean transmit power consumption The transmitter power consumption when adaptive transmission is employed is given by Ptx(t) = (G1 cmin Dn B a(t)) + G2, where a(t) is the power control factor which is varied according to the instantaneous channel conditions. The instantaneous received SNR is given by c?t? ? g?t? c a?t? [28], where the mean received SNR is given by c ? N0S B and S is the mean signal power. The channel gain, denoted by g(t), is a chi-square random variable with 2 degrees of freedom, which has an exponential dis2 tribution fg ?g? ? ?1=2r2 ? e?g=2r H?g?, where r denotes the variance of the distribution, g P 0 and H(g) is the Heaviside step function. In the case of a power optimal adaptive communication scheme that operates under no rate
30 25 20 15 10 5 0
D = 250 m D = 450 m D = 650 m
0
10
20
30
40
nodes
50
60
Number of nodes N
(a)
50 45
Energy saving per node (%)
40 35 30 25 20 15 10 5 0 0.2 0.4 0.6 0.8 1 1.2 1.4
FB
NFB = 10 NFB = 100 NFB = 1000
1.6
1.8
2
Energy consumption per FB E
(joules)
(b)
Fig. 3. Scalability of master node’s energy savings with: (a) network size for various communication ranges assuming NFB = 10 and EFB = 0.35 J, and (b) computational energy consumption per FB (EFB) for different computational workloads (NFB) assuming Nnodes = 2 and D = 200 m.
Please cite this article in press as: D. Datla et al., Wireless distributed computing in cognitive radio networks, Ad Hoc Netw. (2011), doi:10.1016/j.adhoc.2011.04.002
D. Datla et al. / Ad Hoc Networks xxx (2011) xxx–xxx
7
constraints, the transmit power level is varied such that the following conditions are met:
where k, gxy, rxy > 0. 4.1.2. Derivation of distribution function of power available for computational purposes When both the communication and computational processes operate concurrently in a radio node, Pcpt can be de?ned as
min?c?t? ? cmin ? ) min?g?t? c a?t? ? cmin ?;
a?t? a?t?
S:T c?t? P cmin & ) a?t? ? 1=g?t?; c?t? P cmin 0; '
c?t? < cmin
P cpt ?g? ?
&
In addition, the transmitter operates using BPSK which is the lowest and most power-ef?cient modulation scheme. The resulting transmitter power consumption can be expressed as
' PT ? ?C 1 =g? ? C 2 ; g P C 3 ; PT ? C 2 ; g < C 3
?17?
where Pcpt and g are random variables and g > 0, " t. The following preliminary observations can be made:
(
Pxy ?g xy ? ? tx
?C 1 =g xy ? ? C 2 ; g xy P C 3 C 2 ; g xy < C 3
)
( F Pcpt ?pcpt ? ?
;
?14?
1; 0;
pcpt > PT ? C 2 pcpt < PT ? C 1 =C 3 ? C 2
) : ?18?
where P xy and gxy are random variables, gxy > 0, " t, and the tx remaining variables are constants de?ned as C 1 ? G1 cmin Dn B; C 2 ? G2 and C3 = gmin, and gmin is the minixy mum channel gain required for transmission which is related to cmin. When cmin ? c, then gmin = 1. For the sake of the derivation, subscripts and superscripts that indicate the link xy are not used on the variables. Then, the mean transmit power consumption can be derived as
Since Pcpt(g) is constant in the interval ?0; C 3 ?; F Pcpt ?pcpt ? is discontinuous at PT ? C2, i.e. Pcpt(g) = PT ? C2 for 0 6 g < C3, and the discontinuity is equal to
PfPcpt ? PT ? C 2 g ? Pf0 6 g < C 3 g ? lim F g ?C 3 ? ? ? lim F g ???
0<!1 0<!1
?19?
? F g ?C 3 ? ? 0 ? F g ?C 3 ?:
At other points, namely in the interval P T ? pcpt < P T ? C 2 ,
C1 C3
?20?
? C2 6
Ptx ? EfPtx g ?
Z
Ptx ?g? ? fg ?g? ? dg
Z C3 ?b C 3 ? fg ?g? ? dg ? lim b!0 0 Z 1 C1 ? C 2 ? fg ?g? ? dg: ? g C3
g
? ? F Pcpt ?pcpt ? ? P Pcpt 6 pcpt (
?15?
While computing the mean which involves an integral of Ptx(g), an in?nitesimally small interval b that converges from the left is used since the interval g < C3 is open in the lower limit. Given that g > 0, " t, the ?rst integral is evaluated as
? PfPT ? ?C 1 =g? ? C 2 6 pcpt g ) C1 ?P g6 PT ? C 2 ? pcpt ! C1 : ? Fg PT ? C 2 ? pcpt
In summary,
C 3 lim
b!0
Z
0
C 3 ?b
fg ?g? ? dg ? C 3 ? lim F g ?C 3 ? b?:
b!0
The other integrals are evaluated ass
Z
1
C3
C 2 f g ?g? dg ? C 2
Z
1
fg ?g? dg ?
Z
0
1
fg ?g? dg
!
0
? C 2 ?1 ? F g ?C 3 ?? Z
1
8 > 1; > > > > F g ?C 3 ?; > > > > < C F Pcpt ?pcpt ? ? F g PT ?C 21?pcpt ; > > > >; > > > > > : 0;
.
pcpt > PT ? C 2 pcpt ? PT ? C 2 PT ? C1 ? C 2 C3 6 pcpt < PT ? C 2 pcpt < PT ? C1 ? C 2 C3
9 > > > > > > > > > = > > > > > > > > > ;
?21?
C1
C3
R 1 ?t where the exponential integral E1 ?z? ? z e t dt; jarg:zj < p for z = x + i y. The condition jarg.zj < p (or arctan(y/x) < p) is met when the imaginary part of Z is zero. Thus,
? C 2 e?k ; k ? C 3 =2r2 ; g; r P 0: Z 1 ?g=2r2 fg ?g? C1 e dg ? dg 2 g 2r C 3 g Z 1 ?t C1 e dt ? 2 2r k t C1 E1 ?k?; k > 0 ? 2r2
4.2. Workload allocation problem formulation The allocation of Fi to Nj, denoted by xij, is optimized with respect to two objectives, namely, minimization of WDC network energy consumption Enw and minimization of master node’s energy consumption E1 . Note that, the node latter objective, particularly, maximizes the master node’s energy savings.
Obj 1 : min: Enw ?
X
i2F
Pxy ? C 3 ?1 ? e?k ? ? C 2 e?k ? tx
C1 E1 ?k?; 2r2 ?16?
?
X
j2N
xij Eij FB
?
XX
k2F l2N
! Ejl cmb bik xij xkl ; ?22?
C1 k ? E1 ?k? ? ?C 2 ? C 3 ? e?k ? C 3 ; C3
Please cite this article in press as: D. Datla et al., Wireless distributed computing in cognitive radio networks, Ad Hoc Netw. (2011), doi:10.1016/j.adhoc.2011.04.002
8
D. Datla et al. / Ad Hoc Networks xxx (2011) xxx–xxx
Obj 2 : min: E1 ? node
X
i2F;j?1
xij Eij ? FB
XX
k2F l2N
! Ejl bik xij xkl txb
17: 18: 19:
d = Cmin(q ? 1) ? Cmin(q) {Improvement in cost function} N L ? f/g i?1 Traceback atleast 2 levels and update costs until conditions are met (see Pseudo code 3) Increment L if i = 1 and N L ? f/g i Xq+1,i = Xq,i;"i 2 M q=q+1 end if end while
?
X X
i2F k2F;l?1
Elj bik xkl ; rxb ?23?
S:T: xij 2 f0; 1g; xij ? 1;
X
8j2N
xij 6 1; 8i 2 F;
20: 21: 22: 23: 24:
j ? 1; 8i 2 f1; NFB g;
xij ? Pij 6 Pjcpt ; cp
8j 2 N; 8i 2 F:
The constant terms, namely Et and Er , are re?ected in the 1 1 available power and energy supply in the node. The above formulation can be solved by enumerating the various permutations involving FBs and radio nodes. Such an approach lends itself naturally to a tree structure, which can be solved using tree search algorithms [20]. 4.3. Workload allocation algorithm description Algorithm 1. Initialization. 1: 2: 3: 4: 5:
NL ? NG ; i ? 1 i i
Algorithm 3. Traversing up tree one level. 1: 2: 3: 4: 5: while (i > 1) AND N L ? f/g do i i=i?1 C j ? C j ? P ij ; j ? X q;i cpp cpp cp C q ? C q ? BM ij ; j ? X q;i ; q ? j for obj1 and q = 1 T T for obj2 end while
Compute branch metrics Bij ; j 2 NL ; i ? 1 i Initialize L = 0 Set Cmin(q) = Eap;q = 0 q=1
Algorithm 4. Traversing down tree one level. 1: 2: 3: 4: 5:
N L ? N L ? fjg i i C j ? C j ? P ij cpp cpp cp
Algorithm 2. Decision-tree search algorithm. 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: Initialize algorithm (see Pseudo code 1) while (L < 2) OR (d < Rd) do if (visiting vertex for the ?rst time: N L ? f/g) then i Compute branch metric: BMij ; 8j 2 N L ; N L ? N G ; i – 1 (Eqs. (24) and (25)) i i i end if Choose branch with minimum branch n o metric, i.e. j : BMij 6 BMik ; j; k 2 N L ; j – k i Compute objective Cnet with BMij (see Eqs. (26) and (27)) if (constraints are satis?ed (Eq. (28))) AND(Cnet < Cmin (q ? 1)) then Increment L if i = 1 and N L ? f/g i Update cost variables and propagate one level down (see Pseudo code 4) else Traceback one level and update costs until conditions are met (see Pseudo code 3) Increment L if i = 1 and N L ? f/g i end if if (i = Nmod + 1) then P C min ?q? ? j C j ; j 2 N for obj.1 and j = 1 for T obj.2. {End of iteration}
C T ? C q ? BM ij ; q ? j T xij = 1,Xq,i = j i=i+1
for obj1 and q = 1 for obj2
WDC slave nodes that cannot process the least powerintensive FBs due to resource constraints are eliminated from further consideration. After applying elimination rules, the remaining subset of candidate WDC nodes for Fi is denoted by N G . When the tree is being traversed, the i subset of candidate nodes that have not been explored yet for allocation of Fi is denoted by N L . The algorithm is i initialized by making an allocation for the ?rst FB, as shown in Pseudo code 1. Cmin(q) denotes the minimum cost at the end of qth iteration of the algorithm. L counts the number of times the last remaining branch of the tree’s ?rst level has been traversed. The algorithm functions iteratively until L = 2, each time propagating the branch downwards and upwards, or if the minimum cost Cmin(q) has not improved by more than Rd from the previous iteration. BMij denotes the metric of the branch associated with the allocation Fi to Nj. The branch metrics quantify the impact of allocating Fi to Nj on the objective function. Eap represents the cost constraints (master node’s energy consumption or that of entire network) placed by the WDC application. Xq,i stores the index of the WDC node to which Fi has been allocated in the qth iteration. Variables C jcpp and C jT are the computational power and total energy consumptions of Nj evaluated for a partial allocation scheme. They are
Please cite this article in press as: D. Datla et al., Wireless distributed computing in cognitive radio networks, Ad Hoc Netw. (2011), doi:10.1016/j.adhoc.2011.04.002
D. Datla et al. / Ad Hoc Networks xxx (2011) xxx–xxx
9
initialized to zero at the beginning of the algorithm. A partial allocation scheme at level K of the tree refers to the allocation mapping: Fi ? Nj, where j = Xq,i and i = 1 to K. In other words, C jcpp and C jT store the total of branch metrics associated with the path traversed. The algorithm is presented in Pseudo code 2. Branch metrics are computed every time a tree node is traversed for the ?rst time. The branch metrics for the two objectives on tree level 1 representing F1 are computed as: BMij ? Eij ; 8j 2 N L ; i ? 1. For all other levels of tree, the branch i FB metrics for the two objectives are computed as
Obj 1 : BM ij ? Eij ? FB 8 > < > :
i?1 X bki ? Elj ; cmb k?1 i?1 P k?1
8j 2 N L ; i
?24? 9 > = > ;
Obj 2 :BM ij ?
Eij ? FB
bki ? Ejl ; rxb
j?1
;
bki ? E1j ; k : X q;k ? 1; txb
8j 2 NL ? f1g i
?25?
where l = Xq,k,i 2 F ? {1, NFB}. The branch metrics are compared with respect to their mean values, where the mean branch metric is a function of Pxy . The branch with the mintx imum metric is chosen and the objective is evaluated for the partial allocations, as given by
Obj 1 : C net ?
X
j2N
! C jT ? BM ij ; ?26? ?27?
Obj 2 : C net ? C 1 ? BM ij : T
The objective is checked against the following power constraint which are applied to the workload allocation: C jcpp ? P ij 6 Pjcpt . In the case of a stochastic environment, cp the constraint has to re?ect the stochastic nature of Pjcpt . Let P cp denote the application’s tolerance limit on the out probability of non-availability of computational resources in Nj. If rjcpt is the maximum power available for computational purposes that meets outage ? constraint P cp , then n o out ? P P jcpt < r jcpt ? P cp ) r jcpt ? F ?1 P cp . Thus, the new conout Pcpt out straint check is given by
stores the number of successful and failed packets associated to a communication method and channel conditions pair. The CE uses the number of successful and failed packets to estimate a con?dence interval for the packet success rate (PSR) of the associated communication method for a particular channel condition. For every packet received, the number of successful and failed packets for the particular communication method used under particular channel conditions is updated followed by update of the con?dence intervals. The Gittins index is computed based on the con?dence intervals and is used to optimally balance exploration and exploration by selecting the method with the highest index [7,29]. Each entry in the database, which is indexed by the associated communication method and channel condition (quanti?ed by metrics such as SNR), consists of the number of successful packets, the number of unsuccessful packets, con?dence interval of the PSR, and the Gittins index. An overview of the database update process is as follows. Packet observation information is collected, where each observation consists of the channel condition, the communication method used, and an indication of successful packet reception. For each packet, the database entry for the corresponding channel condition and communication method is updated, and the knowledge is propagated throughout the relevant portions of the database. For example, if a communication method A is found to drop a packet at 10 dB SNR, it is also expected to drop a packet in any SNR below 10 dB. Therefore, all the entries at 10 dB and below for communication method A are marked with an unsuccessful packet. In addition, if 32 QAM is observed to deliver a successful packet at a certain SNR, 16 QAM and 4 QAM are also expected to deliver a successful packet at that SNR, and for this reason the corresponding entries in the database are marketed with a successful packet too. Once the entire set of packet observations have been taken into consideration, the con?dence intervals and Gittins indices are calculated. Fig. 4 illustrates the different computational tasks associated with the CE operation. All the
? ? C jcpp ? Pij 6 rjcpt ; where r jcpt ? F ?1 Pcp : cp P cpt out
?28?
Initialize Observations Database using BER curves
If the constraints are satis?ed, the algorithm proceeds down the tree to the next level. The costs are updated for each node as shown in Pseudo code 4 and the procedure is repeated. If the constraints are not satis?ed, the algorithm has to avoid the current tree node and look for another one. In that case, the algorithm traverses back one level up the tree, as shown in Pseudo code 3 and searches over a different part of the tree which has not been explored earlier. An iteration is said to have been completed when the algorithm reaches a leaf.
F1
F1
Operate and Collect Packet Statistics
F2 b23 F2
b12 b2M b24 FM bM,M+1
Propagate Packet Results Across the Database
F3 F3 - F M b3,M+1
F4 b4,M+1 FM+1
5. Example cognitive engine computational task This section demonstrates the application of WDC to CE processing with the help of an example operation performed by the CE proposed in [7]. The CE under consideration is based on an observations database that initially
Estimate Confidence Intervals and the Gittins Index
FM+1
Cognitive Engine Computational Task graph
Fig. 4. Example CE computational tasks represented in the form of a ?owdiagram and corresponding task graph.
Please cite this article in press as: D. Datla et al., Wireless distributed computing in cognitive radio networks, Ad Hoc Netw. (2011), doi:10.1016/j.adhoc.2011.04.002
10
D. Datla et al. / Ad Hoc Networks xxx (2011) xxx–xxx
Maximized master node energy savings (%)
tasks can be segmented, processed by individual nodes, and aggregated back together. 1. Task 1 (F1) : Initialize the database by assigning uniform values for packet success and failures. Based on theoretical BER curves, populate the database (i.e. update the packet success and failures) and compute the con?dence intervals and Gittins indices. 2. Task 2 (F2) : Try a particular communication method over-the-air and collect packet observation information. The packet information can either be collected by one node or by several nodes. In the task graph under consideration, however, it is assumed that the packet information is collected by only one instance of the ‘‘Operate and Collect Packet Statistics’’ operation, i.e. only one node collects the information. 3. Task 3 (F3–FM) : Use the packet information to update entries in the database. The collected packet information set can be fragmented into smaller mutually exclusive subsets of data, where a WDC node can process one or more subsets. Function blocks F3–FM represent different parts of the fragmented data. Each fragment can be used to update a different instance of the observations database, where each collaborating node maintains an instance of the entire database. For instance, if node 2 is allocated F3 and F4, node 2 uses the corresponding data to update its instance of the database. 4. Task 4 (FM+1): Assimilate the different instances of the database and compute the con?dence intervals and Gittins index based on the new database. The ‘‘Operate and Collect Packet Statistics’’ block is not a treated as an independent computational task, although it has been explicitly shown as a separate function block in the task graph. This block denotes the operation time between database updates where the current information is used for operation. 5.1. Simulation results The proposed workload allocation algorithm has been applied for the CE task graph. In order to study the impact of various parameters in the network setup on the WDC scalability, the parameter under consideration is varied while the rest are ?xed. The master node’s maximized energy savings is plotted for different network sizes and different computational workloads in Fig. 5. The workload is expressed in terms of the number of sets of packet information, represented by M ? 2. The power consumption for all the FBs is 2.27 W. F1 and FM+1 take 0.1 s each to execute while the remaining FBs take 0.5 s. Distance between master node and slave nodes is 50 m and all nodes have 10 W power supply. Time taken to transmit/receive a bit is 31 ls assuming a transmission rate of 32 kbps. Receiver power consumption is 0.5 W and the variance r = 2. Assuming an outage probability Pcp ? 0:1, using Eq. (21), out =2r2 rjcpt is computed as P T ? C 2 ? logC 11?Pcp . Fig. 5 indicates ? out ? the minimum number of nodes required for minimizing the master node’s energy consumption for different computational workloads. The curves ?atten beyond a particu-
100 90 80 70 60 50 40 30 20 10 0 1 2 3 4 5 6 7 8 9 10
N N N N
FB FB FB FB
= 12 = 17 = 19 = 25
Number of nodes
Fig. 5. Maximized master node energy savings for various network sizes and computational workloads.
lar network size Nmin since only a subset of the nodes are allocated FBs for the workloads under consideration. The nodes that are allocated the FBs have suf?cient resources to process the FBs and communicate with the master node. Hence, Nmin nodes are suf?cient to process all the FBs while the remaining nodes are not allocated FBs. In order to analyze the impact of distance d1j between the master and slave nodes on the master node’s energy savings, d1j is generated as a random variable that is uniformly distributed in the interval [10, Dmax]. The distance, in turn, impacts r jcpt , where nodes located closer to the master node will be able to provide more power resources for computational purposes than nodes that are located further away whose available power falls short of the power requirements. The master node’s energy savings varies with distance Dmax and network size Nnodes as shown in Fig. 6. It is observed that, the savings metric does not vary for short distances less than 150 m. Thereafter, the savings metric degrades with increase in distance. For
95
Maximized master node energy savings (%)
90 85 80 75 70 65 60 55 50 45 50 100 150 200 250 300 350 400 450 500
Nnodes = 10 N
nodes
= 14
Nnodes = 18
Network range Dmax (m)
Fig. 6. Maximized master node energy savings for various network ranges Dmax and network sizes.
Please cite this article in press as: D. Datla et al., Wireless distributed computing in cognitive radio networks, Ad Hoc Netw. (2011), doi:10.1016/j.adhoc.2011.04.002
D. Datla et al. / Ad Hoc Networks xxx (2011) xxx–xxx
11
60
50
40
30
20
NFB = 7 N N = 11 = 14
10
FB FB
NFB = 17
0 5 10 15 20
T2
25
30
35
Remaining power P
(watts)
Fig. 7. Maximized master node energy savings for various remaining power PT2 and computational workloads.
smaller intervals of the uniform distribution (shorter Dmax), the number of slave nodes that lie within a favorably close range to the master node are high. However, for larger network ranges (larger Dmax), there can be some nodes located far away from the master node. When the network size is increased, the number of candidate slave nodes also increases. Thus, in the case of larger networks, the savings metric does not degrade rapidly with distance. The variation in the master node’s energy savings with the remaining power P jT has been plotted in Fig. 7 for various workloads and a network size of 3 nodes. PjT has been generated as a random variable that is uniformly distributed in the interval [5, PT2]. The master node achieves savings by delegating the workload when there is suf?cient remaining power resources in the network. This is re?ected in Fig. 7, where the master node achieves savings for higher workloads for higher values of PT2. In addition, the curves ?atten when the nodes have suf?cient power remaining to process the allocated workload and, thereafter, any increase in PT2 does not impact the workload allocation and the savings.
load. Based on the analysis, the general characteristics of WDC networks can be summarized as follows. WDC exploits non-linearity in the processor characteristics. Not all computing platforms achieve power bene?ts from WDC. Platforms with highly non-linear computational power-frequency characteristics and high power computation tasks bene?t more from WDC. The power and energy bene?ts achieved from WDC are negated by the communication overhead. Hence, WDC is bene?cial when the communication overhead does not dominate over computation power consumption. When uniform workload allocation is employed in homogeneous environments, the network power savings and the master node’s energy savings improve with Nnodes until the communication overhead begins to dominate the savings. The analysis was performed for heterogeneous environments by applying the proposed workload allocation algorithm to an example CE computational task. When resource constraints are taken into consideration while using the proposed algorithm, the master node’s energy savings is maximized for a particular minimum network size. Thereafter, additional number of nodes do not impact the master node’s energy consumption. A similar trend is observed when the master node’s savings are analyzed for different values of remaining power. Furthermore, the master node’s energy savings improves with network size in the case of networks located over large areas.
Maximized master node energy savings (%)
Acknowledgments This work was supported by DARPA (NSWCDD Contract number: N00178-09-D-3017), ONR (Grant No. N30001407-01-0536) and NSF.
References
[1] J. Mitola, Cognitive Radio Architecture: The Engineering Foundations of Radio XML, vol. 1, John Wiley and Sons, 2006. [2] T. Yucek, H. Arslan, A survey of spectrum sensing algorithms for cognitive radio applications, Communications Surveys & Tutorials, IEEE 11 (1) (2009) 116–130. [3] W. Headley, J. Reed, C. da Silva, Distributed cyclic spectrum featurebased modulation classi?cation, in: Wireless Communications and Networking Conference, 2008. WCNC 2008. IEEE, 2008, pp. 1200– 1204. [4] P. Sutton, K. Nolan, L. Doyle, Cyclostationary signatures in practical cognitive radio applications, Selected Areas in Communications, IEEE Journal on 26 (2008) 13–24. [5] T.W. Rondeau, Application of Arti?cial Intelligence to Wireless Communications. PhD thesis, Virginia Tech, 2007. [6] T.R. Newman, B.A. Barker, A.M. Wyglinski, A. Agah, J.B. Evans, G.J. Minden, Cognitive engine implementation for wireless multicarrier transceivers, Journal on Wireless Communications and Mobile Computing 7 (9) (2007) 1129–1142. [7] H.I. Volos, R.M. Buehrer, Cognitive engine design for link adaptation: an application to multi-antenna systems, IEEE Transactions on Wireless Communications 9 (2010) 2902–2913. [8] A. He, J. Gaeddert, K. Bae, T.R. Newman, J.H. Reed, L. Morales, C. Park, Development of a case-based reasoning cognitive engine for IEEE 802.22 WRAN applications, ACM Mobile Computing and Communications Review 13 (2) (2009) 37–48. [9] D. Datla, X. Chen, T.R. Newman, J.H. Reed, T. Bose, Power ef?ciency in wireless network distributed computing, in: IEEE Vehicular Technology Conference, Anchorage, AK, USA, 2009. [10] N.A. Lynch, Distributed Algorithms. The Morgan Kaufmann Series in Data Management Systems, ?rst ed., 1996.
6. Conclusions WDC has been introduced as a technology that reduces the power consumption per node as well as that of the network, and enables ef?cient execution of wireless applications as well as network management services in CRNs that require abundant power and computational resources. WDC is particularly well suited for advanced wireless applications which involve a close interaction between the communication and computation processes that deliver services under stringent resource constraints. In WDC, a computational task is executed among a network of collaborating nodes in a distributed manner as against performing the same task on a single node. The analysis presented in this paper aids CRs in making decisions between local and distributed processing based on perceived network conditions and computational work-
Please cite this article in press as: D. Datla et al., Wireless distributed computing in cognitive radio networks, Ad Hoc Netw. (2011), doi:10.1016/j.adhoc.2011.04.002
12
D. Datla et al. / Ad Hoc Networks xxx (2011) xxx–xxx Haris I. Volos is currently a Postdoctoral Associate with the Bradley Department of Electrical and Computer Engineering at Virginia Tech. He received his B.S. degree from the Old Dominion University, and both his M.S. and PhD degrees from Virginia Tech, all in Electrical Engineering. Dr. Volos research interests include channel modeling, softwarede?ned radios, cognitive radio, smart grid, and wireless distributed computing. Dr. Volos is a recipient of the 2011 Paul E. Torgersen research excellence award and the 2010 Fred W. Ellersick MILCOM award for the best paper presented in the unclassi?ed technical program.
[11] M.K. Goff, Network Distributed Computing: Fitscapes and Fallacies, Prentice Hall PTR, 2004. [12] W. Jia, W. Zhou, Distributed Network Systems: From Concepts to Implementations, First ed., Springer, 2004. [13] S. Abdelhak, R.S. Chaudhuri, C.S. Gurram, S. Ghosh, M. Bayoumi, Energy-aware distributed qr decomposition on wireless sensor nodes, The Computer Journal (2010). [14] Y. Yu, V.K. Prasanna, ‘‘Energy-balanced task allocation for collaborative processing in networked embedded systems,’’ in: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool support for embedded systems (LCTES), vol. 38, San Diego, CA, USA, July 2003. [15] Y. Yu, V. Prasanna, ‘‘Power-aware resource allocation for independent tasks in heterogeneous real-time systems,’’ in: Proceedings of Ninth International Conference on Parallel and Distributed Systems (CAPDS), pp. 341–348, 2002. [16] Y. Yu, V.K. Prasanna, Energy-balanced task allocation for collaborative processing in wireless sensor networks, Journal Mobile Networks and Applications 10 (2005). [17] A.B. Olsen, F.H.P. Fitzek, P. Koch, ‘‘Evaluation of cooperative task computing for energy aware wireless networks,’’ in: Proceedings of International Workshop on Wireless Ad-Hoc Networking (IWWAN), 2005. [18] T. Xie, X. Qin, An energy-delay tunable task allocation strategy for collaborative applications in networked embedded systems, IEEE Transactions on Computers 57 (2008) 329–343. [19] D.P. Vidyarthi, B.K. Sarker, A.K. Tripathi, L.T. Yang, Scheduling in Distributed Computing Systems: Analysis, Design and Models, Springer, 2008. [20] E.Y.S.L. Perng-Yi Richard MA, M. Tsuchiya, A task allocation model for distributed computing systems, IEEE Transactions on Computers C-31 (1982) 41–47. [21] D. Datla, S.M. Hasan, J.H. Reed, T. Bose, Fundamental issues of wireless distributed computing in sdr networks,’’ in: SDR’10 Technical Conference and Product Exposition, Washington, DC, USA, 2010. [22] D. Datla, T. Tsou, T.R. Newman, J.H. Reed, T. Bose, ‘‘Waveform level computational energy management in software de?ned radios,’’ in: SDR’09 Technical Conference and Product Exposition, Washington, DC, USA, 2009. [23] R. Min, A. Chandrakasan, ‘‘A framework for energy-scalable communication in high-density wireless networks,’’ in: Proceedings of the International Symposium on Low Power Electronics and Design ISLPED ’02, 2002, pp. 36–41. [24] A. Sinha, A.P. Chandrakasan, ‘‘Energy aware software,’’ in: Thirteenth International Conference on VLSI Design, Calcutta, India, 2000, pp. 50–55. [25] A. Sinha, A.P. Chandrakasan, ‘‘Jouletrack-a web based tool for software energy pro?ling,’’ in: Proceedings of Design Automation Conference, 2001, pp. 220–225. [26] S.R. Cui, Cross-Layer Optimization in Energy Constrained Networks. PhD thesis, Stanford University, 2005. [27] S. Cui, A.J. Goldsmith, A. Bahai, Energy-ef?ciency of mimo and cooperative mimo techniques in sensor networks, IEEE Journal on Selected Areas in Communications 22 (2004) 1089–1098. [28] A.J. Goldsmith, S.-G. Chua, Variable-rate variable-power MQAM for fading channels, IEEE Transactions on Communications 45 (1997) 1218–1230. [29] H.I. Volos, R.M. Buehrer, ‘‘On Balancing Exploration vs. Exploitation on a Cognitive Engine for Multi-Antenna Systems,’’ in: Proceedings of the IEEE Global Telecommunications Conference, 2009, pp. 1–6.
S.M. Hasan is currently a Research Scientist with the Bradley Department of Electrical and Computer Engineering at Virginia Tech. He received his B.S. degree from the Bangladesh University of Engineering and Technology, M.S. degree from the University of Tennessee, Knoxville, and Ph.D. from the Virginia Tech, all in Electrical Engineering. His research interests are in the RF front end, software radio and cognitive radio areas. He was the Recipient of the 2007 William Bazzy Fellowship from the Microwave Journal. He was also the Recipient of the ?rst prize of the IEEE Myron Zucker Student Design Award in 2001.
Jeffrey H. Reed is the Willis G. Worcester Professor in the Bradley Department of Electrical and Computer Engineering at Virginia Tech. He currently serves as Director of the newly formed umbrella wireless organization Wireless@ Virgina Tech. Dr. Reed received his B.S. M.S., and Ph.D. from the University of California, Davis in 79–87. Dr. Reed has provided signi?cant contributions in the area of software radio and communications signal processing. Speci?c contributions include the development of hardware architectures for software radios based on recon?gurable computing, prototype hardware development, assistance in standardizing software architectures, development of software radio tools in education and research that are available for public domain download and creation of analysis procedures for cognitive software radios. His textbook, Software Radios: A Modern Approach to Radio Design, is based on his research experience with ONR, DARPA, IT, and Samsung, and is one of the ?rst books devoted exclusively to software radios. Dr. Reed has served on several company advisory boards. He is cofounder of CRT. In 2005, Dr. Reed became Fellow to the IEEE for contributions to software radio and communications signal processing and for leadership in engineering education.
Dinesh Datla is currently pursuing his Ph.D. degree in the Bradley Department of Electrical and Computer Engineering at Virginia Tech (Blacksburg, VA, USA). He received his MS in Electrical Engineering from the University of Kansas (Lawrence, KS, USA) in 2007 and BE in Electronics and Communications from the University of Madras (Chennai, India) in 2004. His current research interests include wireless distributed computing in software-de?ned radio networks, cognitive radios and dynamic spectrum access radios.
Tamal Bose received the Ph.D. degree in electrical engineering from Southern Illinois University in 1988. After a faculty position at the University of Colorado, he joined Utah State University in 2000, where he served as the Department Head and Professor of Electrical and Computer Engineering from 2003 to 2007. Currently, he is Professor in the Bradley Department of Electrical and Computer Engineering at Virginia Tech. He is the Associate Director of Wireless@VT and Director of the NSF center site WICAT@VT. The research interests of Dr. Bose include signal classi?cation for cognitive radios, channel equalization, adaptive ?ltering algorithms, and
Please cite this article in press as: D. Datla et al., Wireless distributed computing in cognitive radio networks, Ad Hoc Netw. (2011), doi:10.1016/j.adhoc.2011.04.002
D. Datla et al. / Ad Hoc Networks xxx (2011) xxx–xxx non-linear effects in digital ?lters. He is author of the text Digital Signal and Image Processing, John Wiley, 2004 and also the author or co-author of over 120 technical papers. Dr. Bose served as the Associate Editor for the IEEE Transactions on Signal Processing from 1992 to 1996. He is currently on the editorial board of the IEICE Transactions on Fundamen-
13
tals of Electronics, Communications and Computer Sciences (Japan) and Research Letters in Signal Processing. He also served on the organizing committees of several international conferences and workshops. He is an IEEE EAC program evaluator and a member of the DSP Technical Committee for the IEEE Circuits and Systems society.
Please cite this article in press as: D. Datla et al., Wireless distributed computing in cognitive radio networks, Ad Hoc Netw. (2011), doi:10.1016/j.adhoc.2011.04.002