# Minimizing Wireless Connection BER through the Dynamic Distribution of Budgeted Power

←

→

**Page content transcription**

If your browser does not render page correctly, please read the page content below

1 Minimizing Wireless Connection BER through the Dynamic Distribution of Budgeted Power Bilal Khan∗ Ghassen Ben Brahim† Ala Al-Fuqaha† Mohsen Guizani† Abstract— We develop a new dynamic scheme which contin- In this paper, we will not consider mobility-related issues. uously redistributes a fixed power budget among the wireless Although our investigation makes the simplifying assumption nodes participating in a multi-hop wireless connection, with the of a scenario in which mobility does not greatly impact power objective of minimizing the end-to-end wireless connection bit error rate (BER). We compare the efficacy of our scheme with allocation decisions, the conclusions we present are neverthe- two static schemes: one that distributes power uniformly, and less significant in the broader context of power management one that distributes it proportionally to the square of inter-hop in wireless and ad-hoc networks. distances. In our experiments we observed that the dynamic The remainder of the paper is organized as follows. We allocation scheme achieved superior performance, reducing BER begin in Section II with an exposition of prior related research by using its ability to distribute the power budget. We quantified the sensitivity of this performance improvement to various envi- work. Then, in Sections III and IV we define the problem and ronmental parameters, including power budget size, geographic the presumed network model. In Section V, we describe the distance, and the number of hops. protocol by which power is redistributed dynamically, to attain Index Terms— wireless ad-hoc networks, multi-hop path, bit minimum BER. In Section VI we describe the experimental error rate, power budget, optimal power distribution. setup, and then analyze the results of the simulation study in Section VII, by comparing the proposed protocol against other traditional power distribution schemes. I. I NTRODUCTION New distributed computing/communication applications drive the energy requirements of wireless ad-hoc systems II. R ELATED W ORK ever upwards, while simultaneously, the batteries which power Approaches for efficient power management have been wireless devices present a hard constraints on the operation of investigated at various protocol layers by several researchers, mobile computing systems. Recent developments in devices (e.g. see [14], [13], [4]) 1. At the Physical layer: Using with tunable transmission power enable us to manage the directional antennae, applying knowledge of spatial neighbor- tension of power supply and power demand using dynamic hood as a hint in setting transmission power; 2. At the Data- power redistribution schemes. In this paper, we present results link layer: Avoiding unnecessary retransmissions, avoiding of recent investigations along this avenue. Our objective is to collisions in channel access whenever possible, allocating optimize the bit error rate (BER) of connections—and hence contiguous slots for transmission and reception whenever pos- the packet-level error rate (PER) experienced at the network sible; 3. At the Network layer: Considering route-relay load, layer. Since many applications require a minimal Quality of considering battery life in route selection, reducing frequency Service (QoS) to guarantee acceptable responsiveness, such an of control messages, optimizing size of control headers, route improvement can greatly benefit network function. reconfiguration; 4. At the Transport layer: Avoiding repeated Historically, reconciling the gap between power consump- retransmissions, handling packet loss in a localized manner, tion and supply involved [14] solving the following issues: (i) using power-efficient error control schemes. improving the power efficiency in the system; and (ii) prevent- One broad category of solutions consists of energy aware ing the system deconstruction due to unfair power usage. In routing protocols (e.g. see [13], [6], [8]). In wired networks, our earlier work [2], [3], we proposed addressing these issues the emphasis has traditionally been on maximizing end-to-end through the principle of optimal allocation of budgeted power; throughput and minimizing delay. To maximize the lifetime we introduced a model in which every connection request is of mobile hosts, however, routing algorithms must select the assigned a fixed power budget to support its instantiation. best path from the viewpoint of power constraints and route In this paper, we present a scheme which dynamizes these stability. Routes requiring lower levels of power transmission approaches by enabling the redistribution of a power budget are generally preferred, but this can adversely affect end-to- among the constituent nodes in a multi-hop connection, with end throughput. Transmission with higher power increases the the objective of minimizing the wireless connection BER. probability of successful transmission, although high power Standard models of wireless ad-hoc networks typically con- strategies also result in more cross-node interference, destroy sider infrastructure-less networks in which every node assumes existing transmission bands, and thus cause the network to the role of both a host and router, and every node is mobile. have blocked connections. In [5] and [1], Banerjee and Misra showed that energy-aware routing algorithms that are solely † Western Michigan University, MI. ∗ John Jay College of Criminal Justice, City University of New York, NY based on the energy spent in a single transmission are not 10019. able to find minimum energy paths for end-to-end reliable

packet transmissions, in both End-to-End and Hop-by-Hop received by node j is given by retransmission settings. Pt (i) Our own prior work [3] was a natural extension of Misra Prcv (j) = , (1) c × dα [1] and Banerjee [5], reframed by normalizing experimental ij scenarios using a fixed power budgets for each connection. where dij is the distance between nodes i and j. α and c are In [2], we presented an experimental evaluation of those both constant, and usually 2 ≤ α ≤ 4 (See [5]). In order to techniques, showing how data replication along multiple paths correctly decode the signal at the receiver side, it is required can be used to lower packet error rate of application layer that connections in wireless ad-hoc networks under power budget P (j) > β0 × N0 , (2) constraints. This work begins at the point where energy aware routing where β0 is the required signal to noise ratio (SNR) and N0 ends. Here we propose a new dynamic scheme that con- is the strength of the ambient noise. We denote the minimum tinuously redistributes the power budget among all nodes signal power at which node i is able to decode the received across a multi-hop wireless connection with the objective of signal as Pmin . minimizing the wireless connection BER. Each link (i, j) has a computable bit error rate BER(i, j), which represents the probability of the occurrence of an error during the data transfer over that link. The relationship III. P ROBLEM D EFINITION between the bit error rate BER over a wireless channel and Consider a single connection request between a source node the received power level Prcv is a function of the modulation s and a destination node t, and assume that a transmission scheme. It can be expressed in general as follows [5]. power budget P has been specified for this connection. The s ! question to be answered is how should P be distributed among Prcv Cte BER ∝ Q , (3) intermediate nodes of the connection if the objective is to f Pnoise minimize the end-to-end connection bit error rate? We shall where Pnoise is the noise spectral density, f is the raw channel assume, as assumed in other similar investigations (e.g. [11]), bit error rate, and Q(x) is defined as follows. that each node has the ability to send with dynamically tunable 2 x −t2 Z transmission power, and that node mobility is insignificant Q(x) = 1 − e dt. (4) when compared to routing convergence times. The proposed π 0 dynamic power distribution protocol is implemented on top of Since we are only interested in studying the general depen- a routing protocol that is responsible for providing a multi-hop dence of the bit error rate on the received signal power, we path between s and t, within total power budget constraints— will consider the non coherent binary orthogonal Frequency designing such an energy-aware routing protocol is beyond the Shift Keying (FSK) modulation scheme. Other modulation scope of this paper. schemes can be analyzed in similar way, however closed- Our design idea is founded on the simple observation that form analysis may not be always possible. For this specific in a multi-hop path the distance between two consecutive modulation scheme, the instantaneous channel bit error rate intermediate nodes varies on a hop-by-hop basis. For nodes BER is given by [9], [10], [7] to be: which are a short distance from each other, less power can be 1 − 2PPrcv allocated while still attaining good channel bit error rate. When BER = e noise (5) 2 two consecutive nodes are far from each other, a weak trans- mission power would result in a high wireless channel bit error A path consisting Qrof a sequence of links L1 , . . . , Lr has a rate. We present a dynamic power redistribution scheme based BER equal to 1 − `=1 1 − BER(L` ) on geographical distance, which allows nodes to negotiate the amount of power they use (while remaining within connection V. DYNAMIC S CHEME budget constraints) thereby optimizing overall connection bit The proposed protocol operates on all (overlapping) consec- error rate. utive triplets of nodes within the connection (s, t). Within each triplet, we denote the nodes to as the upstream node, the central node, and the downstream node. This naming convention is IV. N ETWORK M ODEL illustrated in Figure 1. We consider a wireless ad-hoc network consisting of N A node enters the protocol by simultaneously sending nodes equipped with omni-directional antennas that can dy- an Update message to its upstream and downstream neigh- namically adjust their transmission power. We model this bors. The Update message describes its present transmission network as a linear geometric graph G = (V, E), where V strength. A node receiving an update uses its contents and the is the set of nodes and E is the set of edges. Each node is actual received signal strength to deduce an estimate of the assigned a unique ID i in {1, . . . , |V |}, and node i can send distance to the sender of the Update. Thus each node (viewed data with a dynamically tunable transmission power in the in its central role) maintains estimates of distance to upstream range [0, Pmax (i)]. and downstream nodes. When the central node receives an Wireless propagation suffers severe attenuation [5] and [12]. update message informing it of the transmission power and If node i transmits with power P (i), the power of the signal (implicitly) distance to a neighbor, it determines the optimal

Upstream Central Downstream Upstream Node Central Node Downstream Node node node node Update from neighbors Get Initial Get Initial Signal Get Initial Signal Signal Power Power strength Power strength strength s Update message Update message t (1) Estimate the distance to the upstream and downstream nodes Fig. 1. Multi-hop path description (2) Compute best Pow er distribution negotiation power allocation between central and upstream nodes (3) if a significant redistribution of power between itself and the upstream node. change is required then: This local optimization is computed on the basis of the analytic BER model presented in the previous section. In effect the Decrease transmit signal power central node acts greedily to minimize the BER of the two Power Transfer Message hop sub-path from its upstream node to the downstream node. Increase If the local optimization shows that a significant redistribution transmit signal power of power is required, and this redistribution will not cause Ack message Update to neighbors Update Message Update the received signal strength to drop below Pmin at any node, message Update local information then the central node is able push power downstream (Figure about neighbor 2) or push power upstream (Figure 3). It accomplishes this by Power Request and Power Transfer messages, respectively. Receipt of a Power Request always causes a node to reduce its Fig. 2. Event sequence diagram: pushing power upstream transmission power and reply with a Power Transfer Message. Receipt of a Power Transfer Message always causes a node to increase its transmission power and reply with a Ack Message. two end points. During the experiment, all network parameters Receipt of Ack and Update Messages always result in further involved in the system are kept in the following ranges: propagation of an Update Message. The power reallocation • Path Length: We consider path lengths ranging from short process is negotiated concurrently between all (overlapping) (5 intermediate nodes) to long (25 intermediate nodes). triplets of nodes via a distributed protocol. The protocol is • Power budget: We consider connection power budgets said to have converged if the total power exchange drop below ranging from small (1 Watt) to large (10 Watts). a user specified threshold. In the rest of this paper, we will • Distance: We consider scenarios in which the two end- refer to the converged distribution attained by this distributed points range from nearby (100m) to distant (400m). protocol as the Dynamic scheme. We compare the performance • α: A scaling constant is kept fixed at 2, as appropriate to of the dynamic protocol against two static schemes. our connection scales. • SN R: The Signal to Noise Ratio of the wireless channel is kept fixed at 1mW, as appropriate to a typical SN R A. Uniform Scheme value for wireless channel. Given a connection between nodes s and t with length The graphs in the next section depict the average values k + 1 hops and a total power budget P . The uniform power collected from 104 trial runs of each experiment scenario. distribution scheme consists of allocating to each of the k We demonstrate how protocol optimally distributes this budget nodes (excluding the destination node) a uniform fraction of among the nodes of the multi-hop path under consideration. the total power Punif = Pk . VII. R ESULTS AND A NALYSIS B. Sqr Scheme To begin, we study the impact of the variance in inter-node Under this power distribution scheme, the power is allocated distances on the improvement (in connection BER) achieved based on the square of the distance to the next hop along by the Dynamic scheme when compared to the Uniform the path towards the destination node. Specifically, given a scheme. Intuitively, one might expect that in a high variance connection between nodes s and t with length N − 1 hops scenario the dynamic power distribution would outperform and a total power budget P, each node j will be allocated a PN −1 uniform allocation of power, because the negotiation process power Psqr such that Psqr = P d2j / i=1 d2i , where dj is the would converge to a significantly different power distribution. distance from node j to node j + 1 along the path. However, Figure 4 shows that the effects are more subtle and cannot be captured by a single parameter of variance. For VI. E XPERIMENTAL S ETUP instance, for a variance value of 37m, the improvement varies In our simulations, we consider networks where the inter- from 4% to 24%. Similarly, when the variance is small (say mediate nodes are randomly distributed along a line between 7m), the improvement varies from 3% to 17%. We conclude

Upstream Node Central Node Downstream Node Power Distribution Scheme Efficacy 50 Dynamic/Sqr Dynamic/Uniform Update from neighbors Get Initial Signal Power Get Initial Signal Get Initial Signal 40 Sqr/Uniform Power strength Power strength Percentage Improvement strength 30 Update message Update message 20 10 (1) Estimate the distance to the upstream and 0 downstream nodes (2) Compute the best power allocation -10 between the upstream Power distribution negotiation and downstream nodes (3) If a significant -20 change is required 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 then: Power (mW) Power Request Message Fig. 5. Percentage improvement vs. total connection power budget Decrease transmit signal power Power Transfer Message conducted at that power setting. Similarly, the curve indicates Increase transmit power that with a 5W power budget, Sqr performed almost 20% U pdate to neighbors Update Message Update Message Ack worse than Uniform. Update local information Figure 5 illustrates the impact of the power budget on the about neighbor performance of each power allocation scheme. The distance between endpoints was fixed at 120m, and the number of Fig. 3. Event sequence diagram: drawing power downstream intermediate nodes was fixed at 9—thus the average internode spacing was approximately 12m, in the range of present 25 path length = 5 54M b/s wireless technology. Considering the slopes of these curves we conclude that the improvement of the Dynamic scheme relative to the Uniform and the Sqr schemes increases 20 as the total connection power budget increases. For example, comparing Dynamic to Sqr, we see that at 1W power budget 15 Dynamic outperforms Sqr by 8% in terms of BER, while by improvement 9W the improvement rises to 40%. We note, however, that 10 the relative performance of Uniform and Sqr schemes is not monotone: when the power budget is small, the Sqr scheme outperforms the Uniform approach, but as the power budget 5 increases to 10W , the conclusion is reversed. Comparing the heights of the curves, we conclude that the proposed dynamic 0 0 5 10 15 20 25 30 35 40 45 50 scheme outperforms both of the other power allocation tech- variance niques in both fair and good wireless channel conditions. Figure 6 illustrates the impact of varying the distance Fig. 4. Percentage improvement of Dynamic over Uniform vs. variance between the connection end points, while keeping constant both the number of intermediate hops and the total power that the performance of the dynamic scheme is not well- budget. The connection power budget was fixed at 2200mW , modeled by a coarse measure such as variance. and the number of intermediate nodes was fixed at 10— We compare the performance of our Dynamic scheme with thus the average node transmission power was approximately both the Uniform and the Sqr schemes. For each of these 220mW , in the range of present 54M b/s wireless technology. schemes, we study the impact of considering different path Considering the slopes of these curves we conclude that the lengths, connection power budgets, and end point distance. improvement of the Dynamic scheme relative to the Uniform The legends of each curve indicate the average relative per- and the Sqr schemes decreases as the total distance increases. formance of two schemes. For example in Figure 5, the curve For example, comparing Dynamic to Sqr, we see that at 100m titled Dynamic/Sqr shows the average value of the quantity distance Dynamic outperforms Sqr by 16% in terms of BER, but at 200m the improvement drops to 3%. We note, however, BER(Sqr) − BER(Dynamic) . that the relative performance of Uniform and Sqr schemes BER(Sqr) is not monotone: The lower curve of Figure 6 reaches a The fact that this curve passes through the point local minimum at distance 110m. At connection distances (8000mW, 40%) indicates that when the power budget below this critical value, the improvement of Uniform over was 8W , the BER achieved by Dynamic was (on average) Sqr decreases as the distance increase, but this behavior gets 40% lower than what was achieved by Sqr, over the 104 trials reversed for distances bigger than 110m. By comparing the

Power Distribution Scheme Efficacy VIII. C ONCLUSION AND F UTURE W ORK 60 In all the experiments, the dynamic allocation scheme Dynamic/Sqr 50 Dynamic/Uniform achieved superior performance relative to the uniform and Sqr/Uniform Percentage Improvement 40 distance-squared proportional schemes. This improvement re- sulted from the dynamic scheme ability to reduce the BER by 30 dynamically allocating the power budget among the interme- 20 diate nodes. 10 In all the experiments conducted, the proposed scheme was 0 seen to converge in fewer than 10 iterations per node. The convergence rates and communication overhead was tunable -10 by adjusting the definition of “significant change” in the -20 protocol. Because we were not considering mobility, this 50 100 150 200 250 300 Distance (meters) cost was taken as the one-time initialization cost for the connection. In future, we intend to extend our consideration to Fig. 6. Percentage improvement vs. total connection distance the fully mobile setting. Because our power allocation protocol is decentralized and dynamic, it can react to node mobility by Power Distribution Scheme Efficacy redistributing power in a manner which optimizes the BER. To 20 evaluate the efficacy of the protocol in the mobile setting, we Dynamic/Sqr are presently conducting experiments to quantify the tradeoffs 15 Dynamic/Uniform Sqr/Uniform between convergence thresholds, control-traffic overhead, and Percentage Improvement 10 resultant improvement in BER. 5 0 R EFERENCES -5 [1] S. Banerjee and A. Misra. Energy Efficient Reliable Communication for Multi-hop Wireless Networks. Journal of Wireless Networks (WINET), -10 2004. [2] G. B. Brahim and B. Khan. Budgeting Power: Packet Duplication and -15 Bit Error Rate Reduction in Wireless Ad-hoc Networks. International -20 Wireless Communications and Mobile Computing Conference, IWCMC, 5 10 15 20 25 Vancouver, Canada, 2006. Path Length (hops) [3] G. B. Brahim, B. Khan, A. Al-Fuqaha, and M. Guizani. Using Energy Efficient Overlay to Reduce Packet Error Rates in Wireless Ad-Hoc Fig. 7. Percentage improvement vs. connection length Networks. International Conference on Communications, ICC, 2006. [4] R. Cravets and P. Krishnan. Power Management Techniques for Mobile Communication. NOBICOM 98 Dallas Texas USA, 1998. [5] Q. Dong and S. Banerjee. Minimum Energy Reliable Paths Using Unreliable Wireless Links. MobiHoc’05, Urbana-Champaign, Illinois, heights of the curves, we conclude that the proposed dy- May 25-27, 2005. namic scheme outperforms both of the other power allocation [6] C. E. Jones, K. M. Sivalingam, P. Agrawal, and J. C. Chen. A Survey techniques in both small and large distances scenarios. As of Energy Efficient Network Protocols for Wireless Networks. Wireless Networks 7, 343 358, 2001. the distances become larger, the difference between power [7] G. Laurer. Packet Radio routing, Chapter 11, pages 351-396, Prentice allocation schemes becomes immaterial. Hall 1995. [8] Q. Li, J. Aslam, and D. Rus. Online Power-aware Routing in Wireless Figure 7 illustrates the impact of varying the path length Ad-hoc Networks. Proceedings of ACM Mobicom’2001, pp97-107, (in terms of the number of intermediate nodes) between the 2001. source and destination nodes while keeping constant both the [9] S. Loyka and F. Gagnon. Performance Analysis of the V-BLAST Algorithm: An Analytical Approach. IEEE Transactions onWireles distance between the connection end points and the total power Communications, Vol.3 No.4, 2004. budget. The connection power budget was fixed at 2200mW , [10] J. G. Proakis. Digital Communications, McGraw Hill, 2001. and the number of distance was fixed at 120m–drawing upon [11] A. Srinivas and E. Modiano. Minimum Energy Disjoint Path Routing in Wireless Ad-hoc Networks. MobiCom’03, San Diego, California, the two experiment scenarios described earlier. Considering September 14-19, 2003. the slopes of these curves we conclude that the improvement [12] J. Tang and G. Xue. Node-Disjoint Path Routing in Wireless Networks: of the the Dynamic scheme relative to the Sqr scheme lightly Tradeoff between Path Lifetime and Total Energy. IEEE Communica- tions Society, 2004. decreases as the number of the intermediate hops increases. [13] C.-K. Toh. Maximum Battery Life Routing to Support Ubiquitous Mo- However, in case of Dynamic versus Sqr and Sqr versus bile Computing in Wireless Ad Hoc Networks. IEEE Communications Uniform schemes, the improvement increases as the length Magazine, June 2001. [14] Y. Zhang and L. Cheng. Cross-Layer Optimization for Sensor Networks. of the path increases. For example, when considering a 10 New York Metro Area Networking Workshop, New York, September 12, hop path, Dynamic achieved an improvement of 7% over the 2003. Uniform scheme, while for a 20 hop path, the improvement was 10%. Comparing the heights of the curves, we conclude that the proposed dynamic scheme outperforms both of the other power allocation techniques for both short and long paths scenarios.

You can also read