無線感測器網路中資料收集延遲之最佳化

On Minimizing the Latency of Convergecast in Wireless Sensor Networks

賴乃倫(Nai-Luen Lai)

指導教授 ： 金仲達

國立清華大學/電機資訊學院/資訊工程學系/碩士(2007年)

摘要

感測並收集資料，是無線感測器網路(WSN)系統中最基礎的功能之一。一般在感測器網路中，通常使用單一匯集點(sink)來收集感測資料。即使系統只從每一節點收集一筆資料，但所有的資料匯集至匯集點，亦會使匯集點週遭產生大量的無線通訊，導致嚴重的干擾(interference)及碰撞(collision)。
針對於此問題的現有解決方式，是對每個節點的無線傳輸做排程(scheduling)，避開節點間可能的干擾與碰撞。但在無線傳輸的排程之前，必須先決定各個節點至匯集點的繞徑(routing)方式；現有解法中甚少提及繞徑方法對於系統收集資料效能的影響，而大多直接採用最短路徑繞徑法(shortest-path routing)。本篇論文除了探討不同繞徑方法對於系統效能的影響，並提出了一個有效的繞徑方法、以補最短路徑繞徑法之不足；此外亦善加利用繞徑方式的資訊、透改進了傳輸排程的結果。藉由共同考慮繞徑方法與傳輸排程兩方面，達到更快的資料收集速度。透過模擬實驗，也印證了我們的想法。

關鍵字

無線感測器網路 ； 繞徑 ； 排程

並列摘要

The primary function of wireless sensor networks is to sense the environment and gather data. In typical scenarios, a single sink node is used to collect data from all the sensor nodes of the network. The load of the sink will be heavy and wireless communication around the sink tends to be congested. A general strategy to solving the problem is to schedule the communications of the sensor nodes so that their radio transmissions will not interfere with each other. Assuming each sensor has a piece of sensed data to send back to the sink, the above problem becomes that of scheduling the transmission and relaying of these data in the sensor network so that the throughput is maximized. That is, all the data are sent to the sink in the shortest time subject to the radio interfere among the sensor nodes. However, to do this, we must first organize the sensor nodes into a certain transmission structure, often a tree, to relay the data back to the sink. This structure must take into account of the radio interference among the sensors and the balance of the nodes in the subtrees. In this thesis, we consider gathering-structure construction and transmission scheduling together, aiming at a more compact and efficient schedule than using simple greedy heuristics. We study how different gathering topologies affect the system throughput and propose an efficient routing algorithm for data gathering that complements the shortest-path routing algorithm. The knowledge of the gathering structure is then used to guide the graph coloring heuristic to schedule the data transmissions. The proposed schemes are evaluated and verified through simulations.

並列關鍵字

sensor network ； scheduling ； routing ； graph coloring