TW201217751A - Method and apparatus for determine real-time travel time of a road based on mobile communication network - Google Patents

Description

201217751 六、發明說明： 【發明所屬之技術領域】 本發明係關於道路交通管理與行動通信科技之領 域，特定言《，係相關於藉決定具有行動通信網路之道 路的即時行程時間，而監視道路交通的科技。 【先前技術】 在道路交通管理與導航系統中，道路交通監視為— 個重要的課題。交通監視可被用以產生道路交通的基本 資訊，諸如載具的平均速度、道路的行程時間、道路擁 塞程度、以及事故位署楚；# 位置等等。猎由提供即時基本資訊， 導航系統可即時學習；首& > 山& 路父通狀態，且合理地安排載具 的駕駛路徑’從而有效率士沾 力双早地減；擁塞並避免碰撞。 對於監視道路φ補， ήη. „ 般的解決辦法，諸如基於交 通感測器（如電感性迴圈侦 貝利益）及全球定位系統（Gpy 游動車輛（floating e㈣’如具有邮的計程車）已被應用 至都會區道路。然而，該解決辦法尚未被應用至遼闊的 郊區道路與城市間道路。 要因為：（1)交通感測器的部 署與維護昂貴，且 不適於郊區部署；（2)基於GPS游動車 輛的解決辦法非常依賴 — 很又孤視道路上游動車輛的數量， 且事貫上，在邓區道路盘;古卩9 .. 市間道路上行驶的游動車柄 201217751 數量很少。 古2G/3 G行動通信網路的行動通信網路已 在許多國家中涵蓋九成以上的區域，且七成以上的人每 天使用行動電話。當發生通信行為時，諸如發送/接收簡 訊、啟動/接收通話、或在—通信期期間執行交遞 (。術）網路會記錄當下提供對應服務之基地台的 位置目此’亦可考慮以行動通信網路監視道路交通。 在見存的基於行動通信網路以監視道路交通的解決 辦法中’可於行動使用者在受監視道路上發出兩通信行 為時D己錄位置貢訊與兩連續通信事件之時間，以計算 行動使用者的移動速度，從而可評估受監視道路的交通 狀態。然而’此解決辦法依賴發生在受監視道路上的通 "ί吕事件的數量，且其危、s >古 …通#事件發生在受監視道路上則 無法作用。 此外，因為在長時間區間中載具的速度通常有报大 的變化’所以當兩連續通信事件之間的時間差為大時， 此解決辦法有些粗糖。通常地’郊區道路與市區間道路 具有不同的交通環境，舉例而言，在經過—些村落的城 市間道路上，載具的行程速度根據位置而變化，例如在 接近村落時速度慢且在離開村落時速度快。因此，此解 決辦法無法精確地評估道路的交通狀態。 大部分的行動通信㈣具有线定位的功能，主動 201217751 定位已被廣泛的使用於行動定位服務（LBS)。以主動地傳 呼（paging)行動使用者的電話，可決定行動使用者之位 置。然而’主動定位功能將會觸發基地台與行動電話間 的sil息傳遞互動’其將花費大量的無線資源。 【發明内容】 有鑑於上述技術問題提出本發明，且本發明之目的 為提供用以基於行動通信網路以決定道路之即時行程時 間的方法與裝置，其可精確地即時提供道路交通狀態， 並能涵蓋所有道路，且花費少。 根據本發明之一態樣’提供用以基於行動通信網路 以決定道路之即時行程時間的方法，該方法包含以下步 驟：收集發生在正於受監視道路上的行動使用者的通信 事件，以獲得行程時間取樣；根據行程時間取樣，決定 在受監視道路上之對應道路區段的即時行程時間；對於 在受監視道路上之尚未決定即時行程時間的未決定道路 區段，選擇最有可能出現在未決定道路區段上的候選行 動使用者；主動定位候選行動使用者；以及以該主動定 位作為候選行動使用者之一通信事件，返回至收集發生 在正於受監視道路上的行動使用者上之通信事件的步 驟’以決定未決定道路區段之即時行程時間。 根據本發明之另一態樣，提供用於基於行動通信網 201217751 路以決定道路之即時行程時間的裝置，該裝置包含：收 集模組，其收集發生在正於受監視道路上之行動使用者 的通^事件’以獲得行程時間取樣；行程時間決定模組， 其根據打程時間取樣，決定在受監視道路上之對應道路 區&的即時行程時間；選擇模組其對於在受監視道路 上之尚未決定即時行程時間的未決定道路區段，選擇最 有可能出現在未決定道路區段上的候選行動使用者；以 及主動定位模組，其主動定位候選行動使用者，且將主 動足位作為候選行動使用者之一通信事件，提供至收集 模組以決定未決定道路區段的即時行程時間。 【實施方式】 上文所述，與其他本發明之物件、特點、及優點將 由下述具體實施例料盡描述，以及相連的伴隨圖式而 更為顯然。 第1圖圖示根據本發明之—具體實施例，用以基於 仃動通信網路以決定即時行程時間的方法之流程圖。具 體實施例將併同圖式以詳盡描述。 終端、基地台、及 為涵蓋一細胞服務 眾所皆知行動通信網路係由行動 行動交換中心等等所组成。基地台可 區的全向(_i-directional)基地台，或為涵蓋許多細胞 服務區（例如三個細胞服務區）的方向導向 6 201217751 (direction-oriented)基地台。當行動終端發生—通信事 件，例如行動終h進入新細胞服務區以更新位置、發送 /接收簡訊、啟動/接收通話、或在通信期期間執行交 遞時，基地台與行動交換中心將會相應地紀錄通信事件 發生的時間與提供服務之細胞服務區的位置。本具體實 施例利用此等資訊以監視道路交通。 如第1圖所示’在步驟31〇1中，在選擇一受監視道 路之後，根據行動通信網路内相關於受監視道路的細胞 服務區’將受監視道路分段成複數個道路區段。 在本具體實施例中，首先，根據行動通信網路的部 署，獲得在沿著受監視道路之特定距離内的所有細胞服 務區（例如受監視道路兩側一公里以内的細胞服務區）， 以及該等細胞服務區的位置資訊。接著，查詢這些獲得 的細胞服務區之歷史交遞紀錄，以找出對應於受監視道 路的細胞服務區交遞序列，細胞服務區交遞序列被視為 父瓜視道路與基地台間的聯結序列。大體上細胞服務 區的歷史交遞紀錄被儲存在基地台控制器。可查詢基地 〇控制器以獲得在一時間範圍内之細胞服務區的歷史交 遞紀錄。當行動使用者正於受監視道路上移動且正在通 信期狀態時，細胞服務區交遞序列即表示歷史交遞序 列。接著，基於細胞服務區交遞序列將受監視道路分區 為複數個道路區段。因為細胞服務區具有特定的涵蓋範 201217751 圍’在本具體實施例中’在細胞服務區交遞序列中兩相 鄰細胞服務區之間的中間點被視為各別道路區段的邊 界’且由各別邊界點鑑別（identified )各別道路區段。 例如，假設獲得的細胞服務區交遞序列為細胞服務區 A-B-C-D-E ’且受監視道路的起點以「a」代表，細胞服 務區A與B之間的中間點以「b」代表，細胞服務區B 與C之間的中間點以「c」代表，細胞服務區c與D之 間的中間點以「d」代表，細胞服務區〇與E之間的中 間點以「e」代表，受監視道路的終點以r f」代表。則 對應細胞服務區A的道路區段可以（a，b)代表，對應細胞 服務區B的道路區段可以（b，c)代表，對應細胞服務區c 的道路區段可以（c，d)代表，對應細胞服務區D的道路區 段可以（d，e)代表，對應細胞服務區E的道路區段可以（e，f) 代表。在為全向基地台的情況下，兩相鄰基地台間的中 間點亦可作為各別道路區段的邊界。 接著’在步驟S105,將複數個道路區段的歷史行程 時間基線化’以獲得各別道路區段的基線（baseline )行 程時間。 在本具體實施例中’首先，基於在步驟Si〇i中獲得 的細胞服務區交遞序列之歷史交遞紀錄’對每個道路區 段的歷史行权時間進行計時（c〇untp如上所述，各別道 路區段的邊界為兩相鄰細胞服務區之間的中間點，即為 201217751 此兩細胞服務區的交遞點。因此，可基於交遞紀錄獲得

兩相鄰交遞點之間的主M 的寺間差’從而獲得對應道路區段的 灯程時間。大體上’選擇在一較長的時間範圍内的歷史 乂遞紀錄（例如在過去三個月内的紀錄），以更精確地對 歷史行程時間進行計時。接著對每個道路區段，將干擾 時門諸如由步仃(導致行程時間過長)與基地台邊緣交 遞（導致灯程時間過短）導致的干擾時間自歷史行程時 間中遽除以產生每個道路區段的基線行程時間。特定言 之’可基於所計時的歷史行料間產生歷史行程時間: 機率刀布圖。第2圖圖示—特定道路區段的歷史行程時 間之機率分布’其中橫軸代表時間，縱軸代表機率。接 著’過小或過大的時間值，諸如在第2圖中低於2〇秒或 高於秒的時間值，自機率分布圖中被移除，接著應用 機率平均法（probability averaging meth()d)以計算特定道 路區段的基線行程時間。 在本發明所屬技術領域中具有通常知識者，將會理 解以上步驟SiOW S1〇5的運作為在受監視道路上:程 序’故些程序可預先被執行且並不必要被包含在本具體 實施例的方法中。 接著’在步驟SU0中，收集發生在正於受監視道路 上的行動使用者的通信事件以獲得行程時間取樣。在本 具體實施例中’通信事件可為位置更新服務、撥叫/簡 201217751 訊服務、以及細胞服務區交遞之任一者。 首先’收集在一預定時間範圍内、發生於同—行動 使用者的兩連續通信事件。在此預定時間範圍為-可依 需求設置為數分鐘至數小時之觀察窗。在此「兩連續通 信事件」A表在正發生的序列中該兩通信事件為相鄰 的，例如’該兩通信事件為連續地發生，或於該兩通信 事件之間存有—時間區間，上述兩情況皆屬於「兩連續 通信事件」。接著，該兩通信事件發生之細胞服務區的位 置’與該兩通信事件之間㈣間差，被記錄為行程時間 取樣，行程時間取樣表示自第一通信事件發生之細胞服 務區起點至第=通信事件發生之細力服務區起點所耗費 的時間。 下文將以一範例解釋行程時間取樣的產生。在此範 例中’假設行動通信網路中的基地台為全向基地台，其 每一者僅涵蓋一細胞服務區，且該細胞服務區可由對應 基地台的識別號（identifier )鑑別。行動使用者經由基 地台A在8:46時使用簡訊服務，基地台a(細胞服務區 A)的位置（緯度，經度）為（39.65722035, 1 16.381390249) 且涵蓋範圍為2000公尺；行動使用者經由基地台B在 9:40時播打電話，基地台B(細胞服務區B)的位置為 (39.51223035，1 16.30998024)且基地台B涵蓋範圍為 1400公尺。為簡潔起見，在行程時間取樣中，可以細胞 10 201217751 服務區的識別號代替細胞服務區位置，換言之，行程時 間取樣可以（A，B，54分鐘）代表之。 接著’在步驟S115中，根據在步驟S110中獲得的 行程時間取樣，決定在受監視道路中的對應道路區段之 即時行程時間。 在本具體實施例中，首先，因為一些行程時間取樣 不能被用於計算行動使用者的移動速度，自獲得的行程 時間取樣中萃取有效的行程時間取樣。特定言之，對每 個行程時間取樣，決定在行程時間取樣中兩細胞服務區 的位置是否相同，若相同則忽略此行程時間取樣。若此 兩細胞服務區為不同的細胞服務區，則決定此行程時間 取樣為有效的行程時間取樣。 再者’若此兩細胞服務區的位置不同，則亦可決定 此兩細胞服務區是否為相鄰的細胞服務區，且若此兩細 胞服務區為相鄰的細胞服務區則行程時間取樣亦可被忽 略。若此兩細胞服務區不為相鄰的細胞服務區則決定此 行程時間取樣為有效的行程時間取樣。由此可避免由發 生在兩細胞服務區的相鄰邊界的兩通信事件所導致的錯 誤。在此情況下，僅當行程時間取樣包含兩相異且不相 鄰的細胞服務區時，行程時間取樣為有效的。 接著，從有效的行程時間取樣中選擇可唯—地 (uniquely)決定一特定道路區段的即時行程時間之—明 201217751 確的取樣，且使用明確的取樣以鑑別其對應的道路區 段。再者，當同樣的道路區段上存在複數個明確的取樣， 則自該等明確的取樣計算一算術平均值，並使用算術平 均值作為即時行程時間以鑑別道路區段。接著，對於在 有效行程時間取樣中之明確的取樣而言（意味該取樣對 應的道路區段並不為唯一），比較明確的取樣中之一時間 差與每個可能的道路區段之各別的道路區段組成之即時 行程時間的總和，該等可能的道路區段係對應於明確的 取樣，以選擇在時間上最接近對應於明確的取樣的道路 區段之可能的道路區段，其中對於尚未決定即時行程時 門的道路區段組成，使用此道路區段的基線行程時間以 代替即時行程時間。接著，在時間上最接近之可能的道 路區段視為（identified with)明確的取樣。 在上述步驟S115之後，法，丄· 决疋疋否仍有尚未決定即時 行程時間的未決定道路區段 匕仅右無未決定道路區段，則 思味著，在受監視道路上的 工幻所有道路區段的即時行程時 間均已被決定，且方法έ士击。—^ > 、.。束右仍存在未決定道路區段 (例如以基線行程時間取代 代即時仃程時間的道路區段，或 未包含在於步驟Sll〇中庐犋 獲仔的仃程時間取樣中的道路 區段），則在步驟S120中， ☆ 對於尚未決定行程時間、在 欠監視道路上的未決定道路 疋、峪區蚁，選擇最有可能出現在 未決定道路區段的候選行動使用者。 12 201217751 本’、體貫施例中，選擇候選行動使用者的策略 為考慮使用者可在特定時間以現有的速度向量通過未 兵疋道路區&的仃程機率，具有大機率的使用者將被選 為候選彳T#使$者。假設未決定道路區段的長度為K， 行動使用者在起始;士# 於田下時間τ之特定時間點t通過未 決疋道路區#又的條件為：行動使用者的行程速度大於 v(K,t)=栏

t 丁，I 卜「J ^ r d」代表行動使用者從當下位置到未 決定道路區段之起始點的位置。因為使用者的當下位置 係位在使用者當下屬於的細胞服務區之涵蓋範圍内，「d」 係為一變數’該變數的平均值為從使用者當下屬於的細 胞服務區之位置到未決定道路區段之起始點的距離 E[d] ’且該變數的標準差為細胞服務區的涵蓋範圍r。 在本具體實施例中’行動使用者可在時間t通過未決定 道路區段的機率’由在使用者之速度向量V與V(K，t) 之間的預測相關係數C所量測而得。假設在細胞服務區 中的行動使用者於當下的位置係為均勻分布（uniformly distributed) ’則V(K, t)可被近似地視為在最小速度 與最大速度Vmax間均勻分布，其中vmin係基於以下的公 式（1)計算出： V„ E[d]-R-HK ———’ Ο) 以及，最大速度Vmax係基於以下的公式（2)計算出 13 (2) (2)201217751

因此’可基於以下的公式(3)得到預測相關係數C: 特定言之，在步驟S120中，根據在步驟S115中獲 得的有效行程時間取樣’分析對應的在受監視道路上的 -使用者之移動模式以及速度向量。如上所述，行程 時間取樣由根據同-行動使用者的兩通信事件所產生， 因此行動使用者的速度向量可基於在有效行程時間取樣 中的兩細胞服務區之位置與時間差異而計算出，再者， 可分析行動使用者的移動模式(如步行或駕駛)。在本具 體實施例中，以下的作業將只在移動模式為駕駛的行動 使用者上執行。對於在上文給定的行程時間取樣，首先， 根據基於84座㈣統之距離計算公式，計算細胞服務區 A與B之間的距離： 幸 cosa 承 cosb + cosc^cosd Vsin7 a * sin2 c+sin2 b * sin2 d 其中L代表距離，R代表地球半徑，「&」與「b」各 別代表細胞服務區A的經度與緯度，「c」與「d」各別代 表細胞服務區B的經度與緯度。接著，可計算出行動使 用者的速度向量為V = 56公里/每小時。 在得到正在駕駛車輛之行動使用者的速度向量之 14 201217751 後可估汁故些行動使用者之每一者從當下時間到特定 時間在未決定道路區段上行程的行程速度，換言之，基 於上述a式⑴與公式⑺估計最小行程速度與最大行程 速度接對於行動使用者之每一者根據基於行動 使用者的速度向量與估計得之行程速度的公式（3)，計算 行動使用者可在時M t通過未決定道路區段的行程機 率。最後’將一定數量的具有大行程機率的行動使用者 選定為候選行動使用者。 上文已描述利用預測相關係數，以量測行動使用者 可在特定時間通過未決定道路區段的機率，以便選擇候 選行動使用者的範例，然而在此相關領域具有通常知識 者可⑽知到，亦可利用其他用以計算行動使用者可在特 疋時間通過未決定道路區段之行程機率的方法。 在以上關於選擇候選行動使用者的描述中，係自提 供有效仃程時間取樣之行動使用者中選擇候選行動使用 換。之’係自在不同細胞服務區中連續地發生兩通 仏事件之使用者中選擇候選行動使用者。 再者’在步驟S120中，當在特定未決定道路區段上 沒有户 不同且不相鄰細胞服務區中連續地發生兩通信事

件之行動使用者時’僅在未決定道路區段之前一道路區 段上發喹 _ 'X 通彳§事件之行動使用者亦可被選為候選行動 使用者。 15 201217751 —接^在步驟S125中’對選定的候選行動使用者執 仃主動疋位《主動定位為行動通信網路中的常見功能， 且為在本發明所屬技術領域具有通常知識者所熟知，因 此在此省略細節上的描述。接著，將主動定位視為候選 仃動使用者的一通信事件，且方法回到步驟川〇。未決 定道路的即時行程時間由執行步驟su〇與S115而決定。 、上所述可見，本具體實施例之基於行動通信網 路以決定道路的即時行料間的方法，根據發生在受監 視道路上的通信事件，以將受監視道路分為複數個道路 區段且決定每個道路區段的即時行程時間，可精確且即 時地監視道路的交通狀態。此可應用至各種道路狀態， 諸如城市道路、郊區道路與城市間道路等等。此外，本 具體實施例之方法係基於已存在的行動通信網路，故其 花費非常低。 第3圖圖不第1圖之具體實施例的方法的範例。為 了簡單起見’每個基地台為僅涵蓋-個細胞服務區的全 向基地台。因，-Γ L t 可由對應基地台的識別號鑑別細胞服 務區h第3圖中所示’假設有兩條各別以長虛線箭頭 與短虛線箭碩代表的受監視道路，起點與終點各別以「&」 與 j」表不。對於此兩受監視道路，各別對應的細胞服 務區父遞序列為A n 钓A-B-C-D-E_h與A-F-G-H，且兩相鄰細 胞服務區之間的中間點各別以「b」、「c」、「d」、「e」、「h」 16 201217751 與「f」、「g」、「h」表示。於是，此兩受監視道路根據細 胞服務區交遞序列被分區為複數個道路區段，可以{a， b}、（b，c}、{c,匀、{d，e}、{e，h}、{h，j}、{a，f}、{f，g}、 與{h'，j}鑑別。接著，獲得每個道路區段的基線行 程時間，諸如{a，b,20s}、{b,c’30s}、{c’d,50s}、{d，e，40s}、 {e，h，30s}、{h，j，2〇”、{af，3〇s}、{fg，4〇s 丨、{g，h’，3叫 與（h’’ j，3 0S} ^接著，以收集在一觀察窗（5分鐘）内發生 在同一行動使用者上的兩連續通信事件獲得行程時間取 樣’諸如{A，H，200s}、{F，H,80s}與{B，D，90s}。在以上的 行程時間取樣中，{F，H，80s丨與{B，D 9〇s}為明確的取樣， 且可作為即時行程時間以直接地鑑別對應的道路區段{f， h }與{b，d}。對於其他的道路區段{a，、{d，勾、& h}、 (h’ j}、{a，f}與{h’，j}，以他們的基線行程時間代替即時 仃程時間以鑑別他們。含糊的取樣應於兩 可此的道路區段“，b，c，d，e，h}與{a, f，g，h，}。此時， 道路區段ia a j ,、 ’ ’ ，d，e, h}的各別道路區段組成之即時行 程時間的總和為20 + 90 + 4〇 + 3〇=1 8〇⑷，道路區段{a, f，g， }的各別道路區段組成之即時行程時間的總和為 8〇 110(S)。因此，時間上最接近的道路區段為{a，b, c， ’ }所以含糊的取樣{A，H，200s}係用以鑑別道路區 又（a’ b’ c，d，e，h}。現在尚未決定即時行程時間的未決 &道路區段為{h’j} ]a，Π與{h’，j}。接著，對於未決定 17 201217751 道路區段，選擇在下〆個觀察窗中最有可能出現在此兩 未決定道路區段上的行動使用者’且在選定的行動使用 者上執行主動定位以獲得位置資m。接$再次獲得行程 時間取樣’以決定未決定道路區段的即時行程時間。 雖然第3圖的範例中提供兩受監視道路在本發明 所屬技術領域中具有通常知識者將可理解本具體實施例 之方法可被應用至任何數量的受監視道路。 在同樣的發明概念下，第4圖為根據本發明之一具 體實施例、用以基於行動通信網路決定道路之即時行程 時間的裝置之方塊示意圖。此具體實施例將連同於圖式 加以詳盡描述，其中對於與前揭具體實施例相同的部 件’將適當地省略其描述。 如第4圖所不，用以基於行動通信網路決定道路的 即時行程時間的裝置400包含：道路分區模組4〇1，其 根據相關於受監視道路的細胞服務區將受監視道路分段 成複數個道路.區段；收集模組4〇3,其收集發生於正於 受監視道路上的行動使用者的通信事件，以獲得行程時 間取樣；行程時間決定模組4〇4，其根據行程時間取樣 決疋在受監視道路上的對應道路區段的即時行程時間； 選擇模，、且405，其對於在受監視道路上之尚未決定即時 行程時間的未決定道路區段，選擇最有可能出現在未決 疋道路區段上的候選行動使用者；主動定位模組，

1S 201217751 其主動定位候選行動_，η μ + + 叮勒使用者，且將主動定位作為候選行 動使用者之一通信事件提供至收集模組403，以決定未 決定道路區段的即時行程時間。 應理解«為了簡單起見，道路分區模組彻與基 線模組402係包含於本具體實施例之裝置4〇〇中在本 發明所屬技術領域具有通常知識者將可理解此兩模組係 用以在受監視道路上執行程序，並不必要被包含在裝置 400 内 ° 在本具體實施例之裝置400中，在受監視道路被決 定後，道路分區模組401根據行動通信網路中與受監視 道路相關的細胞服務區，將受監視道路分段成複數個道 路區#又。在道路分區模組40 i中，細胞服務區涵蓋範圍 計算元件4011獲得沿著受監視道路之特定範圍内的所 有細胞服務區，以及細胞服務區的位置資訊，並將位置 資訊提供至查詢元件4012。接著查詢元件4(H2查詢相 關於細胞服務區的歷史交遞紀錄，以找出對應於受監視 道路的細胞服務區交遞序列。分區元件4〇13根據查詢元 件4012提供的細胞服務區交遞序列，將受監視道路分區 成複數個道路區段，其中以兩相鄰細胞服務區之間的中 間點作為各別道路區段的邊界，且可以對應細胞服務區 的識別號鑑別各別道路區段。 接著，在基線模組402中，複數個道路區段的歷史 19 201217751 行程時間被基線化以獲得道路區段的基線行程時間。特 疋δ之，計算元件4021根據在道路分區模組40 1中獲得 的細胞服務區交遞序列’就各別道路區段的歷史行程時 間計間’接著’基線行程時間產生元件4〇22自各別道路 區段的歷史行程時間中，濾除干擾時間（諸如由步行或基 地台邊緣交遞所導致的干擾時間）以產生道路區段的基 線行程時間。 接著’在收集模組403中，收集元件403 1收集在一 預定時間範圍内發生在同一行動使用者上的兩連續通信 事件，接著紀錄元件4032紀錄該兩通信事件發生時兩細 胞服務區的位置，以及該兩通信事件的時間差，以作為 行程時間取樣。 接著，行程時間決定模組404根據在收集模組4〇3 中獲得的行程時間模組，決定對應道路區段的即時行程 時間。特定言之，首先，決定模組4〇4丨對每個行程時間 取樣，決定行程時間取樣中兩細胞服務區的位置是否相 同，並在兩細胞服務區的位置不同時決定該行程時間取 樣為有效的行程時間取樣。接著，取樣選擇元件4〇42從 由決定元件4041提供之有效的行程時間取樣，選擇可唯 一地決定道路區段的即時行程時間之明確的取樣，且鑑 別tl件4043以明確的取樣鑑別道路區段。對於在有效行 程時間取樣中的含糊的取樣，比較與選擇元件4〇44比較 20 201217751 含糊的取#中的時間I，與每個對應於含糊的取樣的可 能的道路區段之各別道路區段組成的即時行程時間之總 和，以選擇時間上最接近之可能的道路區段，其中對於 尚未決定即時行程時間的道路區段組成，使用道路區段 組成的基線行程時間以代替即時行程時間。接著鑑別元 件4043鑑別時間上與含糊的取樣最接近的可能的道路 區段。 再者，決定元件4041可更進一步決定在此兩細胞服 務區位置不同時，此兩細胞服務區是否為相鄰細胞服務 區，並在此兩細胞服務區不為相鄰細胞服務區時決定該 行程時間取樣為有效的行程時間取樣。 再者，行程時間決定模組4〇4可更進一步包含平均 值計算元件》當相同道路區段上存在複數個明確的取樣 時，平均值計算元件計算出複數個明確的取樣的算術平 均值，接著鐘別元件4〇43以算術平均值鑑別道路區段。 對於在受監視道路上、即時行程時間尚未被決定的 未決定道路區段’選擇模組4〇5選擇最有可能出現在未 决疋道路區段上的候選行動使用者。選擇候選行動使用 者的策略已於上文描述，且將於此省略其描述。在選擇 模組405中’根據在行程時間決定模組4〇4中獲得的有 效行時間取樣’分析元件4〇5丨分析在受監視道路上的 對應仃動使用者之移動模式以及速度向量。接著，估計 21 201217751 兀件4052對每個對應行動使用者，估計行動使用者由當 下時間至特定時間通過未決定道路區段的行程速度。特 疋s之，估計元件4052根據方程式（1)與（2)各別估計行 動使用者的最小行程速度與最大行程速度。接著，機率 计算兀件4053對每個行動使用者，根據行動使用者的速 度向里以及在估計元件4〇52中估計的行程速度計算出 订動使用者可在特定時間通過未決定道路區段的行程機 率。特疋吕之，機率計算元件4〇53根據方程式計算 出預測相關係數C以作為行動使用者的行程機率。接 著，使用者選擇元件4〇54選擇一定數量之具有大行程機 率的行動使用者，以作為候選行動使用者。 如以上所述，上述之選擇模組405從在不同細胞服 務區發生兩連續通信事件的行動使用者中，選擇候選行 動使用者备，又有在不同細胞服務區發生兩連續通信事 件的行動使用者時’在選擇模組4〇5中的使用者選擇元 件4054亦可選擇僅在未決定道路區段之前—道路區段 上發生-通彳t事件的行動使目者，以作為候選行動使用 士。 接著主動疋位模組406主動定位由選擇模組4〇5 提供的候選行動㈣者，並將线定位料候選行動使 用者之-通信事件提供至收集模組4()3，以決^未決定 道路區段的即時行程時間。 22 201217751 應注意者為，基於行動通信網路以決定道路之即 行程時間的本具體實施例中之裝置_，係可操作以^ 現如第1圖所圖示之基於行動通信網路以決定道路 時行程時間的方法。 地个丹體貫施例 軟硬體的結合上。硬體部分可以為特定應用的邏輯來實 ^ °例如’上述具體實施例中用以基於行動通信網路決 定道路的即時行程時間的裝置，彳由諸如大型積體電 路、閘陣列、半導體（如邏輯晶片、電晶體，或如可程式 化閘陣列、可程式化邏輯裝置的可程式化硬體裝置)的硬 體電路來實現’或可由可被各種處理器執行的軟體來實 、或可由上述硬體電路與軟體的組合來實現。軟體部 分可被儲存於記憶體中，且由適當的指令執行系統諸如 微處理益 '個人電腦(PC)、或大型電腦來執行。 雖然本發明之用以基於行動通信網路以決定道路的 即時行程時間的方法與裝置以經由—些示例性具體實施 例描述之，# # , 不例性具體實施例並不為窮舉的 (、aUStlVe) ’在本發明所屬技術領域具有通常知識者在 修=離本發明精神與範_的情況下，可理解各種改變及 > 本發明並不限制於該等示例性具體實施例， 本發明之1E^僅由附加中請專利範圍定義。 23 201217751 【圖式簡單說明】 第1圖圖示根據本發明之—具 、遛實施例、用以基於 行動通信網路決定道路的 、 圖； 時間的方法之流程 第2圖圖示描緣歷史行程時間之機率分布之圖表· 第3圖圖示根據第1圖所圖示之具體實施例的方法 之一範例； 第4圖圖示根據本發明之-具體實施例、用以基於 行動通㈣路決定料的即時行料間㈣置之示意方 塊圖。 【主要裝置符號說明】 400 裝置 401 道路分區模組 402 基線化模組 403 收集模組 404 行程時間決定模組 405 選擇模組 4 022 基線行程時間產生 元件 4031 收集元件 4032 紀錄元件 4041 決定元件 4042 取樣選擇元件 4043 鑑別元件 24 201217751 406 主動定位元件 4044 比較與選擇元件 4011 細胞服務區涵蓋範圍 405 1 分析元件 計算元件 4012 查詢元件 4052 估計元件 4013 分區元件 4053 機率與計算元件 4021 計算元件 4054 使用者選擇元件 S101 步驟 S 12 5 25

Claims (1)

1. 201217751 七、申請專利範圍·· 1. 一種用以基於行動通信網路以決定一道路的即時行程 時間的方法，包含以下步驟： 收集步驟’收集發生於正在一受監視道路上之一行 動使用者的通信事件’以獲得行程時間取樣； 決定步驟，根據該等行程時間取樣，決定在該受監 視道路上之對應道路區段的該即時行程時間； 選擇步驟，對於在該受監視道路上之尚未決定即時 行程時間的一未決定道路區段，選擇最有可能出現在該 未決定道路區段上的一候選行動使用者； 主動定位步驟，主動定位該候選行動使用者；以及 以該主動疋位作為該候選行動使用者之一通信事 件，而回到該收集發生於正在一受監視道路上之一行動 使用者的通信事件之收集步驟，以決定該未決定道路區 段之該即時行程時間。 2·如申請專利範圍第（項所述之方法，其中該收集發生於 正在一受監視道路上之一行動使用者的通信事件以獲得行 程時間取樣之收集步驟，更包含以下步驟： 收集在一預定時間範圍内發生於同一行動使用者 之連續的兩通信事件；以及 26 201217751 紀錄该兩通信事件發生時細胞服務區的位置，與該 兩通彳§事件間的一時間差，以作為該行程時間取樣。 •如申凊專利範圍第2項所述之方法，其中該根據該等行 程時間取樣決定在該受監視道路上之對應道路區段的該即 時行私時間之決定步驟，更包含以下步驟： 對該等行程時間取樣之每一者，決定該行程時間取 樣中的兩細胞服務區之位置是否相同，並當該兩細胞服 務區之位置不相同時決定該行程時間取樣為一有效的 行程時間取樣； 自該專有效的行程時間取樣中，選擇可唯一地決定 一特定道路區段之該即時行程時間的一明確的 (unambiguous )取樣； 以該明確的取樣鑑別該特定道路區段； 對該等有效的行程時間取樣

   之一含糊的 (ambiguous)取樣，比較該含糊的取樣中之該時間差， 與對應於該含糊的取樣的每個該等可能的道路區段之 該等各別道路區段組成的該等即時行程時間之總和，以 選擇在時間上最接近之該可能的道路區段，以該道路區 段組成之一基線行程時間代替該道路區段組成之即時 行程時間；以及 27 201217751 以該含糊的取樣鑑別在時間上最接近的該可能的 道路區段。 4. 如申請專利範圍第3項所述之方法，其中該根據該等行 程時間取樣決定在該受監視道路上之對應道路區段的該即 時行程時間之決定步驟’更包含以下步驟： 當該兩細胞服務區之位置不同時，決定該兩細胞服 務區是否為相鄰細胞服務區；以及 當該兩細胞服務區不為相鄰細胞服務區時，決定該 行程時間取樣為有效的。 5. 如申請專利範圍第3項或第4項之任一項所述之方法， 其中該根據該等行程時間取樣決定在該受監視道路上之對 應道路區段的該即時行程時間之決定步驟，更包含以下步 驟· 田對於同一道路區段存在複數個明確的取樣時，計 算該等明確的取樣之算術平均值；以及 以該算術平均值鑑別該道路區段。 士申μ專利範圍帛i項所述之方法，其中料於在該受 皿視道路上之尚未決定即時行程時間的—未決定道路區段 28 201217751 選擇最有可能出現在該未決定道路區段上的一候選行動使 用者之選擇步驟，更包含以下步驟： 根據該等有效的行程時間取樣，分析在該受監視道 路上之該等對應行動使用者的移動模式與速度向量； 估計步驟，估計該等對應行動使用者之每一者自當 下時間至特定時間通過該未決定道路區段的速度； 計算步驟，根據該行動使用者之該速度向量與該估 計到的速度，計算該等行動使用者之每—者在該特定時 間通過該未決定道路區段的行程機率；以及 選擇一特定數量之具有大行程機率之行動使用者 以做為該候選行動使用者。 7.如申請專利範圍第6項所述之方法，其中該估計該等對 應行動使用者之每一者自當下時間至特定時間通過該未決 疋道路區段的速度之估計步驟，更包含以下步驟： V — E[d] R * I - K 根據 {~τ 估計該行動使用者之一最小行 程速度’其中E[d]代表自該行動使用者在當下時間屬於 的該細胞服務區之該位置至該未決定道路區段的一起 點的一距離，R代表該細胞服務區的一涵蓋範圍，κ代 表該未決定道路區段的一長度’ t代表該特定時間，τ 代表該當下時間；以及 29 201217751 E[d]-i-R-fK 根據 t-T估計該行動使用者之—最大行 程速度； 其中該（計算該等行動使用者之每一者在該特定時 間通過該未決定道路區段的行程機率）之計算步驟更包 含以下步驟： ^ V-V c = 111111(1,-逆-) 根據 計算該速度向量與該行動使用 者之該行程速度之間的一預測相關係數，作為該行動使 用者之該行程機率，其中V代表該行動使用者之該速度 向量。 8.如申請專利範圍第6項所述之方法，其中該選擇最有可 能出現在該未決定道路區段上的一候選行動使用者之選擇 步驟’更包含以下步驟： 選擇在該未決定道路區段之一先前道路區段上、僅 發生一通信事件的一行動使用者，以作為一候選行動使 用者。 9·如申請專利範圍第1項所述之方法’在該收集發生於正 在又眞視道路上之一行動使用者的通信事件之收集步驟 之前，更包含以下步驟： 30 201217751 分段（dividing)步驟，根據關聯於該受監視道路 的細胞服務區，將該受監視道路分段成複數個道路區 段； 基線化步驟，對該等道路區段基線化歷史行程時 間’以獲得該等各別道路區段的基線行程時間。 10.如申請專利範圍第9項所述之方法，其中該根據關聯 於該受監視道路的細胞服務區，將該受監視道路分段成複 數個道路區段之分段步驟，更包含以下步驟： 獲得沿著該受監視道路之一特定範圍内之所有細 胞服務區，與該等細胞服務區之位置資訊； 查詢與該等細胞服務區相關聯之歷史交遞紀錄，以 找出對應於該受監視道路之一細胞服務區交遞序列；以 及 根據該細胞服務區交遞序列，將該受監視道路分區 成複數個道路區段，其令在兩相鄰細胞服務區間的中間 點被視為該等各別道路區段的邊界。 11.如申請專利範圍第9 路區段基線化歷史行程時 線行程時間之基線化步驟 項所述之方法，其中該對該等道 間以獲得該等各別道路區段的基 ’包含以下步驟： 31 201217751 根據在該細胞服務區交遞序列中的歷史交遞紀 錄，對該道路區段之該歷史行程時間進行計時；以及 自該歷史行程時間濾除干擾時間，以產生該道路區 段的該基線行程時間。 如申請專利範圍第i項所述之方法，其中該通信事件 為位置更新服務、撥叫/簡訊服務、與細胞服務區交遞之任 一者。 以決定一道路之即時行程 13. —種用於基於行動通信網路 時間的裝置，其包含： 一收集模組，其收集發生於正在一受監視道路上之 一行動使用者的通信事件，以獲得行程時間取樣； -行程時間決定模組’其根據該等行程時間取樣， 決定在該受監視道路上之對應道路區段的該即時行程 時間； —選擇模組’其對於在該受監視道路上《尚未決定 即時行程時間的一未決定道路區段，選擇最有可能出、現 在該未決定道路區段上的一候選行動使用者； -主動m组’其主動定位該候選行動使用者， 且將該主動定位作為該候選行動使用者之κ言事 32 201217751 件，提供至該收集模組，以決定該未決定道路區段的該 即時行程時間。 14.如申請專利範圍第13項所述之裝置，其中該收集模組 更包含： 一收集70件，其收集在一預定時間範圍内發生在同 一行動使用者上之連續的兩通信事件；以及 一紀錄元件，其紀錄該兩通信事件發生時該細胞服 務區的位置，以及該兩通信事件的一時間差，以作為該 行程時間取樣。 b·如申請專利範圍第14項所述之裝置，其中該行程時間 決定模組更包含： 一決定元件’其對該等行程時間取樣之每一者，決 定該行程時間取樣中該兩細胞服務區的位置是否相 同，並在該兩細胞服務區的位置不同時決定該行程時間 取樣為一有效的行程時間取樣； 一取樣選擇元件’其自該等有效的行程時間取樣 中，選擇可唯一地決定一特定道路區段之即時行程時間 的一明確的取樣； 一鑑別元件’其以該明確的取樣鑑別該特定道路區 段； 33 201217751 —比較與選擇元件’其對該等有效的行程時間取樣 中之一含糊的取樣，比較該含糊的取樣中之該時間差， 與對應於該含糊的取樣的每個該等可能的道路區段之 該等各別道路區段組成的該即時行程時間之總和，以選 擇在時間上最接近之該可能的道路區段，以該道路區段 組成之一基線行程時間代替該道路區段組成之即時行 程時間； 其中該鑑別元件經配置以使用該含糊的取樣鑑別 在時間上最接近的該可能的道路區段。 1 6.如申請專利範圍第13瑙 項所述之裝置，其中該選擇模 包含： 刀析元件，其根據該等有效的行程時間取樣，分 析在該受監視道路上之哕笙料ώ m & 心°茨寺對應灯動使用者的移動模 式與速度向量； 一估計元件，其估計該等對應行動使用者之每一者 自备下時間至特定時間通過該未決定道路區段的速度； -機率計算元件’其根據該行動使用者之該速度向 量與該估計到的速度 计鼻該等行動使用者之每一者在 該特定時間通過該未決 定道路區段的行程機率；以及 一使用者選擇元件 程機率之行動使用者以 ’其選擇一特定數量之具有大行 做為該候選行動使用者。 34 201217751 17. 如申請專利範圍第16項所述之裝置，其中該估計元件 V E[d]-R + K 經配置以根據 t-τ估計該行動使用者之—最小行 程速度’其中E[d]代表自該行動使用者在當下時間屬於的 該細胞服務區之該位置至該未決定道路區段的一起點的一 距離’ R代表該細胞服務區的一涵蓋範圍，κ代表該未決 定道路區段的一長度，t代表該特定時間，τ代表該當下時 V — E[d〕+R+K 間；以及根據t-τ估計該行動使用者之一最大行 程速度， 〇 ^mia \ 該機率計算元件經配置以根據 心計算該速产 向量與該行動使用者之該行程速度之間的一預測相關係 數，如同該行動使用者之該行程機率，其中v代表該行動 使用者之該速度向量。 18. 如申請專利範圍第13項所述之裝置，其中更包含·· 一道路分區（segmentation)模組，其根據關聯於 該受監視道路的細胞服務區，將該受監視道路分段成複 數個道路區段； 一基線化模組，其對該等道路區段基線化歷史行程 時間，以獲得該等各別道路區段的基線行程時間。 35 201217751 19.如申請專利範圍第18項所述之裝置，其中該道路分區 模組更包含： 一細胞服務區涵蓋範圍計算元件，其獲得沿著該受 監視道路之一特定範圍内之所有細胞服務區，與該等細 胞服務區之位置資訊； 一查詢兀件，其查詢與該等細胞服務區相關聯之歷 史父遞紀錄，以找出對應於該受監視道路之一細胞服務 區交遞序列，以及 一分區元件，其根據該細胞服務區交遞序列，將該 受監視道路分區成複數個道路區段，其中在兩相鄰細胞 服務區間的中間點被視為該等各別道路區段的邊界。 36