A 2-approximation double-tree algorithm for correlated data gathering in wireless sensor networks

Hsien Cheng Weng, Hope Chan, Eric Hsiao Kuang Wu, Gen Huey Chen

研究成果: 書貢獻/報告類型會議論文篇章同行評審

6 引文 斯高帕斯(Scopus)


In this paper, we design a novel transmission structure called a double-tree for correlated data gathering problem for wireless sensor networks, where the goal is to minimize the total transmission cost of information collected by all sensor nodes, to the sink node. It is well-known that a tree structure is often adopted for network routing problems. However, the traditional tree transmission structure for network routing may not be an optimal structure while data correlation factors are being considered. For a given wireless sensor network, some nodes send their raw data directly to the sink, and some nodes send their encoded data based on information received from other nodes; therefore, there are two types of data in the network. Without the help of decoding/re-coding at the intermediate node, the purpose of encoded data routing is to directly send to the sink, but the purpose of raw data routing is not only to send to the sink, but also to spread raw data to other nodes as side information in encoding operations. The difference from one data type makes traditional tree structure unsuitable for the correlated data gathering problem. Therefore according to our observations, we propose a new transmission double-tree structure, which uses one tree for raw data routing, and uses another tree for encoded data routing. By employing the double-tree structure, the network can achieve lower transmission cost of gathering sensing data. Furthermore the adoption of double-tree structure always outperforms the traditional tree structure in correlated data gathering problem. We first formulate the optimization problem with a double-tree transmission structure in the general case, and prove NP-Hardness of simplified version of this problem. Then we present a 2-approximation algorithm MST+ SPT that guarantees the upper bound of total transmission cost compared to the optimal solution.

主出版物標題IEEE GLOBECOM 2007 - 2007 IEEE Global Telecommunications Conference, Proceedings
出版狀態已出版 - 2007
事件50th Annual IEEE Global Telecommunications Conference, GLOBECOM 2007 - Washington, DC, United States
持續時間: 26 11月 200730 11月 2007


名字GLOBECOM - IEEE Global Telecommunications Conference


???event.eventtypes.event.conference???50th Annual IEEE Global Telecommunications Conference, GLOBECOM 2007
國家/地區United States
城市Washington, DC


深入研究「A 2-approximation double-tree algorithm for correlated data gathering in wireless sensor networks」主題。共同形成了獨特的指紋。