# 臺灣博碩士論文加值系統

(98.81.32.131) 您好！臺灣時間：2024/08/07 20:44

:::

### 詳目顯示

:

• 被引用:0
• 點閱:161
• 評分:
• 下載:2
• 書目收藏:0
 從感知無線網路中的兩個次要用戶在公用控制通道設定的技術當中獲得啟發，我們考慮在一個有限且相連的無向圖中的兩個使用者的交會搜索問題。在我們的題目中，兩個使用者對於圖上的節點與邊的標示皆相同。時間劃分成時槽，並且兩個使用者的時間並不同步。每個使用者有一個子圖做為其移動範圍，且只有該使用者自己知道。在每個時槽中，每個使用者可以沿著其在子圖中的邊移動到相鄰的節點，或是停留在現在的節點上。若兩個使用者在同一個時槽時停留在同一個節點，我們就將其稱作交會，而在交會前所經過的時槽個數，我們稱作為交會時間 (time-to-rendezvous, TTR)。當兩個使用者的子圖交集不為空集合時，我們提出了數個確定性的交會演算法來限制其最大交會時間 (maximum TTR, MTTR)，特別是我們證明對於任意有 N 個節點的圖，其最大交會時間將可以被限制在 O(N2log N) 內。而對於特殊拓樸的圖形，如線圖、環以及樹等，其最大交會時間將可以被限制在 O(N)。我們的研究結果也可以延伸至局部標示的圖且使用者有不同的 ID 的情況。在使用者有 LbitsID 的情況下，我們證明在任意的有 N 節點的圖上最大交會時間可以被限制在 O(N2L)，在樹與環上則可將最大交會時間限制在 O(NL)。
 Motivated by the need to set up a common control channel between two secondary users in a cognitive radio network, we consider the two-user rendezvous search problem in a finite, connected and undirected graph. The labels of nodes and edges in the graph are the same for the two users. Time is partitioned into time slots and the clocks of the two users are not synchronized. Each user is assigned with a subgraph that is only known to itself. In everytime slot, a user can either move along an edge in its subgraph from its current node to another neighboring node or stay in its current node. Two users rendezvous when they are at the same node at the same time. The number of time slots needed for the two users to rendezvous is called the time-to-rendezvous (TTR). As long as the intersection of the two subgraphs is not empty, we propose various deterministic rendezvous algorithms to bound the maximum TTR (MTTR). In particular, we show that the MTTR can be bounded within O(N2log N) time slots for any arbitrary graph with N nodes. For special graphs, including line graphs, rings and trees, the MTTR bounds can be further reduced to O(N). Our results can also be extended to locally labelled graphs with distinct IDs. In that setting, we show the MTTR bounds are O(N2L) for general graphs and O(NL) for trees and rings, where L is the number of bits of an ID.
 Contents 1List of Figures 3List of Tables 41 Introduction 52 General graphs 102.1 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.2 The homogeneous setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.3 The heterogeneous and asymmetric setting . . . . . . . . . . . . . . . . . . . . 122.4 The heterogeneous and symmetric setting . . . . . . . . . . . . . . . . . . . . 153 Special graphs 203.1 Line graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.2 Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.3 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 Locally labelled graphs with distinct user IDs 344.1 Locally labelled trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.2 Locally labelled rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395 Conclusion 41