Recently, benefiting from rapid development of energy harvesting technologies, the research trend of wireless sensor networks has shifted from the battery‐powered network to the one that can harvest energy from ambient environments. In such networks, a proper use of harvested energy poses plenty of challenges caused by numerous influence factors and complex application environments. Although numerous works have been based on the energy status of sensor nodes, no work refers to the issue of minimizing the overall data transmission cost by adjusting transmission power of nodes in energy‐harvesting wireless sensor networks. In this paper, we consider the optimization problem of deriving the energy‐neutral minimum cost paths between the source nodes and the sink node. By introducing the concept of energy‐neutral operation, we first propose a polynomial‐time optimal algorithm for finding the optimal path from a single source to the sink by adjusting the transmission powers. Based on the work earlier, another polynomial‐time algorithm is further proposed for finding the approximated optimal paths from multiple sources to the sink node. Also, we analyze the network capacity and present a near‐optimal algorithm based on the Ford–Fulkerson algorithm for approaching the maximum flow in the given network. We have validated our algorithms by various numerical results in terms of path capacity, least energy of nodes, energy ratio, and path cost. Simulation results show that the proposed algorithms achieve significant performance enhancements over existing schemes. Copyright © 2016 John Wiley & Sons, Ltd.
This content will become publicly available on October 1, 2024
Optimizing Sectorized Wireless Networks: Model, Analysis, and Algorithm
Future wireless networks need to support the increasing demands for high data rates and improved coverage. One promising solution is sectorization, where an infrastructure node (e.g., a base station) is equipped with multiple sectors employing directional communication. Although the concept of sectorization is not new, it is critical to fully understand the potential of sectorized networks, such as the rate gain achieved when multiple sectors can be simultaneously activated. In this paper, we focus on sectorized wireless networks, where sectorized infrastructure nodes with beam-steering capabilities form a multi-hop mesh network for data forwarding and routing. We present a sectorized node model and characterize the capacity region of these sectorized networks. We define the flow extension ratio and the corresponding sectorization gain, which quantitatively measure the performance gain introduced by node sectorization as a function of the network flow. Our objective is to find the optimal sectorization of each node that achieves the maximum flow extension ratio, and thus the sectorization gain. Towards this goal, we formulate the corresponding optimization problem and develop an efficient distributed algorithm that obtains the node sectorization under a given network flow with an approximation ratio of 2/3. Through extensive simulations, we evaluate the sectorization gain and the performance of the proposed algorithm in various network scenarios with varying network flows. The simulation results show that the approximate sectorization gain increases sublinearly as a function of the number of sectors per node.
more »
« less
- NSF-PAR ID:
- 10465972
- Date Published:
- Journal Name:
- ACM International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing (MobiHoc’23)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract -
Full-duplex (FD) wireless and phased arrays are both promising techniques that can significantly improve data rates in future wireless networks. However, integrating FD with transmit (Tx) and receive (Rx) phased arrays is extremely challenging, due to the large number of self-interference (SI) channels. Previous work relies on either RF canceller hardware or on analog/digital Tx beamforming (TxBF) to achieve SI cancellation (SIC). However, Rx beamforming (RxBF) and the data rate gain introduced by FD nodes employing beamforming have not been considered yet. We study FD phased arrays with joint TxBF and RxBF with the objective of achieving improved FD data rates. The key idea is to carefully select the TxBF and RxBF weights to achieve wideband RF SIC in the spatial domain with minimal TxBF and RxBF gain losses. Essentially, TxBF and RxBF are repurposed, thereby not requiring specialized RF canceller circuitry. We formulate the corresponding optimization problem and develop an iterative algorithm to obtain an approximate solution with provable performance guarantees. Using SI channel measurements and datasets, we extensively evaluate the performance of the proposed approach in different use cases under various network settings. The results show that an FD phased array with 9/36/72 elements can cancel the total SI power to below the noise floor with sum TxBF and RxBF gain losses of 10.6/7.2/6.9 dB, even at Tx power level of 30 dBm. Moreover, the corresponding FD rate gains are at least 1.33/1.66/1.68×.more » « less
-
Full-duplex (FD) wireless and phased arrays are both promising techniques that can significantly improve data rates in future wireless networks. However, integrating FD with transmit (Tx) and receive (Rx) phased arrays is extremely challenging, due to the large number of self-interference (SI) channels. Previous work relies on either RF canceller hardware or on analog/digital Tx beamforming (TxBF) to achieve SI cancellation (SIC). However, Rx beamforming (RxBF) and the data rate gain introduced by FD nodes employing beamforming have not been considered yet. We study FD phased arrays with joint TxBF and RxBF with the objective of achieving improved FD data rates. The key idea is to carefully select the TxBF and RxBF weights to achieve wideband RF SIC in the spatial domain with minimal TxBF and RxBF gain losses. Essentially, TxBF and RxBF are repurposed, thereby not requiring specialized RF canceller circuitry. We formulate the corresponding optimization problem and develop an iterative algorithm to obtain an approximate solution with provable performance guarantees. Using SI channel measurements and datasets, we extensively evaluate the performance of the proposed approach in different use cases under various network settings. The results show that an FD phased array with 9/36/72 elements can cancel the total SI power to below the noise floor with sum TxBF and RxBF gain losses of 10.6/7.2/6.9 dB, even at Tx power level of 30 dBm. Moreover, the corresponding FD rate gains are at least 1.33/1.66/1.68×more » « less
-
The densest subgraph problem in a graph (\dsg), in the simplest form, is the following. Given an undirected graph $G=(V,E)$ find a subset $S \subseteq V$ of vertices that maximizes the ratio $|E(S)|/|S|$ where $E(S)$ is the set of edges with both endpoints in $S$. \dsg and several of its variants are well-studied in theory and practice and have many applications in data mining and network analysis. In this paper we study fast algorithms and structural aspects of \dsg via the lens of \emph{supermodularity}. For this we consider the densest supermodular subset problem (\dssp): given a non-negative supermodular function $f: 2^V \rightarrow \mathbb{R}_+$, maximize $f(S)/|S|$. For \dsg we describe a simple flow-based algorithm that outputs a $(1-\eps)$-approximation in deterministic $\tilde{O}(m/\eps)$ time where $m$ is the number of edges. Our algorithm is the first to have a near-linear dependence on $m$ and $1/\eps$ and improves previous methods based on an LP relaxation. It generalizes to hypergraphs, and also yields a faster algorithm for directed \dsg. Greedy peeling algorithms have been very popular for \dsg and several variants due to their efficiency, empirical performance, and worst-case approximation guarantees. We describe a simple peeling algorithm for \dssp and analyze its approximation guarantee in a fashion that unifies several existing results. Boob et al.\ \cite{bgpstww-20} developed an \emph{iterative} peeling algorithm for \dsg which appears to work very well in practice, and made a conjecture about its convergence to optimality. We affirmatively answer their conjecture, and in fact prove that a natural generalization of their algorithm converges to a $(1-\eps)$-approximation for \emph{any} supermodular function $f$; the key to our proof is to consider an LP formulation that is derived via the \Lovasz extension of a supermodular function. For \dsg the bound on the number of iterations we prove is $O(\frac{\Delta \ln |V|}{\lambda^*}\cdot \frac{1}{\eps^2})$ where $\Delta$ is the maximum degree and $\lambda^*$ is the optimum value. Our work suggests that iterative peeling can be an effective heuristic for several objectives considered in the literature. Finally, we show that the $2$-approximation for densest-at-least-$k$ subgraph \cite{ks-09} extends to the supermodular setting. We also give a unified analysis of the peeling algorithm for this problem, and via this analysis derive an approximation guarantee for a generalization of \dssp to maximize $f(S)/g(|S|)$ for a concave function $g$.more » « less
-
Green wireless networks Wake-up radio Energy harvesting Routing Markov decision process Reinforcement learning 1. Introduction With 14.2 billions of connected things in 2019, over 41.6 billions expected by 2025, and a total spending on endpoints and services that will reach well over $1.1 trillion by the end of 2026, the Internet of Things (IoT) is poised to have a transformative impact on the way we live and on the way we work [1–3]. The vision of this ‘‘connected continuum’’ of objects and people, however, comes with a wide variety of challenges, especially for those IoT networks whose devices rely on some forms of depletable energy support. This has prompted research on hardware and software solutions aimed at decreasing the depen- dence of devices from ‘‘pre-packaged’’ energy provision (e.g., batteries), leading to devices capable of harvesting energy from the environment, and to networks – often called green wireless networks – whose lifetime is virtually infinite. Despite the promising advances of energy harvesting technologies, IoT devices are still doomed to run out of energy due to their inherent constraints on resources such as storage, processing and communica- tion, whose energy requirements often exceed what harvesting can provide. The communication circuitry of prevailing radio technology, especially, consumes relevant amount of energy even when in idle state, i.e., even when no transmissions or receptions occur. Even duty cycling, namely, operating with the radio in low energy consumption ∗ Corresponding author. E-mail address: koutsandria@di.uniroma1.it (G. Koutsandria). https://doi.org/10.1016/j.comcom.2020.05.046 (sleep) mode for pre-set amounts of time, has been shown to only mildly alleviate the problem of making IoT devices durable [4]. An effective answer to eliminate all possible forms of energy consumption that are not directly related to communication (e.g., idle listening) is provided by ultra low power radio triggering techniques, also known as wake-up radios [5,6]. Wake-up radio-based networks allow devices to remain in sleep mode by turning off their main radio when no communication is taking place. Devices continuously listen for a trigger on their wake-up radio, namely, for a wake-up sequence, to activate their main radio and participate to communication tasks. Therefore, devices wake up and turn their main radio on only when data communication is requested by a neighboring device. Further energy savings can be obtained by restricting the number of neighboring devices that wake up when triggered. This is obtained by allowing devices to wake up only when they receive specific wake-up sequences, which correspond to particular protocol requirements, including distance from the destina- tion, current energy status, residual energy, etc. This form of selective awakenings is called semantic addressing [7]. Use of low-power wake-up radio with semantic addressing has been shown to remarkably reduce the dominating energy costs of communication and idle listening of traditional radio networking [7–12]. This paper contributes to the research on enabling green wireless networks for long lasting IoT applications. Specifically, we introduce a ABSTRACT This paper presents G-WHARP, for Green Wake-up and HARvesting-based energy-Predictive forwarding, a wake-up radio-based forwarding strategy for wireless networks equipped with energy harvesting capabilities (green wireless networks). Following a learning-based approach, G-WHARP blends energy harvesting and wake-up radio technology to maximize energy efficiency and obtain superior network performance. Nodes autonomously decide on their forwarding availability based on a Markov Decision Process (MDP) that takes into account a variety of energy-related aspects, including the currently available energy and that harvestable in the foreseeable future. Solution of the MDP is provided by a computationally light heuristic based on a simple threshold policy, thus obtaining further computational energy savings. The performance of G-WHARP is evaluated via GreenCastalia simulations, where we accurately model wake-up radios, harvestable energy, and the computational power needed to solve the MDP. Key network and system parameters are varied, including the source of harvestable energy, the network density, wake-up radio data rate and data traffic. We also compare the performance of G-WHARP to that of two state-of-the-art data forwarding strategies, namely GreenRoutes and CTP-WUR. Results show that G-WHARP limits energy expenditures while achieving low end-to-end latency and high packet delivery ratio. Particularly, it consumes up to 34% and 59% less energy than CTP-WUR and GreenRoutes, respectively.more » « less
