| Abstract: | 在分散式非結構化網路中，經常使用洪水演算法(Flooding)來建立routing path。但此演算法執行時會產生大量的冗餘訊息，浪費網路資源與能量。因此，學者專家提出了RLM及RLM-T演算法來減少這一些冗餘訊息的產生，但此二演算法仍會產生許多冗餘訊息及無法保證選取最佳化路徑的問題。於是本研究提出一個兩者的改進版本，稱為植基於叢集之RLM之繞境路徑建立方式(簡稱C-RLM)，它是在一個基於事件觸發之無線感測器網?中，以RLM建立網路拓樸後，為每一節點N計算其鄰居指標Δ，Δ之定義為N和其每一直接鄰居節點擁有共同鄰居節點數量的總和。其後，由Δ值最大者開始分類每一節點，一個節點P若無其他相鄰節點之Δ值比P之Δ值大，則P為Head-node (簡稱H-node)，一個H-node周遭之相鄰節點為Member-nodes (簡稱M-nodes)，這一些M-nodes和該H-node共同組成一個cluster。其後，一個cluster中，保留M-node和H-node之連線，而隱藏M-node與M-node之間的現有連線，使成為一個以H-node為核心之星狀網路拓墣。接著，任兩cluster之間若有K條連線，K>1，則保留其中一條Δ值加總最小之連線，而隱藏其他者，目的在減少一個節點和BS建立路由路徑(routing path)時所發送及接收之RREQ封包。和洪水演算法相比，本方法可以有效地減少了無線感測器網?建立路由路徑時，所發送之多餘封包，且有效地降低了所耗費之電量、封包遺失率及點對點之封包傳送延遲時間，也提高了封包傳送之throughputs。
In a wireless sensor network, the flooding algorithm is often invoked to establish a routing path between a sensor node and the sink (base station). But this algorithm generates a lot of redundant packets, thus wasting unnecessary network resources and packet delivery energy. Researchers have then presented at least two solutions, Redundant Link Minimization (RLM for short) and Redundant Link Minimization-Triangle (RLM-T for short), to mitigate the mentioned phenomena. But both algorithms still have their own problems, e.g., many redundant packets still exist, meaning that the established routing-path can be further optimized. Therefore, in this paper, we propose an improved version, called the Cluster-based Redundant Link Minimization scheme (C-RLM for short), with which an event-driven wireless sensor network (EDWSN for short) can build a spanning tree with the sink as its root. Then each node N has a path through which N can deliver the packets it generates to the sink. So when N defects an event, it does not need to issue a routing request packet to establish a routing path. In the C-RLM, Δ of a node N, denoted by Δ_N, is defined as the cumulative number of common neighbor nodes between N and each of N’s direct neighbors. After calculating Δ_N, the node with the highest Δ value is classified as a head node, denoted by H-node. This H-node’s all direct neighbors are its member nodes, denoted by M-nodes. These M-nodes and the H-node are grouped together as a cluster. We then mark all of them as classified nodes. The unmarked node with the highest Δ value is again an H-node. All its unmarked direct neighbor nodes are its M-nodes, and these M-nodes and the H-node form another cluster, and all of them are then marked. This procedure repeats until all nodes are marked and classified into either H-nodes or M-nodes. After that, in a cluster, the link between two neighbor M-nodes is hidden. If there are at least two paths connecting two adjacent clusters, we keep the path with the lowest ??Δ, and hide the remaining paths. The purpose is reducing energy consumption during packet delivery. Experimental results show that this method can effectively improve an EDWSN’s throughputs, shorten its end-to-end delays, reduce its packet drop rates, and lower its packet delivery energy consumption. |
