A set of identical, mobile agents is deployed in a weighted network. Each agent has a battery--a power source allowing it to move along network edges. An agent uses its battery proportionally to the distance traveled. We consider two tasks: convergecast, in which at the beginning, each agent has some initial piece of information, and information of all agents has to be collected by some agent; and broadcast in which information of one specified agent has to be made available to all other agents. In both tasks, the agents exchange the currently possessed information when they meet. The objective of this paper is to investigate what is the minimal value of power, initially available to all agents, so that convergecast or broadcast can be achieved. We study this question in the centralized and the distributed settings. In the centralized setting, there is a central monitor that schedules the moves of all agents. In the distributed setting every agent has to perform an algorithm being unaware of the network. In the centralized setting, we give a linear-time algorithm to compute the optimal battery power and the strategy using it, both for convergecast and for broadcast, when agents are on the line. We also show that finding the optimal battery power for convergecast or for broadcast is NP-hard for the class of trees. On the other hand, we give a polynomial algorithm that finds a 2-approximation for convergecast and a 4-approximation for broadcast, for arbitrary graphs.In the distributed setting, we give a 2-competitive algorithm for convergecast in trees and a 4-competitive algorithm for broadcast in trees. The competitive ratio of 2 is proved to be the best for the problem of convergecast, even if we only consider line networks. Indeed, we show that there is no ( @math 2-∈)-competitive algorithm for convergecast or for broadcast in the class of lines, for any @math ∈>0.
In wireless sensor and ad hoc networks the power awareness has been often related to the data communication via efficient routing protocols (e.g. @cite_22 @cite_5 . However in many applications of mobile agents (e.g. those involving actively mobile, physical agents) the agent's energy is mostly used for it's mobility purpose rather than communication, since active moving often requires running some mechanical components, while communication mostly involves (less energy-prone) electronic devices. Consequently, in most tasks involving moving agents, like exploration, searching or pattern formation, the distance traveled is the main optimization criterion (cf. @cite_12 @cite_27 @cite_19 @cite_39 @cite_11 @cite_0 @cite_3 @cite_29 @cite_15 @cite_14 ). Single agent exploration of an unknown environment has been studied for graphs, e.g. @cite_12 @cite_3 , or geometric terrains, @cite_39 @cite_0 .
@cite_14 @cite_22 @cite_29 @cite_3 @cite_39 @cite_0 @cite_19 @cite_27 @cite_5 @cite_15 @cite_12 @cite_11
2022318368 2093917343 2126003739 2026472243
We investigate the problem of wireless power transfer in mobile ad-hoc networks. In particular we investigate which traversal strategy should a Mobile Charger follow in order to efficiently recharge agents that are randomly and dynamically moving inside an area of interest. We first formally define this problem as the Charger Traversal Decision Problem and prove its computational hardness. We then define a weighting function which evaluates several network parameters in order to prioritize the nodes during the charging process. Based on this function we define three traversal strategies for the MC; a global-knowledge strategy that uses an Integer Linear Program to optimize its trajectory; a global-knowledge strategy which tessellates the network area and prioritizes the charging process over each tile; a local-knowledge strategy that uses local network information collected and ferried distributively by the moving agents. We also evaluate two naive zero-knowledge strategies; a space-filling deterministic one in which the MC systematically sweeps the network area and a randomized one in which the MC performs a blind random walk. We evaluate these strategies both in homogeneous and heterogeneous agent distributions and for various network sizes with respect to number of alive nodes over time, energy distribution among the nodes over time and charging efficiency over distance traveled. Our findings indicate that in small networks network agnostic strategies are sufficient. However, as the network scales the use of local distributed network information achieves good performance-overhead trade-offs. Recently, energy efficiency in wireless networks has become an important objective. Aside from the growing proliferation of smartphones and other high-end devices in conventional human-to-human (H2H) communication, the introduction of machine-to-machine (M2M) communication or machine-type communication into cellular networks is another contributing factor. In this paper, we investigate quality-of-service (QoS)-driven energy-efficient design for the uplink of long term evolution (LTE) networks in M2M H2H co-existence scenarios. We formulate the resource allocation problem as a maximization of effective capacity-based bits-per-joule capacity under statistical QoS provisioning. The specific constraints of single carrier frequency division multiple access (uplink air interface in LTE networks) pertaining to power and resource block allocation not only complicate the resource allocation problem, but also render the standard Lagrangian duality techniques inapplicable. We overcome the analytical and computational intractability by first transforming the original problem into a mixed integer programming (MIP) problem and then formulating its dual problem using the canonical duality theory. The proposed energy-efficient design is compared with the spectral efficient design along with round robin (RR) and best channel quality indicator (BCQI) algorithms. Numerical results, which are obtained using the invasive weed optimization (IWO) algorithm, show that the proposed energy-efficient uplink design not only outperforms other algorithms in terms of energy efficiency while satisfying the QoS requirements, but also performs closer to the optimal design. Since ad hoc and sensor networks can be composed of a very large number of devices, the scalability of network protocols is a major design concern. Furthermore, network protocols must be designed to prolong the battery lifetime of the devices. However, most existing routing techniques for ad hoc networks are known not to scale well. On the other hand, the so-called geographical routing algorithms are known to be scalable but their energy efficiency has never been extensively and comparatively studied. In a geographical routing algorithm, data packets are forwarded by a node to its neighbor based on their respective positions. The neighborhood of each node is constituted by the nodes that lie within a certain radio range. Thus, from the perspective of a node forwarding a packet, the next hop depends on the width of the neighborhood it perceives. The analytical framework proposed in this paper allows to analyze the relationship between the energy efficiency of the routing tasks and the extension of the range of the topology knowledge for each node. A wider topology knowledge may improve the energy efficiency of the routing tasks but increases the cost of topology information due to signaling packets needed to acquire this information. The problem of determining the optimal topology knowledge range for each node to make energy efficient geographical routing decisions is tackled by integer linear programming. It is shown that the problem is intrinsically localized, i.e., a limited topology knowledge is sufficient to make energy efficient forwarding decisions. The leading forwarding rules for geographical routing are compared in this framework, and the energy efficiency of each of them is studied. Moreover, a new forwarding scheme, partial topology knowledge forwarding (PTKF), is introduced, and shown to outperform other existing schemes in typical application scenarios. A probe-based distributed protocol for knowledge range adjustment (PRADA) is finally introduced that allows each node to efficiently select online its topology knowledge range. PRADA is shown to rapidly converge to a near-optimal solution. With the tremendous growth in wireless network deployment and increasing use of mobile devices, e.g., smartphones and tablets, improving energy efficiency in such devices, especially with communication driven workloads, is critical to providing a satisfactory user experience. Studies show that signal strength plays an important role on energy consumption of cellular data communications. While energy consumption can be minimized by accurately predicting signal strengths and reacting to it in real-time, the dynamic nature of wireless environments makes signal strengths highly unpredictable. In this paper, after analyzing in detail the signal strength variation and its impact on energy consumption, we propose to use crowdsourcing approach to optimize mobile devices’ energy efficiency by utilizing signal strength traces reported shared by other users devices in cellular networks. Via a comprehensive measurement study, we observe that signal strength traces collected from different devices are pseudo-identical, and they even exhibit similar threshold-based behaviors in the relationship between signal strength and device power consumption. Based on our observations, we propose a predictive scheduling algorithm that: (i) selects the right set of signal strength traces based on its location, (ii) applies a filter to smooth out signal strengths and hide abrupt changes, (iii) digitizes the signal strength to “good” and “bad” areas, and (iv) schedules transmissions based on power-throughput characteristics to optimize the transmission energy efficiency. To demonstrate the efficacy of the proposed algorithms, we prototype the crowdsourcing-based predicative scheduling algorithm on Android-based smartphones. Our experiment results from real-life driving tests demonstrate that, by leveraging others’ signal traces, mobile devices can save energy up to 35 percent compared to the conventional opportunistic scheduling, i.e., schedule transmissions only based on instantaneous channel conditions.