ترغب بنشر مسار تعليمي؟ اضغط هنا

On the Construction of Data Aggregation Tree with Minimum Energy Cost in Wireless Sensor Networks: NP-Completeness and Approximation Algorithms

213   0   0.0 ( 0 )
 نشر من قبل Tung-Wei Kuo
 تاريخ النشر 2014
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

In many applications, it is a basic operation for the sink to periodically collect reports from all sensors. Since the data gathering process usually proceeds for many rounds, it is important to collect these data efficiently, that is, to reduce the energy cost of data transmission. Under such applications, a tree is usually adopted as the routing structure to save the computation costs for maintaining the routing tables of sensors. In this paper, we work on the problem of constructing a data aggregation tree that minimizes the total energy cost of data transmission in a wireless sensor network. In addition, we also address such a problem in the wireless sensor network where relay nodes exist. We show these two problems are NP-complete, and propose O(1)-approximation algorithms for each of them. Simulations show that the proposed algorithms each have good performance in terms of the energy cost.



قيم البحث

اقرأ أيضاً

Recently, many researchers have studied efficiently gathering data in wireless sensor networks to minimize the total energy consumption when a fixed number of data are allowed to be aggregated into one packet. However, minimizing the total energy con sumption does not imply the network lifetime is maximized. In this paper, we study the problem of scheduling data aggregation trees working for different time periods to maximize the network lifetime when a fixed number of data are allowed to be aggregated into one packet. In addition, we propose a heuristic to balance the lifetime of nodes in data aggregation trees such that the network lifetime is maximized. Simulation results show that the proposed heuristic provides a good performance.
147 - Qiao Li , Yifei Wei , Mei Song 2016
An energy cooperation policy for energy harvesting wireless sensor networks (WSNs) with wireless power transfer is proposed in this paper to balance the energy at each sensor node and increase the total energy utilization ratio of the whole WSNs. Con sidering the unbalanced spatio-temporal properties of the energy supply across the deployment terrain of energy harvesting WSNs and the dynamic traffic load at each sensor node, the energy cooperation problem among sensor nodes is decomposed into two steps: the local energy storage at each sensor node based on its traffic load to meet its own needs; within the energy storage procedure sensor nodes with excess energy transmit a part of their energy to nodes with energy shortage through the energy trading. Inventory theory and game theory are respectively applied to solving the local energy storage problem at each sensor node and the energy trading problem among multiple sensor nodes. Numerical results show that compared with the static energy cooperation method without energy trading, the Stackelberg Model based Game we design in this paper can significantly improve the trading volume of energy thereby increasing the utilization ratio of the harvested energy which is unevenly distributed in the WSNs.
Data aggregation in wireless sensor networks refers to acquiring the sensed data from the sensors to the gateway node. It reduces the amount of power consumed during data transmission between the sensor nodes. Generally homomorphic encryptions have b een applied to conceal communication during aggregation. Since enciphered data can be aggregated algebraically without decryption. Here adversaries are able to forge aggregated results by compromising them. However, these schemes are not satisfying multi-application environments, provide insecure transmission and do not provide secure counting for unauthorized aggregation attacks. In this paper, we propose a new concealed data aggregation scheme extended from homomorphic privacy encryption system. The proposed scheme designed for a multi-application environment, mitigates the impact of compromising attacks in single application environments and also it can avoid the damage from unauthorized aggregations by the privacy homomorphic encryption scheme.
We propose an algorithm which produces a randomized strategy reaching optimal data propagation in wireless sensor networks (WSN).In [6] and [8], an energy balanced solution is sought using an approximation algorithm. Our algorithm improves by (a) whe n an energy-balanced solution does not exist, it still finds an optimal solution (whereas previous algorithms did not consider this case and provide no useful solution) (b) instead of being an approximation algorithm, it finds the exact solution in one pass. We also provide a rigorous proof of the optimality of our solution.
Wireless sensor networks (WSNs) have great practical importance for surveillance systems to perform monitoring by acquiring and sending information on any intrusion in a secured area. Requirement of very little human intervention is one of the most d esirable features of WSNs, thus making it a cheaper and safer alternative for securing large areas such as international borders. Jamming attacks in WSNs can be applied to disrupt communications among the sensor nodes in the network. Since it is difficult to prevent jamming attacks, detection and mapping out the jammed regions is critical to overcome this problem. In a security monitoring scenario, the network operators will be able to take proper measures against jamming once the jammed regions in the network are known to them. It is also desirable to keep the interactions of the sensor nodes in the network minimal, as they are low powered devices and need to conserve their resources. In this paper we propose a light-weight technique for faster mapping of the jammed regions. We minimize the load on the sensors by removing the actual responsibility of mapping from the network to the central base station (BS). After a few nodes report to the BS, it carries out the task of mapping of the jammed regions in the network. We use our simulation results to compare our proposed system with the existing techniques and also to measure the performance of our system. Our results show that the jammed regions in a network can be mapped from fewer nodes reporting to the base station.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا