在現今多樣式的無線網路應用中，為了要達到多重連接，節點佈建的方式扮演了很重要的角色。然而，現有的方法在尋找k連接數的時候，並沒有提供一個有系統性的方法來尋找出最佳化的佈建圖形。 在這篇論文中，我們假設節點都是相同的，並且以對稱的形式擺放。結果顯示當我們以這種方式擺放的時候，節點的范諾圖(Voronoi diagram)會是三個regular tessellations的其中一種。基於這點想法，我們設計了一套搜尋的演算法，叫做Pruning and Search(PS) 來尋最佳化的k連接佈建圖形。我們的演算法是第一個採用系統性的方法來尋找最佳化的k連接佈建圖形。雖然PS的時間複雜度是指數型，但最佳化的圖型可以預先尋找出來。除此之外，我們可以透過PS跟RES兩個演算法的結合，來找到k連接以及L覆蓋的佈建圖形。 ;The strategy for sensor node deployment to achieve multiple connectivity plays a critical role in various applications of wireless sensor networks. However, the existing solutions to identify optimal k-connectivity deployment patterns are heuristic in the sense that they do not provide a systematic approach to identify the optimal pattern for a given k value. In this paper, we assume that nodes are homogeneous and deployed to the ground symmetrically. As a result, the Voronoi diagram of wireless nodes will be one of the known three regular tessellations. Based on this idea, we design an intuitive searching algorithm, called Pruning and Search (PS), to identify the optimal k-connectivity deployment pattern for an arbitrary k value. To the best of our knowledge, our PS algorithm is the first one to do this task in a systematical approach. While the time complexity of the algorithm is exponential, the optimal pattern can be pre-computed offline in advance. In addition, PS can be easily combined with the RES algorithm so that the optimal k-connectivity and l-coverage deployment pattern for a given set of k and l values can be found.
