在本論文中，我們提出一個無位置資訊無線感測網路自走車導航與協調演算法。在感測區域中發生事件時，我們將感測到事件發生的節點稱為待援節點(waiting-for-rescue node, WFR node)，待援節點在感測到事件的發生後，必須迅速的將事件訊息通報給網路中所有的感測節點與自走車，並且要求自走車前往做進一步的處理。在現有的導航演算法中的事件通報通常採用洪水氾濫式(flooding)的通報機制，然而這樣的通報機制容易產生過多和冗餘的通報訊息，因此我們提出一個稱為最遠節點轉送(farthest node forwarding, FNF)的高效率通報機制來通報事件的發生，並建立出以待援節點為根節點，僅包含轉送節點的展括樹(spanning tree)，同時也利用展括樹的形成來建置自走車到待援節點的路徑。FNF利用接收訊號強度來決定感測節點發送通報訊號的順序以去除大部份的冗餘事件通報訊息，達到節省電力並且延長無線感測網路生命的好處。我們也利用模擬來驗證FNF不僅可大量減少通報訊息的轉送次數，並且擁有高度的通報接收率。我們也考慮在感測區域內同時存在多個事件與多部自走車的情況，並且在導航演算法中提供自走車的協調機制，我們提出的協調機制是一個分散式處理的貪婪(Greedy)演算法，以自走車與待援節點之間的距離作為協調的根據來達到省時和省電的效果。在自走車的設計上，則透過方向性天線在不具有位置資訊的環境下，循著展括樹中的節點準確且快速地移動到待援節點。最後，經由模擬的結果驗證我們所提出的導航與協調演算法可以在無位置資訊的情況下，透過無線感測網路的導航與協調來幫助自走車順利的移動到待援節點。 In this thesis, we propose a mobile robot navigation and coordination algorithm using directional antennas in positionless wireless sensor networks. When a specific node, called waiting-for-rescue node (WFR node), detects the occurrence of an event, it broadcasts an event announcement message to the entire network for asking a mobile robot to come to help. In many existent schemes, the broadcast is achieved by the flooding scheme and thus incurs many redundant forwarding messages. We propose an energy efficient broadcast scheme called farthest node forwarding (FNF), which utilizes received signal strength for a node to determine the backoff time to forward the broadcast message. Farther nodes have shorter backoff times. And a node does not forward the message if it hears another node forwarding the message before the backoff time elapses. This can reduce a lot of redundant forwarding messages to save energy for prolonging the network lifetime. The simulation results show that FNF can not only reduce a great deal of forwarding messages but also achieve high reachability. We also utilize FNF scheme to establish a spanning tree rooted at WFR node and containing only forwarding nodes for planning paths from mobile nodes to WFR nodes. With the consideration of multiple WFR nodes and multiple mobile robots, we also develop an energy- and time-efficient mobile robot coordination scheme. The scheme is distributed and greedy-based; each WFR node selects the nearest mobile robot to ask it to come to help. In mobile robot design, we equip a directional antenna on a mobile robot for guiding it to move to the WFR node in positionless wireless sensor networks. In our simulation experiments, the sensor nodes can successfully guide the mobile robot to move towards the WFR node efficiently.
