考量能源效益與傳輸量之無線感測網路中繼點佈建方式

On Energy-Efficient Traffic-Aware Deployment of a Wireless Sensor Network

高志偉(Chi-Wai Kou)

指導教授 ： 曾煜棋

國立交通大學/資訊學院/網路工程研究所/碩士(2010年)

https://doi.org/10.6842/NCTU.2010.00567

摘要

在無線感測器網路中，由於感測器是依靠電池的電力維持的，因此，怎樣去減少耗電而延長無線
感測器網路的壽命成為很多人研究的議題之一。而在眾多延長網路壽命的研究中，有一種方法叫做``中繼點佈建''
，我們可以透過佈建中繼點來減少感測器之間的通訊範圍，而因為感測器的耗電與它的通訊範圍成正比，由此，
我們可以使用中繼點來延長網路的壽命。而在早期的中繼點佈建研究中，大部份的研究人員都關注在研究於
同種類或不同種類的感測器網路上，他們怎樣才能用最少數量的中繼點來使得網路達到連結性和存活性的需求
。除此之外，某些研究人員開始察覺得當他們要在網路上佈建中繼點的時候，他們應該要同時考慮到網路流量
的大小。而在某一篇考慮中繼點佈建的研究中，他們在佈建中繼點的時候，他們會同時考慮到網路流量的大小，
並且顧及到網路的連結性而達到真實網路的考量。可是，我們發現這篇研究當中存在某些缺點，這是因為他們的
網路拓樸是由Steiner tree建成的，而當中的Steiner tree是一種方法可保證用最短的距離把整個網路連起來。

因此，在這篇研究裏，首先，我們會介紹為什麼建Steiner tree作為有考慮流量大小的網路拓樸會產生問題。接下來，我們會針對在考慮網路流量大小的網路拓樸中進行
中繼點佈建的這個問題上，提出一個``權重移動演算法''來解決這個問題，而這個演算法我們是透過非線性規
劃(NLP)來處理。可是，因為非線性規劃不能保證程式可以在多項式時間下結束，所以我們另外提出了兩個啟發式方法來處理這個佈建的問題。最後，在我們的模擬結果中，我們會呈現我們提出的方法以及以前在中繼點佈建中提出的方法的數據。當中，我們察覺到我們的方法一定比以前的方法來得省電，因此網路的壽命也相對的比較長，而且我們的方法的改進效果在不同的情況下都可以維持在一個很好的範圍內。

關鍵字

省電 ； 中繼點佈建 ； 考慮流量 ； 無線通訊 ； 無線感測器網路

並列摘要

There are many different kinds of studies discussing how to achieve extending lifetime on sensor network. Among them, relay nodes deployment is a way to enlarge lifetime by reducing the communication range of sensor nodes. And in the early studies, they are usually concerned with placing minimum number of relay nodes into homogeneous or heterogeneous WSNs to meet certain connectivity and survivability requirements. However, some researchers start to consider the traffic volume in the network when they deploy relay nodes. And there is a study which the relay node deployment is related to the traffic volume and ensures the network connectivity. But, we have found some drawbacks on it since its network topology is based on Steiner tree, which can guarantee to connect the network with the minimum distance.

In this paper, we will first explain the problems about constructing Steiner tree as traffic-aware network topology. Then, we will propose a weighted moving algorithm using non-linear programming (NLP) to solve this traffic-aware relay node deployment problem. Since NLP can not guarantee to terminate in polynomial time, we also propose two heuristic approaches to solve this traffic-aware relay node deployment problem. In our simulation results, we have shown that both of our approaches must consume less energy than previous studies and obtain a pretty good improvement.

並列關鍵字

energy efficient ； relay node deployment ； traffic-aware ； wireless communication ； wireless sensor network

參考文獻

[3] D. Braginsky and D. Estrin. Rumor routing algorithm for sensor networks. In Proc. of

ACM Int’l Workshop on Wireless Sensor Networks and Applications (WSNA), 2002.

[5] E. K. P. Chong and S. H. Zak. An Introduction to Optimization, 2nd Edition. Wiley, 2001.

[7] G. Lin and G. Xue. Steiner tree problem with minimum number of steiner points and

bounded edge-length. Information Processing Letters, 69:53–57, 1999.