etd-0728105-091340 EDI 技术论文.pdf

朝陽科技大學 資訊工程系 碩士論文 在行動裝置上監視大量移動物體之兩階段濃縮方法的研究 The Study of two phase SRM for Surveillance of Massive Moving Objects on Mobile Devices 指導教授 廖 珗 洲 博士 研 究 生 陳 文 峰 中華民國九十四年八月六日 朝陽科技大學資訊工程系 Department of Computer Science and Information Engineering Chaoyang University of Technology 碩士論文 Thesis for the Degree of Master 在行動裝置上監視大量移動物體之兩階段濃縮方法的研究 The Study of two phase SRM for Surveillance of Massive Moving Objects on Mobile Devices 指導教授 廖 珗 洲 博士 Hsien Chou Liao 研 究 生 陳 文 峰 Wen Feng Chen 中華民國九十四年八月六日 6 August 2005 I 中文摘要 近年來隨著無線網路與個人的數位助理 PDA 之普及 越來越多 PDA 有內建無線通訊功能 同時亦使得越來越多的行動資訊系統建構在 PDA上 然而建構這類系統時受到四個主要的資源限制 分別是 儲存空間 運算速 度 顯示畫面 與 網路頻寬 的不足 這導致某些系統功能的設計上需要 配合特定的方法才能符合這些限制 另一方面 隨著全球定位裝置 GPS 準確度的提升 導致將 GPS 結合到 地理資訊系統 GIS 的相關應用逐漸普及 例如衛星導航系統或車隊管理系 統等 也有許多研究著重於解決提供位置相依服務時可能遭遇的問題 因此 若是位置相關的應用要實現於 PDA 時 一個基本功能就是要能在 PDA上顯示 人員或物體的位置 當位置數量龐大並且是不斷改變時 顯示畫面 網路 頻寬 與 運算速度 將成為參個主要的問題 為了克服上述問題 在本篇論文中提出一濃縮方法稱為 two phase SRM Scale Based Reduction Method 之濃縮方法 其濃縮方法分成兩階段 第一階 段為位置濃縮 Map Reduction 主要是以顯示比例 Scale 為基礎 目的是 為了減少資料的傳輸量 而濃縮方法則依據畫面的顯示比例來決定 依據濃縮 比例來決定一個濃縮區域的大小 將同一區域內之位置資料濃縮為一單一數 II 值 藉此達成降低網路頻寬的使用量 第二階段為畫面濃縮 Screen Reduction 其主要是繼第一階段之濃縮之後再針對使用者要求之顯示品質作 進一步濃縮 目的是為了藉此加強顯示速度之提升 使濃縮比例再降低 同時 傳輸率亦隨之降低 本論文中針對兩階段之濃縮方法在群組與隨機分佈的情況下 進行資料濃 縮 並針算其濃縮率與傳輸率的結果 在第一階段中在群組分佈下的濃縮率可 以達到 82 4 而隨機分佈的情形下可以達到 94 6 傳輸率則依據濃縮比例 的不同 不管是群組或隨機分佈 最小時可以減少為 1 而在第二階段之中 則群組分佈與隨機分佈下的濃縮率皆可以達到 52 3 傳輸率則依據顯示比例 的不同 不管是群組或隨機分佈 最小時可以減少為 1 以下 另外 在第二 階段中隨著顯示品質降低 顯示時間亦隨著縮短 由此可說明本方法確實可以 針對大量移動物體的監視 運用濃縮的方法克服PDA在顯示畫面與網路頻寬 上的限制 關鍵詞 個人數位助理 無線網路 位置濃縮 III Abstract Recently the wireless network and personal digital assistant PDA is getting more and more popular It causes that the wireless communication capability becomes a built in function of PDA Many mobile information systems are also implemented on PDA However the implementation is constrained by four primary resources the storage computing speed screen size and network bandwidth It causes that some functions of systems need special designs to meet these constrains On the other hand the precision of global positioning system GPS is increased It causes that many applications provide location related services by integrating GPS and geographical information system GIS such as vehicle navigation or management Many researches are also focused on the p roblems related to location related services When these services are intent to be implemented on PDA a primitive function is the display of locations If the size of locations is massive and continuous changed the constraints on screen size and network bandwidth and computing speed become three primary problems To overcome the above problems a scale based reduction method for massive locations is proposed in this paper The SRM has two phases Zoom Phase is Map Reduction it is mainly to reduce the network transmission The origin map is split IV to a set of squares based on the selected scale The size and area of squares for reduction is determined by the scale Those locations in the same square are then reduced into a single value and thus reduce the network transmission Mosaic Phase is Screen Reduction it is mainly follow Zoom Phase to reduce the network transmission display time and reduction In this paper the two phase SRM Locations for reduction are generated based on random or group distributions The simulation results on Zoom Phase reveal that the reduction ratio can achieve 82 4 and 94 6 under group and random distribution respectively The transmission ratio is varied from the scale It can be lower to 1 for both distributions On Mosaic Phase the simulation results reveal that the reduction ratio is 52 3 under group and random distribution The transmission ratio is varied from the Screen Scale It can be lower to 1 for both distributions The result illustrates that the scale based reduction method can overcome the screen size and network bandwidth constraints for displaying massive locations on PDA Keywords PDA Wireless network Map Reduction V 誌謝 在朝陽的這些日子以來 無論在學業上或工作上 都給予我相當多的知 識 因學校環境良好 師資優良 同儕激勵 設備先進 身處在這樣的環境之 下 讓我不斷提升自已的能力 能更有自信 全因我是朝陽的一份子 我以朝 陽為榮 在學校裡 師資都相當的優良 尤其是我的指導教授廖珗洲教授 不僅專 業知識紮實 更是位認真負責且熱心的老師 在他的細心指導之下 不單是在 課業上或研究上 能給予我很大的啟發與成長 在職場上除了本職學能的提升 外亦在做人處事方面能夠更加的圓融 身處在 21 世紀的我們 不只是要 IQ 高 EQ 更要高才能在這個社會上生存 在此 向老師致上最深切的感謝 感謝口試委員張本杰教授 賈坤芳教授對於本論文不吝指教及提供了許多 寶貴的建議 使學生的碩士論文更加精進 完整 在此 致上最誠摯的感謝 對於學校裡的同學 師長 行政人員 還有一些默默在幫助我的人 可能 我無法一一知曉 但在此 我也一併獻上最誠摯的感謝 最後 我要特別感謝我的父母以及老婆 很感謝他們多年以來的栽培與支 持鼓勵 讓我能夠全心全力專注於我的研究上 使我可以很順利的完成學業 僅以此榮耀與我的家人分享 VI 目錄 中文摘要 I Abstract III 誌謝 V 目錄 VI 表目錄 VIII 圖目錄 IX 第一章 簡介 1 第二章 相關研究 4 第三章 資料濃縮方法 7 3 1 濃縮與壓縮比較 7 3 2 Two phase SRM 9 3 3 濃縮率 傳輸率及失真率之定義與計算 12 第四章 模擬系統實作 18 4 1 Zoom Phase 模擬結果展示 19 4 2 Mosaic Phase 模擬結果展示 21 第五章 實驗結果 25 5 1 Zoom Phase 之效能評估 25 5 2 Mosaic Phase 之效能評估 29 VII 5 3 伺服器之效能及負載評估 34 第六章 結論 38 參考文獻 39 VIII 表目錄 表 1 資料濃縮與資料壓縮的比較 8 表 2 不同 MS 及 SS 之計算總表 16 表 3 Pocket PC 2002下之顯示時間 31 表 4 Pocket PC 2003下之顯示時間 31 表 5 不同訂閱者數量及不同數量位置點下之濃縮時間 35 表 6 回應時間容許在 1 秒內之伺服器之負載量 36 表 7 回應時間容許在 3 秒內之伺服器之負載量 36 表 8 回應時間容許在 5 秒內之伺服器之負載量 37 IX 圖目錄 圖 1 Push系統架構圖 6 圖 2 行動裝置監視服務情形 7 圖 3 Zoom Phase與 Mosaic Phase 示意圖 9 圖 4 Zoom Phase方法示意圖 10 圖 5 Mosaic Phase 方法示意圖 11 圖 6 模擬程式功能示意圖 18 圖 7 群組分佈 MS 為 0 1 1 10 顯示結果 19 圖 8 群組分佈 MS 為 0 2 1 5 顯示結果 20 圖 9 群組分佈 MS 為 1 1 1 顯示結果 20 圖 10 位置在群組分佈下 Mosaic Phase SS 1 濃縮結果 21 圖 11 位置在群組分佈下 Mosaic Phase SS 0 7 濃縮結果 22 圖 12 位置在群組分佈下Mosaic Phase SS 0 1 濃縮結果 23 圖 13 位置在 Random分佈下 Mosaic Phase SS 1 濃縮結果 23 圖 14 位置在 Random分佈下 Mosaic Phase SS 0 4 濃縮結果 24 圖 15 位置在 Random分佈下 Mosaic Phase SS 0 1 濃縮結果 24 圖 16 Zoom Phase 群組及隨機位置分佈之濃縮率比較 26 圖 17 位置點為 10000 群組與隨機分佈之傳輸率比較 27 圖 18 不同位置數量之 AvgTRatio 比較 28 圖 19 位置點群組與隨機分佈在不同顯示品質下濃縮率比較 29 圖 20 位置點群組與隨機分佈在不同顯示品質下傳輸率比較 30 圖 21 群組與隨機分佈在不同顯示品質下所需顯示時間 Pocket PC 2002 32 圖 22 群組與隨機分佈在不同顯示品質下所需顯示時間 Pocket PC 2003 32 1 第一章 簡介 近年來隨著無線網路的發展及手持行動裝置的普及使得無線網路的應用 層面已經越來越廣 這也使得行動資訊相關應用日漸重要 然而建構這類系統 時受到四個主要的資源限制 分別是 儲存空間 運算速度 顯示畫面 與 網路頻寬 的不足 以目前最普遍的 Pocket PC 為例 內建的儲存空間最 高只有 128MB CPU 只有 400MHz 螢幕大小只有 320 240 點 而目前無線 網路以 11Mb sec 及 54Mb sec為主 這樣的頻寬仍不足以滿足現有網路上的各 種服務 這導致某些系統功能的設計上需要配合特定的方法才能符合這些限 制 另一方面 移動物體的地點能從定位裝置取得 這些裝置能分成二類 戶 外的或戶內的 全球定位裝置 GPS Global Positioning System 是最普遍的戶 外定位裝置 然而它卻不能在室內使用 有許多室內定位技術被提出 它們使 用 不 同 種 類 設 備 例 如 RFID Ultra wideband Wireless LAN Bluetooth 1 2 3 4 除此之外 有許多位置相關的研究被廣泛的討論 例如 有針對位置認知系統架構的研究 例如 S Banerjee 等人所提出的 Rover系統 架構 5 強調這個架構是可以擴充規模的 例如 一個地區有三間博物館都 在附近 藉由 Rover 系統可以提供位置相關的服務之外 一旦使用者離開某個 2 Rover 系統服務的範圍 並進入另一個博物館時 Rover 系統間具備類似基地 台的漫遊功能 可以交換需要的資訊 並且保持服務不會中斷 另外 也有研 究是著重在位置的管理 Location Management 例如 S C Lo 等人提出一個 方法來解決如何在較小的基地台範圍內具有高密度的使用者的情形下來有效 地找出一個使用者的位置 6 另外 D L Lee 等人則是針對所謂的 位置相 依資訊服務 LDIS Location Dependent Information Service 釐清許多相關研 究上的論點 7 進一步地 M Bauer 等人則是從 位置模型 Location Model 的角度出發 針對位置認知計算所需的位置相關資料提出位置模型所需的必要 條件 Augmented World Modeling Language AWML and Augmented World Querying Language AWQL 8 也有研究針對如何透過使用者的移動行為來進 行位置的查詢 以得到更準確的位置結果 9 10 11 而 S Harri 等人則是針 對位置相依的查詢 如 附近五公里內的計程車 由於這些查詢的結果通 常需要不斷地更新其位置資料 其運用代理人 Agent 的技術來增加連續性 更新上的效率 12 另外 S Prabhakar 等人的研究也是針對上述的問題提出另 一個解決方法 13 因此 若是位置相關的應用要實現於 PDA 時 一個基本的功能就是要能 顯示人員或物體的位置 然而 當位置數量龐大時 顯示畫面 網路頻寬 3 與 運算速度 將成為三個主要的問題 為了克服上述問題 在本篇論文中提出一濃縮方法稱為 two phase SRM Scale Based Reduction Method 之濃縮方法 其濃縮方法分成兩階段 第一階 段稱為 Zoom Phase 進行整個地圖的位置濃縮 Map Reduction 主要是以顯 示比例 Scale 為基礎 目的是為了減少資料的傳輸量 而濃縮方法則依據畫 面的顯示比例來決定 依據顯示比例來決定一個濃縮區域的大小 將同一區域 內之位置資料濃縮為一單一數值 藉此達成降低網路頻寬的使用量 第二階段 稱為 Mosaic Phase 進行畫面濃縮 Screen Reduction 其主要是繼第一階段之 濃縮之後再針對使用者要求之畫面品質作進一步濃縮 目的是為了藉此加強顯 示速度之提升 並且使濃縮比例再降低 同時傳輸率亦隨之降低 第二章將說明相關之研究 第三章說明資料濃縮的方法以及濃縮率與傳輸 率的定義及計算方式 第四章說明實作出來的模擬程式 第五章是實驗的結果 與討論 而第六章則是本論文的結論 4 第二章 相關研究 位置管理 Location Management 已在行動運算領域中成為一重要議 題 所謂位置管理就是如何管理移動物體 並且依據移動物體之位置提供相關 之資訊 其中Adaptive Location Management 14 是假設行動物體的歷史記錄會 影響未來之移動行為 亦證明透過Adaptive Location Management提供比廣範圍 之Static Schema Location Management更有效率之解決方法 而位置關聯式服務 Location Based Service 15 16 是隨著無線行動資訊 傳輸時代之來臨 使用者可於任何地點 任何時間 透過無線技術去取得即時 又符合使用者所在位置之相關資訊 例如旅行 或許會尋找使用者所在位置之 旅館或餐廳 其相關之價位及特色等 這就是位置關聯資料服務之目的 早期 在有線網路中使用者可能來自全世界任一地點 因此 無法根據使用者位置來 提供資訊 但在無線行動環境中 使用者位置會不斷改變 全域性之資料已不 符合使用者之需求 因此 未來區域性之位置關聯資料服務必定是無線技術應 用之發展重點 除此之外 網路資訊服務就是為了解決網路環境之限制 為使用者提供有 效的資料存取方法 降低使用者負擔 節省網路資源及系統資源之損耗 為使 用者端及資料提供端提供更有效率之資訊服務 這就是所謂的資料管理 17 5 在資料管理方法中 快取 Cache 是相當有效率之技術 其主要運用在使用 者常存取且資料本身更新頻率不高之情況下 提供查詢過資料之暫存功能 目 的是為了減少網路頻寬的成本 另外 在解決伺服器負載部份有所謂使用Push方法主要是有別於傳統Pull 方法中需由Client作Request Server再將結果Response給Client的作法 如圖1 所示 Push是透過Agent將Mobile Client之需求作事先之處理再傳給後端伺服 器 如此之架構不僅大幅減輕伺服器之負載 同時透過中介層Agent之佈署可 使得其與Mobile Client之間之網路傳輸量降低 18 19 除此之外 在網路頻寬 大小及伺服器效能會隨著訂閱者要求之資料更新頻率而改變 因此 透過An Intelligent Push System 利用ACM Adaptive Cache Management Schema可以 解決上述的問題 相對地 其架構有成本考量之缺點 6 圖 1 Push系統架構圖 行動資料源 Moving Data Source 是指在無線網路之環境中 本身會因所 在位置或時間而使其內容不斷地在作改變 自己本身是資料擷取者同時亦可能 為資料之提供者 有別於傳統固定式伺服主機 其資料庫系統是固接的 因此 若對範圍內之資料作擷取 其相關數量及內容是固定的 但是在行動資料源之 環境中 其範圍所含之資料數目及數量會隨著行動資料源之進出而改變 透過 行動資料源配合動態資料管理策略能夠有效減少網路傳輸成本 增進系統效能 20 7 第三章 資料濃縮方法 假設移動物體的位置是由行動裝置 例如Pocket PC Smart Phone Palm 等 定時發出 而位置資料透過無線網路傳送至位置伺服器儲存 行動裝置之監視 設備主要是用來觀察移動物體之位置呈現 這樣之場景如圖 1 所示 Mobile ClientLocation Server Pocket PC Smart Phone Palm 圖 2 行動裝置監視服務情形 3 1 濃縮與壓縮比較 在敘述 SRM方法之前 為了減少資料量的大小 一般最常使用的是壓縮 compress 的技術 然而壓縮過的資料傳送給接收端之後 必須進行解壓縮 decompress 的動作 也就是需要耗費額外的運算資源 特別是這樣運算資源 用於不斷更新的位置資料是無謂的浪費 原因在於為了顯示位置必須不斷地進 8 行壓縮與解壓縮的動作 除此之外 壓縮比率亦會因資料型態之不同而會有較 少可壓縮率 在表 1 中針對資料壓縮及資料濃縮分別依照 Load Scope及 Ratio 作比較 兩者之間之比較如表 1 所示 表 1 資料濃縮與資料壓縮的比較 Methods Factors Data Compression Data Reduction Load Server Client Server Scope All Partial Ratio Small Large 由表 1 中在 Load方面 資料壓縮運算分散在 Client 及 Server 端 而資料 濃縮的運算則集中在 Server 端 在 Scope方面 資料壓縮必需針對資料全部之 範圍作壓縮 而資料濃縮之處理則可針對資料之部份範圍作濃縮 在 Ratio 方 面 則資料濃縮方法比資料壓縮之方法資料量降低比率高 假設壓縮之方法在圖 2 之情況下 位置資料必須定時地在使用者端之行動 設備進行解壓縮之動作才能做到位置資訊立即呈現之效果 這種方法會使得行 動裝置之運算速度面臨極大之瓶頸 除此之外 由於行動裝置之顯示畫面是小 的 沒有必要將所有移動位置之資料作壓縮及傳輸 亦因為行動裝置之顯示畫 面較小之關係導致使用者只能針對某一部份區域之位置資料作監視 亦只有特 定部份之資料作傳輸 因此在本論文針對監視大量移動物體中提出 two phase 9 SRM Scale Based Reduction Method 滿足以上的需求 3 2 Two phase SRM 在本論文中分別依照 顯示比例 及 顯示品質 而將 two phase SRM 分 成 Zoom Phase及 Mosaic Phase 兩階段來進行 首先在 Zoom Phase中其濃縮之 方式單純是針對位置依據顯示比例所進行之地圖大小濃縮 在此稱為 地圖濃 縮 Map Reduction 而 Mosaic Phase 則針對行動裝置端在畫面上之顯示品 質來做進一步的濃縮 稱為 畫面濃縮 Screen Reduction 其示意圖如圖 3 所示 Zoom Phase Map Reduction Mosaic Phase Screen Reduction 圖 3 Zoom Phase 與 Mosaic Phase 示意圖 在圖 3 中 由下而上分別介紹 Zoom Phase 及 Mosaic Phase 之濃縮原理 10 最下方是位置在地圖上的原始資料 一個點表示實際在座標上的位置 針對 Zoom Phase 之部份 它是透過 顯示比例 來進行濃縮 因此在中間層的一 個點 可能表示下方原始地圖的一個區域 區域大小則依據顯示比例來決定 至於 Mosaic Phase 部份 它是經由 Zoom Phase 之過程再進一步針對使用者之 畫面將位置資料作進一步之濃縮 因此 中間層之好幾個點 可能相當於最上 層的一個馬賽克區域 馬賽克的顏色會依照區域中點數的多寡來決定 接著 這裡將 Zoom Phase 之方法說明如圖 4 所示 圖4 Zoom Phase方法示意圖 a Map Scale 1 1 b 原始區域 c Map Scale 1 2 假設地圖的大小為 20 20 點 然而 PDA的顯示畫面的大小為 10 10 點 因此 針對顯示比例為 1 1 的情況下 一個畫面只能顯示四分之一的地圖 如 圖 3 b 的藍色框線所顯示的大小 黑色的點如圖 4 a 代表傳輸之位置資料 這 時畫面所顯示某個人員或物體的位置與實際位置完全符合 一旦顯示比例調整 為 1 2 的時候 原圖將縮小為原來的四分之一 這時畫面就可以完整顯示整個 11 地圖的內容 如圖 4 c 所顯示的灰色區域 這時圖 4 c 中的一個格子相當於圖 4 b 中的四個格子 也就如同我們在圖 4 b 中以紅線所表示的狀況 因此 使 用者可以調整顯示比例來決定是要看整張地圖或者地圖的某四分之一部份 而 且當使用者只看某四分之一的畫面時 我們只需要傳送四分之一的位置資料到 接收端即可 圖 5 Mosaic Phase 方法示意圖 a b Screen Scale 1 c Screen Scale 1 2 在圖 5 中 5 a 為 Screen Scale 為 1 時假設顯示畫面的大小為 10 10 點 因此 針對 Screen Scale 1 2 的情況下 5 a 中每四個方格將在 5 b 中濃縮成一 個相同區域的方格 經Mosaic Phase 後如 5 c 所示 同時在 5 c 中亦針對方格 內位置數量之多寡給予不同深淺之顏色表示 資料傳輸量由 5 a 之黑色區域之 傳輸量減少為 5 c 之灰階區域所框區域之傳輸量 達到進一步資料之濃縮效 果 根據以上之方法 使用者可自行調整本身想要監視之範圍及畫面品質 而 伺服器就針對這二參數進行 two phase SRM 之運算 然後將其結果經由無線網 12 路傳送至行動裝置上 如此行動裝置只負責位置資訊之呈現 而不需要其它額 外之運算 接著說明為了評估 two phase SRM 之效能 所定義的位置資料 濃 縮率 RRatio 與 傳輸率 TRatio 3 3 濃縮率 傳輸率及失真率之定義與計算 濃縮率 是經過濃縮方法後佔所有資料量的比率 而 傳輸率 則是經 過濃縮方法後佔所有資料量的傳輸比率 在本論文中針對濃縮率及傳輸率分別 針對 Zoom Phase及 Mosaic Phase 二個階段加以定義 特別說明的是 在 Zoom Phase 中 單純是針對位置由行動裝置端控制欲監視之比例所進行之位置資料 濃縮 而傳輸率則是經過濃縮方法後佔所有資料量的比率 背景地圖 Maps 或是標示 Labels 應該被傳送至行動裝置以配合作監視之目的 然而這些資 料大小是固定的 只需傳送一次即可 因此這部份之資料就不列入 濃縮率 與 傳輸率 之計算中 假設地圖是正方形的 寬度為 W 螢幕大小為 SW 地圖顯示比率 Map Scale 為 MS 螢幕顯示品質 Screen Scale 為 SS 假設地圖顯示比例為 1 1 時 MS 等於 1 比例 1 2 時 MS 等於 0 5 螢幕顯示品質為 1 時 SS 等於 1 螢幕 顯示品質為 1 2 時 SS 等於 0 5 i L表示某個位置 而 xi yi 表示 i L的位置座標 一個位置座標由 N bytes 所組成 一個移動物體是由 M bytes 組成 在顯示比 13 率 MS 下 螢幕顯示品質為 SS 下 i L的位置座標經以下之定義被轉換成 i L SSMSyySSMSxxyxL iiiiiii where 1 在公式 2 中 W表示寬度W在顯示比率 MS 下 螢幕顯示品質為 SS 下之定 義如下 SSMSWW 2 由 i L乘以顯示比率 MS 所產生 計算濃縮率之前 會先計算在某個顯示比 例之下有位置資料量 其資料量之計算方式定義如下 11 otherwise 0 1 when and where ofNumber W m W n mnSSMS mnmn mn iiimn BTotal CountCountMN B nymxLCount 3 在公式 3 中 i L位置點數量等於在顯示比例下 m n 位置座標下之位置數 量稱為 mn Count mn B 代表在 m n 點資料數量 bytes 當 mn Count大於等於 1 時 M 代表每一移動物體之識別資料 因此在 m n 的總資料量為 mn CountM N 代表 m n 位置座標資料 因此 mn B 值等於 mn CountMN 當 mn Count為 0 時 mn B 值亦為 0 SSMS Total則表示在顯示比例為 MS 顯示品質為 SS 濃縮後 之資料量 SSMS RRatio 表示在顯示比例為 MS 顯示品質為 SS 下之濃縮率 14 其值是由 SSMS Total除以原來區域範圍內總資料量 1 Total 它的定義如下 LSMN Total Total Total RRatio SSMSSSMS SSMS 1 1 4 接著 使用者端可監視之區域影響傳輸資料量大小 而每一個使用者所監 視位置之位置點數量有多有寡 因此 我們定義三種類型之傳輸率 分別為最 大傳輸率 MaxTRatio 最小傳輸率 MinTRatio 及平均傳輸率 AvgTRatio 它們 的運算式定義如下 2 1 1 1 1 1 1 11 1 11 11 11 1 1 SSSWW jiTRatio AvgTRatio SSSWWnSSSWWm nmTRatioMininumMinTRatio SSSWWnSSSWWm nmTRatioMaximumMaxTRatio Total B nmTRatio SWW i SWW j SSMS SSMS SSMSSSMS SSSMS SWm mi SWn nj ij SSMS 5 在公式 5 中 nmTRatio SSMS 表示從 m n 的左上角算起之傳輸率 它的值 是由 Bij 除 1 Total而得 SSMS MaxTRatio 和 SSMS MinTRatio表示在 nmTRatio SSMS 之最大值及最小值 而 SSMS AvgTRatio表示 nmTRatio SSMS 之平均值 除此之外 在考慮其失真率 DRatio 方面 在 Zoom Phase中是以顯示比例 為資料之濃縮原則 因此沒有失真 Distortion 之問題產生 而在 Mosaic Phase 15 中則是以顯示品質作為濃縮原則 因此在這方面就有失真之情形產生 因此失 真率為則是經過 Mosaic Phase 濃縮方法後平均傳輸資料量佔原有顯示品質 SS 1 平均傳輸資料量的比率 其運算式作定義如下 1 1 MS SSMS SSMS AvgTRatio AvgTRatio DRatio 6 以圖 3 及圖 5 為例 區域之寬度 W為 20 螢幕之寬度 SW 為 10 MS 值 分別為 1或 0 5 SS 為 1 或 0 5 假設位置座標值 N 配置 2 bytes 每個移動物 體之識別資料 M配置 2 bytes LS 值為 11 RRatio 和 TRatio之運算如下 5 30 100 11 9 36 1 9 100 44 4 1 59 100 44 26 50 100 44 22 2 1 1 59 100 44 26 1 1 9 90 9 90 100 11 22 2 222 7 22 1 1 100 100 11 22 11 22 9 90 100 11 22 2 222 7 22 2 1 1 1 1 1 1 1 1 1 1 1 5 0 1 5 0 1 5 0 1 5 0 1 1 1 1 1 1 1 1 1 5 0 1 5 0 AvgTRatio MinTRatio MaxTRatio TRatio TRatio AvgTRatioMinTRatioMaxTRatio TRatio Total Total RRatio Total Total RRatio 7 16 2 30 100 5 30 3 21 1 0 1001 3 21 100 6 67 7 1 9 100 44 4 50 100 44 22 3 36 100 44 16 2 1 50 100 44 22 1 1 6 63 6 63 100 11 22 322 1 222 522 1 22 1 1 9 90 100 11 22 2 222 7 22 6 63 100 11 22 322 1 222 522 1 22 5 0 1 1 1 2 5 0 1 5 0 1 5 0 1 5 0 1 5 0 1 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 1 1 5 0 1 5 0 1 1 1 1 5 0 5 0 5 0 DRatio DRatio AvgTRatio MinTRatio MaxTRatio TRatio TRatio AvgTRatioMinTRatioMaxTRatio TRatio Total Total RRatio Total Total RRatio 8 表 2 不同 MS 及 SS 之計算總表 RRatio MinTRatio AvgTRatio MaxTRatio MS SS 1 0 5 1 0 5 1 0 5 1 0 5 1 100 90 9 9 1 90 9 30 5 90 9 59 1 90 9 0 5 90 9 63 6 9 1 63 6 21 3 63 6 50 63 6 註 單位 百分比 從以上結果中可以發現如表 2 所示 當 SS 等於 1 MS 為 1 時 1 1 RRatio 是 100 且 1 1 AvgTRatio是 30 5 如此結果意謂的是當 MS 值為 1 時 顯然沒 17 有任何之濃縮 其平均之傳輸量卻因可見區域縮小導致只有原資料量的 1 3 左 右 另外一方面 當 MS 等於 0 5時 在 SRM 下只有減少 9 為所有資料量 的 90 9 因為所有資料必須被傳送至行動使用者端 所以 1 5 0 MaxTRatio值亦 為 90 9 1 1 DRatio值為 0 當 SS 等於 0 5 時 MS 為 1 時 5 0 1 RRatio 是 90 9 且 5 0 1 AvgTRatio是 21 3 如此結果意謂的是當 MS 值為 1 時 在 Mosaic Phase下顯然濃縮率及 傳輸率皆比 Zoom Phase 的 1 1 RRatio為 100 及 1 1 TRRatio為 30 5 為低 另外一 方面 當 MS 等於 0 5 時 在 SRM 下減少 36 4 為所有資料量的 63 6 因為所有資料必須被傳送至行動使用者端 所以 05 5 0 MaxTRatio值亦為 63 6 5 0 1 DRatio值為 30 2 18 第四章 模擬系統實作 在本章節中首先介紹模擬系統之環境 我們利用 Visual Basic NET 實作一 個運用 two phase SRM 的模擬系統 這裡預設的地圖大小為 2000米 2000米 行動裝置 Pocket PC 的顯示畫面大小設定為 200 200 程式會在地圖的範圍內 分別設定任意個位置 而這些位置的分佈可以採 Random 及 Group 方式來決 定 相關功能之示意圖如圖 6所示 圖 6 模擬程式功能示意圖 Reset Zoom In Zoom Out Group 分佈 螢幕顯示品質調整 螢幕顯示品質參數SS 地圖顯示比例參數MS Random分佈 19 4 1 Zoom Phase 模擬結果展示 以下用幾個畫面來說明在 Zoom Phase模擬程式下的執行結果 圖 7 群組分佈 MS 為 0 1 1 10 顯示結果 這裡先將 SS 固定為 1 表示在 Mosaic Phase中沒有任何濃縮的動作 以 瞭解 Map Phase 的過程 當 MS 為 0 1時 在 Pocket PC 之畫面顯示如圖 7 所 示 Pocket PC 之畫面位置資料是透過群組方式產生 使用者可透過畫面上之 Zoom In 或 Zoom Out 按鈕來調整 MS 值 當 MS 值調整為 0 2 時 畫面上之 顯示結果如圖 8 所表示 在圖 9 中 調整 MS 值為 1 相關之位置點分佈情況 精確地展示出來 20 圖 8 群組分佈 MS 為 0 2 1 5 顯示結果 圖 9 群組分佈 MS 為 1 1 1 顯示結果 根據以上之展示 可以容易瞭解 Zoom Phase在資料濃縮上的運作過程 21 4 2 Mosaic Phase 模擬結果展示 在 Mosaic Phase 模擬實驗中 除了有 Zoom Phase 之 Zoom In 或 Zoom Out 參數值 MS 外還增加螢幕顯示品質之參數 SS 在Mosaic Phase 模擬實驗 中 SS 共分成四個等級 分別為 SS 0 1 0 4 0 7 及 1 由於 SS 愈小 馬賽 克情形會較為嚴重 但顯示速度愈快 因此在操作畫面上提供 Quality及 Speed 的選項供使用者選擇 而 SS 1 則為原來 Zoom Phase 之品質 以下用幾個畫面 來說明在 Mosaic Phase Pocket PC在不同的顯示比例下模擬程式的執行結果 圖 10 位置在群組分佈下Mosaic Phase SS 1 濃縮結果 在 Mosaic Phase 實驗中 當 MS 值為 0 1 時 位置點為群組分佈且顯示 品質為最佳 SS 1 之條件下在 Pocket PC 之畫面顯示如圖 10 所示 這個畫面和 圖 7 是相同的 當 SS 值調整為 0 7 時 Pocket PC 之畫面位置如圖 11 所示 22 由圖 11 中可看出其顯示品質比圖 10 低 主要是因為顯示品質之參數調整之 後 在相同之 Scale 下之位置資料會再進行進一步之資料濃縮所致 但是 隨 著顯示品質之下降 相對地 顯示速度可以因而提升 在圖 12 中 則是進一 步調整顯示品質 SS 值為 0 1 之後所展示出之結果 其顯示品質比圖 11 更低 圖 11 位置在群組分佈下 Mosaic Phase SS 0 7 濃縮結果 23 圖 12 位置在群組分佈下Mosaic Phase SS 0 1 濃縮結果 底下則是選擇 Random 分佈時 在不同 SS 下模擬程式的執行結果 如圖 13 14 和圖 15 所示 圖 13 位置在 Random 分佈下 Mosaic Phase SS 1 濃縮結果 24 圖 14 位置在 Random分佈下 Mosaic Phase SS 0 4 濃縮結果 圖 15 位置在 Random分佈下 Mosaic Phase SS 0 1 濃縮結果 25 第五章 實驗結果 本章將說明針對 two phase SRM 所設計的實驗以評估 SRM 之效能 實驗 相關之參數及設定如下 原始區域 2000 meters 2000 meters 螢幕大小 200 pixels 200 pixels 位置數量分別為 1000 4000 7000 及 10000 MS 0 1 0 2 1 SS 0 1 1 分別代表行動裝置使用者要求之不同顯示品質 1 最 高 0 1 最低 位置之分佈 分為隨機分佈及群組分佈 N 每個集合位置座標佔 2 bytes M 每個移動物體相關識別資料佔 2 bytes 下面將分別針對 Zoom Phase 及 Mosaic Phase 中之效能來進行評估 5 1 Zoom Phase 之效能評估 此模擬工具產生八組不同的位置集合 分別計算在不同之 MS 下每一部位 之 RRatio及 TRatio 其中 RRatio之結果如圖 16 所示 26 Map Scale 1 00 90 80 70 60 50 40 30 20 1 Reduction Ratio RRatio 100 95 90 85 80 75 70 Group 1 000 Group 4 000 Group 7 000 Group 10 000 Random 1 000 Random 4 000 Random 7 000 Random 10 000 圖 16 Zoom Phase 群組及隨機位置分佈之濃縮率比較 在圖 16 中 X 軸表示 MS 值範圍由 0 1 至 1 Y 軸表示濃縮率 而分別使 用四條不同曲線來代表在位置點在群組分佈及隨機分佈下 1000 4000 7000 及 10000個位置之濃縮率 從圖中可知 隨著 MS 值增加濃縮率亦隨著增加 群 組分佈之濃縮率大約比隨機分佈之濃縮率低 10 至 15 這意謂的是在 SRM 方法針對位置點的分佈較集中時 則能得到較佳的濃縮率 在這四條曲線中都 是呈現相同之趨勢 另外 由黑色曲線中可發現 在隨機分佈下其濃縮率不受 位置點之多寡影響 相對地 在群組分佈下 越多的位置點其濃縮率越低 最 小之濃縮率在群組分佈下 MS 為 0 1 且位置點為 10000個大約是 80 6 因此 資料量可以減少五分之一 27 Map Scale 10 90 80 70 60 50 40 30 20 1 Transmission Ratio TRatio 100 90 80 70 60 50 40 30 20 10 0 Group Avg Group Max Group Min Random Avg Random Max Random Min 圖 17 位置點為 10000 群組與隨機分佈之傳輸率比較 傳輸率之運算結果如圖 17 所示 三條曲線分別代表平均 最大傳輸率及 最小傳輸率在 10000 個位置點分別以群組及隨機方式分佈之情形 由圖 17 中 很明顯地當 MS 值增加時 傳輸率呈現快速下降 就隨機分佈而言 MinTRatio 和 MaxTRatio之間之差異是非常小的 而在群組分佈這部份則 AvgTRatio是接 近隨機分佈之曲線 而 MaxTRatio 是高於 AvgTRatio 大約 5 至 13 這表示 說只要位置較集中時 傳輸率 TRatio 差異較大 由圖 17 中可觀察到 MaxTRatio AvgTRatio及 MinTRatio 之最小值分別為 6 2 1 2 及 0 這充 份顯示 SRM 在 Zoom Phase 具有使傳輸率快速下降之優點 除此之外 行動位置點之多寡對平均傳輸率之影響亦在