分布式應(yīng)急調(diào)度系統(tǒng)的設(shè)計與實現(xiàn)

1、第 31卷第 8期 2010年 8月微 計 算 機 應(yīng) 用M I CROCOMPUTER APPLI CATI ONSV o l 31N o 8 A ug 2010分布式應(yīng)急調(diào)度系統(tǒng)的設(shè)計與實現(xiàn)劉 捷 冼 進(華南理工大學(xué) 計算機科學(xué)與工程學(xué)院 廣州 510006摘要 :該系統(tǒng)作為分布式應(yīng)急調(diào)度數(shù)字化系統(tǒng)的軟件部分 , 基于 V C+、 Socke t 編程、 UDP 組 播等技術(shù) , 將 集群系統(tǒng)與 調(diào) 度中心座席連接 , 實現(xiàn)調(diào)度臺服務(wù)端與座席的 相關(guān)功 能。該系統(tǒng) 采用了 分布式 的結(jié)構(gòu) , 各 座席之 間相互 獨立 , 協(xié) 同工作 , 有效地保證了系統(tǒng)的穩(wěn)定性 , 確保系統(tǒng)在惡劣的環(huán)境

2、下依然能正常運行。 該系統(tǒng)實現(xiàn) 了一個基 于工作量的 協(xié)商算法 , 以 解 決座席間的潛在應(yīng)答沖突 , 并自動調(diào)節(jié)各座席的負載。關(guān)鍵詞 :分布式 應(yīng)急調(diào)度 基于工作量的協(xié)商算法Desi gn and I m ple m entation of a D istri buted Em ergency D ispatch Syste m LI U Jie , X I A N Ji n(School O f Co m pute r Sc i ence &Eng i neer i ng , South China U niversity of T echno l ogy , Guangzhou

3、, 510006, Ch i naAb stract :T his syste m is the soft w are components o f a distr i buted em ergency dispatch dig ital syste m, based on V C +, Socket pro gra mm i ng , UD P mu lti cast , connecti ng the c l uste r hardware system and d i spatch center agents to ach i eve dispatche r server and age

4、nt s related features . T h i s syste m uses a distri buted structure , so a ll the agents are i ndependent o f each o t her and w ork together e ffective l y . T he struct ure ensures the stab ility o f this syste m so t hat t h i s syste m can w ork correctl y even i n a poor env iron m ent . Th i

5、s syste m i m ple m en ts a nego ti ation a l go rith m based on w ork l oad to reso lve the potenti a l confli ct a m ong agents and to auto m aticall y adjust t he wo rk l oad .K ey words :distributed , e m ergency dispatch , negotiati on a l gor it hm based on wo rk l oad1 引言分布式集群應(yīng)急調(diào)度數(shù)字化系統(tǒng)是按照公安業(yè)務(wù)

6、實際需要 , 切實圍繞應(yīng)急、防暴、防恐和重大保衛(wèi) 工作需要進行設(shè)計 , 以惡劣自然條件、重大事件可能的破壞為使用客觀條件 , 單基站可通、一個基站剩 下一個信道還可通、多基站可通、有線聯(lián)網(wǎng)可通 , 有線鏈路中斷后自身系統(tǒng)具備的無鏈路技術(shù)迅速自動 啟動繼續(xù)保障通信。系統(tǒng)的無線網(wǎng)專用鏈路技術(shù) , 確保在任何惡劣情況下 , 基站之間的自愈環(huán)聯(lián)網(wǎng) , 不 受任何客觀鏈路條件制約 , 為整個系統(tǒng)無線通信提供整體網(wǎng)絡(luò)通暢。本系統(tǒng)是分布式集群應(yīng)急調(diào)度數(shù)字化系統(tǒng)的軟件部分?；?VC +、 Socket 編程、 UDP 組播等技術(shù) , 將集群系統(tǒng)與調(diào)度中心坐席連接 , 實現(xiàn)調(diào)度臺服務(wù)端與座席的相關(guān)功能 , 是

7、集通信、指揮和調(diào)度于一體 , 是高度智能化的分布式應(yīng)急調(diào)度系統(tǒng)。本系統(tǒng)采用了分布式的結(jié)構(gòu) , 由指定網(wǎng)段內(nèi)登陸的座席自動組成 , 數(shù)量不限。各座席之間相互獨立 , 協(xié)同工作 , 任意座席故障不會對系統(tǒng)產(chǎn)生任何影響。本系統(tǒng)的核心在于實現(xiàn)一個基于工作量的協(xié)商算法 , 以解決座席間的應(yīng)答沖突 , 并自動調(diào)節(jié)各座席的負載。為了實現(xiàn)更短的響應(yīng)時間、更高的效率并且減輕 網(wǎng)絡(luò)負載 , 我們采用 UDP 組播的方式發(fā)送所有會話協(xié)商信息。本文于 2010-06-08收到 , 2010-07-16收到修改稿。2 系統(tǒng)結(jié)構(gòu)分布式集群應(yīng)急調(diào)度數(shù)字化系統(tǒng)分為硬件部分和軟件部分。 圖 1 系統(tǒng)結(jié) 構(gòu)圖硬件部分為單片機系統(tǒng)

8、 , 由物理上分散的基站和若干特制的移動臺組成。每個基站包括 4條或 8條可 分配的信道 , 負責呼叫的應(yīng)答、信道的分配、通話的維持等功能。各基站采用無線通信的方式與特制的 移動臺連接 , 工作在 350兆赫茲的頻率上 , 也可以通過已有的 PSTN 網(wǎng)絡(luò)接入普通的固定電話。移動臺和 固話統(tǒng)稱為終端。每次通話時 , 終端可以呼叫某個終端 (即單呼 , 需要指定終端號 或者呼叫若干個終 端 (即組呼 , 需要指定組號 , 被呼叫的終端需要在同一個組中 , 也可以選擇呼叫座席。軟件部分為純數(shù)字化 , 采用 VC+進行編寫。各個座席完全相同 , 在系統(tǒng)中處于同等地位 , 具體座 席的存在與否、具體座

9、席數(shù)量對系統(tǒng)無影響。每個座席運行在單獨的計算機上 , 與終端進行通信 , 實現(xiàn) 接警、呼出 (單呼或組呼 、監(jiān)聽 , 加入和退出組、轉(zhuǎn)接等功能。服務(wù)端為系統(tǒng)可選部件 , 負責集中存儲 通話記錄 , 保存通話語音內(nèi)容 , 提供語音內(nèi)容的檢索和下載 , 以及實現(xiàn)服務(wù)器硬盤空間管理。座席之間 采用 UDP 組播技術(shù)發(fā)送協(xié)商信息 , 以此減輕網(wǎng)絡(luò)的負擔。3 座席功能描述座席分為普通座席和管理座席 , 后者在前者的基礎(chǔ)上加入了額外的管理功能。所有的座席在部署時 , 都預(yù)先分配一個座席號 , 并加入到特定的組中。普通座席包括以下功能 :(1 接警 :移動臺發(fā)送呼叫請求 , 座席響應(yīng)請求的過程稱為接警。移動

10、臺在發(fā)送請求時無需指定具 體座席號。每當有外部呼叫進入時 , 呼叫請求信號將由硬件以組播的形式發(fā)送給所有的座席。座席在接 收到呼叫請求信號時 , 在界面上顯示圖形化提示。用戶點擊 接警 ! 按鈕后 , 經(jīng)過所有座席的內(nèi)部協(xié)商 , 決定由哪個座席發(fā)送響應(yīng)信號給基站 (具體協(xié)商算法見第 5小節(jié) , 由基站分配信道之后形成實際的通話 通路。通話時的語音信號全部記錄到本地 , 并在結(jié)束通話時上傳至服務(wù)器保存。(2 呼出 :座席發(fā)送呼叫請求 , 移動臺響應(yīng)請求的過程。座席在發(fā)送請求時需要指定移動臺號或移 動臺組號。具體流程類似于普通電話通信。(3 監(jiān)聽 :座席上顯示移動臺之間正在進行的通話 , 并可以選

11、擇加入到通話進行監(jiān)聽。(4 加入和退出組 :座席可以選擇加入或退出某個組。組呼建立時 , 座席可以選擇加入本次組呼 , 并可在任意時刻退出或再次加入。(5 音頻轉(zhuǎn)接 :由座席將呼叫請求通過有線 PSTN 轉(zhuǎn)接到熱線。(6 語音記錄查詢 :座席可以連接服務(wù)端查詢語音歷史記錄 , 并且可以下載到本地播放。普通座席 可以查詢該座席相關(guān)的語音記錄 , 管理座席可以查詢所有的語音記錄。管理座席還包括以下功能 :(7 統(tǒng)計 :包括所有座席的在線狀態(tài)、在線時長、通話時長等等。(8 插話 :加入到座席與終端正在進行的通話。4 服務(wù)端模塊劃分服務(wù)端分為四個模塊 :記錄存儲模塊、磁盤管理模塊、配置管理模塊和記錄查

12、詢模塊。記錄存儲模塊作為 W i n do w s 系統(tǒng)服務(wù)常駐內(nèi)存 , 負責監(jiān)聽固定端口 , 與座席通信 , 接收通話語音內(nèi) 容文件 , 并存儲在本地硬盤中 , 同時在數(shù)據(jù)庫中存儲通話記錄。磁盤管理模塊作為 W i n do w s 系統(tǒng)計劃任務(wù)定時觸發(fā)。啟動后 , 先掃描存儲文件夾 , 如果未超出最大 存儲空間 , 則結(jié)束運行 ; 如果已超出存儲空間 , 則根據(jù)清盤策略進行清盤操作。清盤策略包括 :按日清 盤 (清除最久的一天的全部音頻記錄 , 按月清盤 (清除最久的一月的全部音頻記錄 , 等等。配置管理模塊為系統(tǒng)管理員提供管理界面。使用前需登陸為系統(tǒng)管理員。系統(tǒng)管理員可在本程序中 修改系

13、統(tǒng)配置 , 啟動和停止系統(tǒng)運行 , 設(shè)置系統(tǒng)為 W i n do w s 系統(tǒng)服務(wù) , 刪除指定語音記錄等等。記錄查詢模塊為用戶提供了一個遠程查詢語音記錄的 W EB 界面。服務(wù)端所有的配置信息均保存在單獨的 Config . x m l 文件中 , 內(nèi)容包括監(jiān)聽端口 , 是否設(shè)置為 W in do w s 系統(tǒng)服務(wù) , 音頻記錄文件存儲路徑 , 最大存儲空間 (單位 MB , 清盤間隔時間 , 清盤策略 , 清盤時 是否考慮優(yōu)先級 , 數(shù)據(jù)庫信息 (地址 , 端口 , 用戶名 , 密碼等等 。5 協(xié)商算法5 1 系統(tǒng)模型本系統(tǒng)由多個地位相同的座席組成 , 座席的數(shù)目無法預(yù)知 , 系統(tǒng)由存活的

14、座席自組織形成網(wǎng)絡(luò)并提 供服務(wù)。本系統(tǒng)的特點 : 對于業(yè)務(wù)的實時性要求很高 , 因此協(xié)商過程不能太長 , 協(xié)商的步驟要盡量少 , 不能采用復(fù)雜的算法 ; #協(xié)商結(jié)果只要保證選出的節(jié)點唯一 , 不需要絕對的公平 ; 沒有中心節(jié)點保存 系統(tǒng)全局信息 , 因此需要由各座席在協(xié)商過程中交換實時運行信息和同步呼叫請求隊列。另外 , 算法還需要滿足兩個要求 :(1 短時間內(nèi)同一移動臺的重復(fù)呼叫 , 有可能是對同一事件的多次協(xié)調(diào) , 因此會需要由同一個座席 進行響應(yīng)。算法應(yīng)能保證其對該呼叫請求的優(yōu)先響應(yīng) , 即只要該座席空閑 , 則協(xié)商的最終結(jié)果必然是由 該座席響應(yīng)請求。但考慮到業(yè)務(wù)對實時性的需求 , 這樣

15、的優(yōu)先響應(yīng)又是有實效性的 , 在該座席忙的情況 下 , 需要有別的座席做出響應(yīng)。(2 在實際應(yīng)用中 , 只將座席響應(yīng)請求后的處理請求過程視作實際工作 , 希望各座席的實際工作量 大體相等 , 因此協(xié)商算法需要參考座席的歷史響應(yīng) , 從而影響到當前的競爭中 , 讓工作量較小的座席先 獲得響應(yīng)權(quán) , 實現(xiàn)負載的平衡。5. 2 算法原理在本系統(tǒng)中 , 座席間協(xié)商之后響應(yīng)呼叫請求的過程類似于分布式系統(tǒng)中各節(jié)點申請分布式鎖互斥訪微 計 算 機 應(yīng) 用2010年問關(guān)鍵資源的過程。經(jīng)典的分布式互斥算法基于時間戳 1并采用廣播的形式發(fā)送消息 , 節(jié)點發(fā)送包含時間戳請求消 息 , 其他節(jié)點在收到消息后 , 如果

16、參與競爭 , 則發(fā)送 FA I L 信息 ; 如果不參與競爭 , 則發(fā)送 OK 信息。每 個節(jié)點只有在收到所有回復(fù)消息之后才競爭成功?？芍?, 每次競爭需要 2(N -1 條消息交換 :N -1條 用于節(jié)點 P 發(fā)送請求 , N -1條用于其它節(jié)點回復(fù)應(yīng)答。在 k 個節(jié)點同時提出請求的時候 , 需要交換的消 息數(shù)將為 2k (N-1 。我們對算法進行了修改 :(1 將時間戳改為工作量。每個節(jié)點維護一個本地計數(shù) C ; i 所有協(xié)商信息中均包含發(fā)送節(jié)點的當前 計數(shù) , 節(jié)點在競爭時根據(jù)本地計數(shù)與所有協(xié)商信息比較 , 計數(shù)最小的節(jié)點競爭成功 ; 每次競爭結(jié)束后 , 節(jié)點更新本地計數(shù)。我們考慮四種情

17、況 :節(jié)點成功建立通話 C i=C i+L ; 節(jié)點參與競爭而競爭成功 , C i= C i+M; 節(jié)點參與競爭而競爭失敗 , C i=C i+N; 節(jié)點未參與競爭且處于忙碌狀態(tài) , C i=C i+K; 節(jié)點未參 與競爭且處于空閑狀態(tài) , C i 不變 ; 令 L>M >N>K >0。通過調(diào)節(jié) L 、 M 、 N 、 K 的值 , 即可較為公平地評 價各節(jié)點的工作量 , 達到我們所需要的負載相對平衡。(2 發(fā)送請求的節(jié)點不再回復(fù)其它節(jié)點的請求 , 而是根據(jù)本機的工作量和其它節(jié)點的請求消息中包 含的工作量來判斷競爭結(jié)果 , 如果本機工作量最小 , 則可知競爭成功 , 否

18、則失敗。在發(fā)送請求時 , 需要 的消息數(shù)不變 , 仍為 k (N-1, 在回復(fù)請求時 , 則只需 (N-k k 條消息 , 兩項相加為 k (2N -k-1 。 對比可知 , 修改后消息數(shù)比原來減少了 (k-1 條。(3 當一個節(jié)點需要優(yōu)先獲得響應(yīng)時 , 只需要在協(xié)商信息中將計數(shù)設(shè)置為 0, 則必然可以競爭成功 , 證明從略。5 3 算法實現(xiàn)5 3 1 名詞定義工作量 :每個座席維護一個計數(shù) C, i 初始值為 0。響應(yīng)權(quán) :每個呼叫請求對應(yīng)一個響應(yīng)權(quán) , 希望應(yīng)答該請求的座席需要參與競爭 , 經(jīng)協(xié)商后由某座席 獲得該響應(yīng)權(quán) , 獲得響應(yīng)權(quán)的座席負責響應(yīng)該請求。在競爭響應(yīng)權(quán)時 , 工作量較小的

19、座席將獲得響應(yīng)權(quán)。 優(yōu)先響應(yīng)規(guī)則 :某個座席需要對某些呼叫請求優(yōu)先獲得響應(yīng)權(quán) , 也就是說 , 在多個參與競爭的座席 工作量相同時 , 算法需要保證該座席總是能夠獲得響應(yīng)權(quán)。需要優(yōu)先響應(yīng)的呼叫請求應(yīng)滿足特定要求。 比如某移動臺在一定時間間隔內(nèi)重復(fù)進行的呼叫 , 則前次響應(yīng)的座席需要優(yōu)先響應(yīng)。優(yōu)先響應(yīng)具有時間 限制 , 在等待一定時間后 , 優(yōu)先響應(yīng)的座席沒有嘗試對該呼叫請求獲取響應(yīng)權(quán) , 則該響應(yīng)權(quán)可由其它座 席公平競爭。5 3 2 消息定義呼叫請求消息 :每當有移動臺主呼調(diào)度臺時 , 由硬件部分組播此消息。消息格式由硬件部分與軟件 部分的連接中間件定義。呼叫應(yīng)答消息 :每當座席獲得響應(yīng)權(quán)時

20、, 發(fā)送此消息到硬件部分 , 從而形成實際的語音通路。消息 格式由硬件部分與軟件部分的連接中間件定義。競爭消息 :座席希望獲得響應(yīng)權(quán)時 , 需要組播此消息 , 消息中格式為 Co m pete ! , Reques, t C lien, t C ount。其中 Co m pete ! 為消息標識 , 與其它消息區(qū)分 ; R equest 代表呼叫請求 ; C lient 代表座席標識 ; C ount 代表該座席當前工作量。放棄消息 :座席不參與某響應(yīng)權(quán)的競爭時 , 需要組播此消息 , 消息中格式為 Abandon ! , R eques, t C li e nt。其中 Abandon ! 為

21、消息標識 , 與其它消息區(qū)分 ; Request 代表呼叫請求 ; C li e n t 代表座席標識。 5 3 3 算法準備每個座席需要維護三種資源 :優(yōu)先隊列、普通隊列和通話記錄表。688期劉 捷 等 :分布式應(yīng)急調(diào)度系統(tǒng)的設(shè)計與實現(xiàn)優(yōu)先隊列包括以下信息 :移動臺號 。優(yōu)先隊列按照 FI FO 的順序存取呼叫請求。不再優(yōu)先響應(yīng)的呼 叫請求將移至普通隊列的尾部。座席會優(yōu)先參與競爭本隊列中的呼叫。普通隊列包括以下信息 :移動臺號 。普通隊列按照 FI FO 的順序存取呼叫請求。通話記錄表包括以下信息 :移動臺號 , 時間 。本表保存數(shù)據(jù)庫 Log 表的簡要記錄 , 采用本地時間 記錄。座席每次

22、初始化時 , 應(yīng)清空優(yōu)先隊列和通話記錄表 , 并與其它座席同步普通隊列 , 運行過程中不再 對上述三種資源做同步。5 3 4 算法流程(1 收到呼叫請求座席在收到呼叫請求時 , 將對比通話記錄表中的記錄 , 根據(jù)優(yōu)先響應(yīng)規(guī)則 , 決定將其放入優(yōu)先隊列 還是普通隊列。(2 競爭響應(yīng)權(quán)座席競爭響應(yīng)權(quán)時 , 對外組播包含自身工作量的競爭消息 ; 座席收到消息時 , 如果之前參與了該響 應(yīng)權(quán)的競爭 , 則不回送消息 , 否則回送放棄消息。每次競爭根據(jù)所有座席的工作量決定響應(yīng)權(quán)歸屬 , 工 作量相同則由座席標識較小的座席獲得響應(yīng)權(quán)。(3 更新工作量每次競爭結(jié)束 , 座席按照以下規(guī)則更新自身工作量 :如果

23、競爭成功 , 則 W =W +L ; 如果競爭失敗 , 則 W =W +M; 如果未參與競爭且座席處于忙碌狀態(tài) , 則 W =W +N; 如果未參與競爭且座席處于空閑狀 態(tài) , 則 W 不變。獲得響應(yīng)權(quán)的座席對外發(fā)送應(yīng)答消息 , 如果通話成功建立 , 則該座席工作量 W =W +K 。 以上 K >L>M >N >0。6 結(jié)束語經(jīng)過測試 , 本系統(tǒng)運轉(zhuǎn)良好 , 能夠達到設(shè)計目標 , 在任意惡劣的環(huán)境下 , 只要有一個座席存在 , 即 可保證系統(tǒng)的正常運行。在采用了基于工作量的協(xié)商算法之后 , 確實降低了網(wǎng)絡(luò)負載 , 縮短了響應(yīng)時間 , 并且能夠?qū)崿F(xiàn)較理想的負載平衡。參 考 文 獻1LAM PORT L. T i m e , C locks , and t he O rder i ng o f Events i n a D istri buted Syste m J.Co mmun ica ti