行動計算環境之位置管理與交易處理

Abstract

近年來由於無線通訊及攜帶型電腦的技術進步，「行動計算」已不再是一遙不可及的夢想。然而由於無線通訊媒介的限制及使用者會移動的特性，行動計算也面臨了比以往更多的挑戰。在使用者位置管理方面，我們主要解決的是HLR為效率瓶頸 (performance bottleneck) 的問題。針對此問題，我們提出了利用複製 (replicating)及叢聚 (clustering) 的技巧，將HLR 複製並分為幾個叢聚。複製 HLR可以提高系統可靠度並減少因為查詢所產生的通話建立延遲，然而卻也同時增加了位置更新的成本。因此，我們利用叢聚的技巧，使得位置更新的成本降低。除此之外，我們也根據使用者位置管理交易 (location-management-related transaction) 的特性，提出了一套名之為 preemptive read-one-write-all 的並行控制協定。 在行動交易方面，由於無線網路的延遲時間較長，交易的執行時間也因此而拉長。交易執行時間變長的結果，導致了使用者必須跨越更多的基地台通訊區域以完成交易的執行。由於使用者在進入新的基地台通訊區域時，可能無法取得可供通訊的頻道，因此交易可能被迫終止 (forced termination)。交易被終止不僅無法完成使用者的工作，而且會浪費系統的資源。目前有關通話交遞 (handoff) 的研究都只考慮到電話的聲音服務，我們考慮了交易執行的特性，分別由個人通訊系統及並行控制協定的角度，提出幾個降低交易因通訊中斷而被迫終止之機率的方法。首先我們分析現有並行控制協定在行動計算環境中的效率，並建立一理論及系統模擬模式，以為後續研究之基礎。接著我們提出了兩個新的通話交遞機制 ¾ 有限等候佇列 (Queue-Limit scheme) 及保留頻道機制 (Guard Channel Scheme) 以降低降低交易因通訊中斷而被迫終止之機率。除此之外，我們亦提出了一個名為提早釋放鎖定 (Early-Release of Lock Protocol, ERL protocol) 的並行控制協定以縮短以鎖定為基礎的並行控制協定 (locking-based protocols) 中交易的等待時間（等待其他交易釋出鎖定）。根據我們的實驗結果顯示，有限等候佇列及保留頻道機制可以有效地降低交易因通訊中斷而被迫終止之機率；而提早釋放鎖定協定則因縮短了交易的等待時間，因此可增加交易的產出 (transaction throughput) 。

More and more information services are provided on the wireless networks. The characteristics of the wireless medium and the mobility of the mobile users new challenging problems. One of the major problems about location management is that the HLR tends to be the performance bottleneck. In our paper, we try to replicate the HLR and distribute them to the network. By this way, we can prevent the HLR from bring the performance bottleneck. However, replicating the HLR will cause extra cost since an update operation should update all the replicas. We divide the replicas of HLR into clusters to reduce the update cost. In addition, we propose a new concurrency control protocol called preemptive Read-One-Write-All protocol for location-management-related transactions. Due to long network delay of wireless links, transactions will be long-lived transactions. In such a situation, the occurrence of handoff is inevitable, and thus a wireless link held by a mobile unit crossing cell boundaries might be forced to terminate. It is undesirable that an active transaction is forced to terminate. In our paper, we first analyze the performance of conventional concurrency control protocols (two-phase locking, timestamp ordering and optimistic concurrency control) in mobile computing environments. We then propose two handoff schemes ¾ Queue-Limit scheme and Guard Channel scheme to reduce the probability of forced termination of transactions. Furthermore, we propose a new concurrency control protocol called Early-Release of Lock (ERL) protocol to alleviate the blocking effect of locking-based protocols in mobile computing environments. The experimental results reveal that the proposed handoff schemes can reduce the probability of forced termination of transactions and ERL protocol can reduce the waiting time of an active transaction and thus improve the transaction throughput.