Energy harvesting (EH) has been recently considered as a promising solution to recharge the batteries of Wireless Rechargeable Sensors (WRS), and thus, extending the life time of networks. With such EH approach, WSR should be able to exploit the received radio frequency (RF) to harvest energy, where the sensor nodes can recharge their batteries from the wireless signal received from a charger. Recent literature has considered the cases of a fixed charger (i.e., a base station), or a mobile charger. In the case of a mobile charger, an Unmanned Aerial Vehicle (UAV) is assumed to visit the sensor nodes, transmitting the wireless signal for the recharging process, and returns back to the base station. Accordingly, The path selection for such mobile charger approach has a significant impact on the lifetime of the network. In this paper, we consider the online setting of the path selection under a special case, where the sensor nodes are deployed on the non-negative real line. Under the online settings, the sequence of sensor nodes that request charging is not known in advance. To handle these circumstances, we present an online algorithm for the path selection and mathematically prove its competitive ratio of 2. That is, the cost incurred by the online algorithm is at most twice the cost incurred by the optimal solution. The conducted simulation results confirms the proved mathematical guarantees.

This article proposes two low complexity decoders for non coherent differential space shift keying (DSSK) multiple input multiple output (MIMO) system by representing the detection problem as a hierarchical tree structure. Such presentation enables yielding the optimal maximum likelihood (ML) performance but with a massive reduction in computational complexity. Attained reduction is accomplished through 1) utilizing the error-repetitive property of DSSK detection to reduce the number of computed error terms and 2) developing two efficient searching strategies that avoid searching the entire alphabet as in ML detectors. These searching strategies enable a trade–off between performance and complexity. Unlike existing sparse recovery (SR) decoders, which require a projection phase to ensure the closure property (i.e., only single transmit antenna is active at each particular time instant and the multiplication of a constellation matrix with another one will produce a matrix from within the set), the new algorithms, inherently, maintain the closure property of DSSK system without additional procedures. Reported results reveal that optimal ML performance is obtained with a huge reduction in complexity by proper adjustment of parameters. It is also shown that the proposed algorithm performs better than state of the art SR algorithms, and the feasibility of massive MIMO configurations with low complexity is demonstrated.

Very recently, signed quadrature spatial modulation (sQSM) is developed as a competent technique that expands the spatial constellation diagram of QSM system by adding a bipolar dimension. Despite the enhanced spectral efficiency, the existing optimal maximum likelihood (ML) presents a serious computational challenge for large scale sQSM systems. Therefore, developing a reduced complexity detector for sQSM schemes is of significant importance to enable implementing and enjoying the inherent advantages of this promising system. Toward this end, a Tree Search (TS) optimal low complexity detector, calledTSopt, for sQSM Multiple Input Multiple Output (MIMO) system is proposed and analyzed in this paper. The proposed detector expands the computationally complex ML detector for sQSM into a tree-structure representation. The idea of the suggested algorithm is to employ an efficient searching strategy that can expeditiously find the branch corresponding to the minimum error without tracing the entire nodes as in the ML case. It is reported that the proposed TSopt algorithm achieves the exact error performance as ML detector but with substantial reduction in computational complexity. Besides, complexity analysis in terms of the number of visited nodes of the TSopt algorithm is analyzed and a closed-form expression for the expected complexity at high SNR values is derived. Reported results disclose agreement between simulation and expected analytical complexity with substantial gains of around 60–80% in complexity reduction for different system parameters.

In vehicular ad-hoc networks, due to high mobility, vehicles usually communicate for short periods of time with several neighboring vehicles and are required to process data fast; sometimes in the order of few milliseconds. This urgency of data processing is further heightened in safety-critical scenarios that involve many vehicles. Such scenarios require data to be prioritized and processed with minimum delay. While packet scheduling has been extensively studied, these studies focus on channel scheduling, our work focuses on processing received packets by a vehicle in dense scenarios. In this paper, we formulate the prioritized data processing problem as an integer linear program given a prior knowledge of the request sequence and prove that it is NP-complete. Due to the difficulty of predicting the traffic patterns and obtaining the request sequence in advance, we propose an online algorithm that does not require the prior knowledge of the request sequence and achieves an O(1) competitive ratio. The proposed online algorithm strives to accept higher severity packets for processing in order to maximize the cumulative severity given vehicular communications/computation capacity constraints. Using real traffic traces, we evaluate the performance of the online algorithm against three online algorithms, in which two of them use an exponentially weighted moving average-based threshold while the other one accepts requests as capacity permits. Our evaluation shows that our algorithm achieves up to 492% more cumulative severity compared to the three other baseline algorithms.

Internet of Things (IoT) applications can benefit greatly from cloud-hosted message broker services that utilize publish-subscribe communications. The operators of IoT cloud-hosted services are often interested in delivering services that maximize their revenue given quality of service guarantees. In this paper, we formulate the problem of maximizing the profit of the service provider given the prior knowledge of the request sequence as an integer linear program and prove that it is strongly NP-complete, and thus there is no fully polynomialtime approximation scheme for the problem, unless P = NP. Due to the above-mentioned problem and the difficulty of obtaining the request sequence in advance in real-world scenarios, we propose an auction-based online algorithm that does not require the prior knowledge of the request sequence. We prove that the competitive ratio of the online algorithm is (9(log(N)), where N is the number of cloud zones that host the publish- subscribe services. Moreover, we show that no online algorithm can achieve a competitive ratio better than Ω(log(N)). Therefore, our online algorithm achieves the optimal competitive ratio in the asymptotic sense. Our simulations, based on real data traces, show that our algorithm achieves up to 83% more profit compared to a heuristic approach, while consuming 60% less resources.

Since the emergence of Content Centric Networking (CCN) as a new paradigm for content delivery in the Internet, copious of research targeted the evaluation or the enhancement of CCN caching schemes. Motivated by providing the Internet Service Providers with incentives to perform caching, the increasing deployment of in-network cloudlets, and the low cost of storage devices, we study caching in CCN from an economical point of view, where the content providers pay the Internet Service Providers in exchange for caching their content items. We propose an online caching algorithm for CCN that does not require the exact knowledge of content items' popularities to minimize the total cost paid by the content providers. The total cost here is the sum of the caching costs and the retrieval costs. Our analysis shows that the proposed algorithm achieves an O(1) competitive ratio when compared to the optimal offline caching scheme that possesses the exact knowledge of content items' popularities. We also show through simulations that the proposed algorithm can cut the cost incurred by widely used caching schemes such as Leave Copy Down (LCD) and Leave Copy Everywhere (LCE) by up to 65%.

We consider joint caching, routing, and channel assignment for video delivery over coordinated small-cell cellular systems of the future Internet. We formulate the problem of maximizing the throughput of the system as a linear program, in which the number of variables is very large. To address channel interference, our formulation incorporates the conflict graph that arises when wireless links interfere with each other due to simultaneous transmission. We utilize the column generation method to solve the problem by breaking it into a restricted master subproblem that involves a select subset of variables and a collection of pricing subproblems that select the new variable to be introduced into the restricted master problem, if that leads to a better objective function value. To control the complexity of the column generation optimization further, due to the exponential number of independent sets that arise from the conflict graph, we introduce an approximation algorithm that computes a solution that is within ϵ to optimality, at much lower complexity. Our framework demonstrates considerable gains in average transmission rate at which the video data can be delivered to the users, over the state-of-the-art Femtocaching system, of up to 46%. These operational gains in system performance map to analogous gains in video application quality, thereby enhancing the user experience considerably.

Caching at the base stations brings the contents closer to the users, reduces the traffic through the backhaul links, and reduces the delay experienced by the cellular users. The cellular network operator may charge the content providers for caching their contents. Moreover, content providers may lose their users if the users are not getting their desired quality of service, such as maximum tolerable delay in Video on Demand services. In this paper, we study the collaborative caching problem for a multicell-coordinated system from the point of view of minimizing the total cost paid by the content providers. We formulate the problem as an Integer Linear Program and prove its NP-completeness. We also provide an online caching algorithm that does not require any knowledge about the contents popularities. We prove that the online algorithm achieves a competitive ratio of O(log (n)), and we show that the best competitive ratio that any online algorithm can achieve is Ω (log (n) / log log (n)). Therefore, our proposed caching algorithm is provably efficient. Through simulations, we show that our online algorithm performs very close to the optimal offline collaborative scheme, and can outperform it when contents popularities are not properly estimated.

Content caching at intermediate nodes is an effective way to optimize the operations of Computer networks, so that future requests can be served without going back to the origin of the content. Several caching techniques have been proposed in literature, including techniques that require major changes to the Internet architecture. In this work, we present a low complexity, distributed, and online caching algorithm based on content popularity. Our algorithm performs en-route caching using a simple cost-reward comparison. Therefore, it can be integrated with the current TCP/IP model. We use the concept of competitive ratio to measure the performance of any online caching algorithm, in terms of traffic savings, with respect to the performance of the optimal offline algorithm that has a complete knowledge of the future. We show that under our settings, no online algorithm can achieve a better competitive ratio than Ω(logn), where n is the number of nodes in the network. Furthermore, we show that under realistic scenarios, our algorithm has an asymptotically optimal competitive ratio in terms of the number of nodes in the network. We also study several extensions to the basic algorithm and show their effectiveness through extensive simulations.

Content caching at intermediate nodes is a very effective way to optimize the operations of Computer networks, so that future requests can be served without going back to the origin of the content. Several caching techniques have been proposed since the emergence of the concept, including techniques that require major changes to the Internet architecture such as Content Centric Networking. Few of these techniques consider providing caching incentives for the nodes or quality of service guarantees for content owners. In this work, we present a low complexity, distributed, and online algorithm for making caching decisions based on content popularity, while taking into account the aforementioned issues. Our algorithm performs en-route caching. Therefore, it can be integrated with the current TCP/IP model. In order to measure the performance of any online caching algorithm, we define the competitive ratio as the ratio of the performance of the online algorithm in terms of traffic savings to the performance of the optimal offline algorithm that has a complete knowledge of the future. We show that under our settings, no online algorithm can achieve a better competitive ratio than O(log n), where n is the number of nodes in the network. Furthermore, we show that under realistic scenarios, our algorithm has an asymptotically optimal competitive ratio in terms of the number of nodes in the network.