無線感測網路是一項新興的研究領域，其技術可廣泛應用在許多領域中，尤其是環境監測。然而，由於部署無線感測節點時的不平均，或有障礙物例如湖和山丘的存在，或感測節點的電量耗盡與被外力破壞等因素，進而造成無線感測網路中存在著空洞，而這些空洞會使許多繞徑通訊協定的效能降低。因此，如何找出這些空洞旁的邊界感測節點，並利用這些感測節點所獲得的邊界點資訊，讓封包繞徑時可事先閃避這些空洞，以及提升其他各種應用之效能，是一個相當重要的研究議題。為了解決這樣的問題，首先，我們提出一個邊界點選擇與目標偵測演算法，該演算法是在具有位置資訊的情況下，以分散式的方式，在短時間內選出位在空洞或監控區域外圍邊界上，具有座標極值之極值點，極值點將成為最初的邊界點，並用來找出剩餘之邊界點。模擬結果顯示，該演算法僅須少量的控制封包負擔，便可快速選出邊界點，且找出之邊界點個數與最佳值相當接近。然而，在某些情況下，感測節點無法取得位置資訊。因此，我們提出空洞偵測與邊界識別演算法，該演算法在無位置資訊的情況下，僅利用感測節點與鄰居感測節點間之連接狀態資訊，來挑選出邊界點。該演算法利用建立虛擬六角形地標節點，找出圍繞在空洞與感測區域旁的地標節點。再利用這些地標節點，找出正確的邊界點。模擬結果顯示，即使在低節點分支度的狀況下，該演算法正確找出邊界點的準確性仍可達到一定水準。最後，因這些邊界點的資訊，須傳送到Sink或特定的資料收集點，且資料封包須能夠避過空洞進行繞送。所以我們提出在無線感測網路中使用六角虛擬座標的繞徑協定，奠基於前一個演算法所建立的虛擬六角形地標節點，利用地標節點產生虛擬座標。傳送資料封包前，感測節點利用虛擬座標，建立從起始點到目的點的輔助繞徑路徑。資料封包將透過輔助繞徑的引導傳送，且即使多次從相同的起始點和傳送到目的點，其封包的繞徑路徑並不會固定。模擬結果顯示，該演算法能讓繞徑路徑均勻分散，而使傳送時所需承受的負擔，能均勻地分散到不同的感測節點，進而達到延長整體網路的壽命。 Wireless Sensor Network (WSN) is an emerging research filed and its technology can be widely utilized in many applications especially in environmental surveillance. However, there are exist some holes within the WSNs caused by some factors such as non-uniform deployment of sensor nodes or the existence of physical obstacle such as mountains and lakes or some sensor nodes deplete their energy or be destroyed by outside forces. These holes will degrade the performance of several routing protocols. Hence, how to discover the boundary nodes surrounding the holes and then utilize the information of boundary nodes for routing protocols to avoid holes in advance and to improve the performance of various applications is a significant research issue. In order to solve this problem, firstly, we propose the Boundary Node Selection and Target Detection protocol where each node has location information. This protocol, in short time, prior to discover some extreme nodes having extreme value of coordinates as the initial boundary nodes surrounding the holes and monitoring region in distributed manner. Then the protocol finds out other remaining boundary nodes based on these extreme nodes. The simulation results show that this protocol can cost few control packets overhead to find out boundary nodes soon and the number of selected boundary nodes comparing the optimal value is approximate. However, in some situations, the sensor nodes cannot obtain location information. Therefore, we propose the Hole Detection and Boundary Recognition protocol. This protocol can discover the boundary nodes by only utilizing the connectivity information among nodes when nodes have no location information. The protocol creates the Virtual Hexagonal Landmarks and then selects the landmarks surrounding the holes and sensing field. Based on this selected landmarks, the protocol further finds out correct boundary nodes. The simulation results show that the protocol has better performance of the accuracy ratio of selecting correct boundary nodes even in low node degrees. Eventually, the information of these boundary nodes should be transmitted to the Sink or some specific data centric nodes and the data packets can avoid the holes when transmitting. Therefore, we propose Routing with Hexagonal Virtual Coordinations protocol. Based on the Virtual Hexagonal Landmarks of previous protocol, the virtual coordination is created. Before transmitting data packets, the protocol uses this virtual coordination to create an Auxiliary Routing Path to indicate the direction of the journey from the source to the destination. When transmitting the data packets, the routing paths assisted by the Auxiliary Routing Path are not always fixed even from same source to destination. The simulation results show that the protocol can find a load balancing routing path to the destination and then prolong the network lifetime.
