Search for: All records

We focus on robotic sensor networks (RSNs), wherein mobile data collectors or robots are dispatched into the sensor field to collect data from the sensor nodes, and study a new algorithmic problem called battery-constrained data collection in RSNs (BC-DCR). Given an RSN of sensor nodes with varying numbers of sensory data packets to be collected and a robot with limited battery power, the goal of the BC-DCR is to dispatch the robot into the sensor field to collect the maximum number of data packets before it runs out of battery power and returns to the depot for recharging. Although extensive research has been conducted to achieve various performance objectives of data collection in RSNs, not much work has focused on the robot’s limited battery power. It is critical to consider the robot’s limited battery power to optimize the data-collecting performance of a large-scale RSN. We show that at the core of the BC-DCR is a new variation of the classic traveling salesman problem called the Budget-Constrained Traveling Salesman Problem (BC-TSP), which has not been adequately solved. We design an Integer Linear Programming (ILP)–based optimal algorithm and a time- efficient iterative greedy algorithm to solve the BC-TSP. Via extensive simulations using real measurements of battery power and mobility models of robots, we show that a) our algorithms outperform the existing work by collecting 29.1% more packets with the same battery power of the robots and b) our BC-TSP- based approach achieves 32.02% more network lifetime of the RSN compared to the existing approach. 

Service function chaining (SFC), consisting of a sequence of virtual network functions (VNFs), is the de-facto service provisioning mechanism in VNF-enabled data centers (VDCs). However, for the SFC, the dynamic and diverse virtual machine (VM) traffic must traverse a sequence of VNFs possibly installed at different locations at VDCs, resulting in prolonged network delay, redundant network traffic, and large consumption of cloud resources (e.g., bandwidth and energy). Such adverse effects of the SFC, which we refer to as SFC traffic storm, significantly impede its efficiency and practical implementation.In this paper, we solve the SFC traffic storm problem by proposing AggVNF, a framework wherein the VNFs of an SFC are implemented into one aggregate VNF while multiple instances of aggregate VNFs are available in the VDC. AggVNF adaptively allocates and migrates aggregate VNFs to optimize cloud resources in dynamic VDCs while achieving the load balance of VNFs. At the core of the AggVNF are two graph-theoretical problems that have not been adequately studied. We solve both problems by proposing optimal, approximate, and heuristic algorithms. Using real traffic patterns in Facebook data centers, we show that a) our VNF allocation algorithms yield traffic costs 56.3% smaller than the latest research using the SFC design, b) our VNF migration algorithms yield 84.2% less traffic than the latest research using the SFC design, and c) VNF migration is an effective technique in mitigating dynamic traffic in VDCs, reducing the total traffic cost by up to 24.8%.