M/M/1/∞/∞/PS強(qiáng)拆繼續(xù)型系統(tǒng)的優(yōu)先權(quán)決策優(yōu)化

李華嵩，羅兵，余健松

?

M/M/1/∞/∞/PS強(qiáng)拆繼續(xù)型系統(tǒng)的優(yōu)先權(quán)決策優(yōu)化

李華嵩，羅兵，余健松

（五邑大學(xué) 信息工程學(xué)院，廣東 江門(mén) 529020）

將風(fēng)險(xiǎn)函數(shù)統(tǒng)計(jì)引入處理M/M/1/∞/∞/PS信息系統(tǒng)規(guī)劃的優(yōu)先級(jí)決策問(wèn)題，利用一致最小風(fēng)險(xiǎn)函數(shù)評(píng)估行動(dòng)空間中系統(tǒng)決策的損失期望，從而在設(shè)計(jì)大規(guī)模通信系統(tǒng)時(shí)降低損失風(fēng)險(xiǎn)，以確保系統(tǒng)長(zhǎng)期運(yùn)轉(zhuǎn)的安全合理性.

系統(tǒng)優(yōu)先權(quán)；信息隊(duì)列處理；信息優(yōu)先策略

現(xiàn)代智能電網(wǎng)與物聯(lián)網(wǎng)對(duì)系統(tǒng)的控制本質(zhì)上可以理解為一個(gè)個(gè)信息服務(wù)平臺(tái)對(duì)各自要求服務(wù)的信息隊(duì)列的處理控制問(wèn)題.

目前對(duì)于信息系統(tǒng)隊(duì)列的論述文獻(xiàn)很多都集中在特定服務(wù)條件下的隊(duì)長(zhǎng)及排隊(duì)結(jié)構(gòu)分布方面[1-2]，近些年來(lái)也逐漸出現(xiàn)了利用排隊(duì)理論解決信息系統(tǒng)的優(yōu)化問(wèn)題，如文獻(xiàn)[3]利用數(shù)字排隊(duì)調(diào)度系統(tǒng)模型對(duì)失效率進(jìn)行分析，從而對(duì)系統(tǒng)可靠性進(jìn)行預(yù)測(cè). 文獻(xiàn)[4]采用基于P-Aloha多址通信技術(shù)進(jìn)行RFID系統(tǒng)的反碰撞處理，用排隊(duì)論中的M/D/1隊(duì)列模型對(duì)通信處理過(guò)程進(jìn)行建模分析，對(duì)RFID的重發(fā)、應(yīng)答器數(shù)量的優(yōu)化設(shè)計(jì)進(jìn)行了仿真. 文獻(xiàn)[5]利用排隊(duì)論對(duì)數(shù)據(jù)幀排隊(duì)延時(shí)及丟包建立基于以太網(wǎng)通信損失代價(jià)的數(shù)學(xué)模型，并利用邊際法計(jì)算出目標(biāo)函數(shù)取極值時(shí)的最佳隊(duì)列長(zhǎng)度實(shí)現(xiàn)系統(tǒng)隊(duì)列優(yōu)化.

由于通常情況下服務(wù)臺(tái)難以控制通信隊(duì)列的通信質(zhì)量、信源和隊(duì)列長(zhǎng)度，因此上述文獻(xiàn)算法在工程中的應(yīng)用受到限制. 而利用排隊(duì)論優(yōu)化服務(wù)臺(tái)信息優(yōu)先級(jí)策略方面的論述較少，因此本文在上述文獻(xiàn)的基礎(chǔ)上，利用風(fēng)險(xiǎn)函數(shù)解決M/M/1/∞/∞/PS的服務(wù)臺(tái)優(yōu)化安全問(wèn)題，研究如何引入統(tǒng)計(jì)決策的一致最小風(fēng)險(xiǎn)函數(shù)用以制定系統(tǒng)的服務(wù)臺(tái)的優(yōu)先級(jí)最優(yōu)決策方案，并應(yīng)用于實(shí)際工程的通信系統(tǒng)設(shè)計(jì)中.

1 系統(tǒng)信息的排隊(duì)特征分析

在設(shè)計(jì)服務(wù)臺(tái)機(jī)制的信息服務(wù)系統(tǒng)的優(yōu)先級(jí)服務(wù)策略時(shí)，總是假定請(qǐng)求信息的到來(lái)服從一定的先驗(yàn)概率分布. 且通常采用肯德?tīng)柗椒ㄓ孟率龇?hào)來(lái)定義排隊(duì)系統(tǒng)的性質(zhì)：

其中①為信息到達(dá)時(shí)刻的概率分布；②為服務(wù)時(shí)間概率分布；③為服務(wù)臺(tái)的個(gè)數(shù)；④為請(qǐng)求信息源的總數(shù)；⑤為系統(tǒng)內(nèi)信息隊(duì)列的容量；⑥為隊(duì)列服務(wù)處理的原則，若⑥缺省則認(rèn)為隊(duì)列處理的原則為FIFO原則（先進(jìn)先出原則first-in-first-out），若⑥為PS則為優(yōu)先級(jí)服務(wù)原則.

由于具有優(yōu)先權(quán)信息隊(duì)列的處理順序僅與當(dāng)前狀況有關(guān)，而與歷史無(wú)關(guān)，因此整個(gè)系統(tǒng)可以看成是一個(gè)馬爾可夫鏈下的生滅過(guò)程. 信息系統(tǒng)的服務(wù)臺(tái)優(yōu)化策略是指定分類(lèi)信息的優(yōu)先級(jí)來(lái)實(shí)現(xiàn)的，假定一個(gè)最簡(jiǎn)信息服務(wù)系統(tǒng)：信息到達(dá)時(shí)刻與服務(wù)時(shí)間均服從馬爾科夫概率分布，信息源的總數(shù)與信息隊(duì)列的容量均為無(wú)限多，僅有一個(gè)服務(wù)臺(tái)，其信息服務(wù)機(jī)制為優(yōu)先級(jí)服務(wù)，則隊(duì)列系統(tǒng)表述為M/M/1/∞/∞/PS.

通常賦予某類(lèi)信息優(yōu)先級(jí)的策略有兩種[6]，一種是強(qiáng)拆型優(yōu)先權(quán)，一種是非強(qiáng)拆型優(yōu)先權(quán).

定義1 假定隊(duì)列系統(tǒng)中A類(lèi)信息具有高于B類(lèi)信息的優(yōu)先權(quán)，若A類(lèi)信息到達(dá)時(shí)，無(wú)論當(dāng)前信息處理是否完成，系統(tǒng)服務(wù)臺(tái)都中斷當(dāng)前對(duì)B類(lèi)信息的服務(wù)處理，轉(zhuǎn)而對(duì)A類(lèi)信息進(jìn)行處理，該優(yōu)先權(quán)稱(chēng)為強(qiáng)拆型優(yōu)先權(quán) (PPDQ，Preemptive Priority Discipline Queue) .

非強(qiáng)拆型優(yōu)先權(quán)是當(dāng)A類(lèi)信息到達(dá)時(shí)，等待服務(wù)臺(tái)執(zhí)行完當(dāng)前B類(lèi)信息的處理，再對(duì)A類(lèi)信息進(jìn)行處理.

為論述方便，本文將PPDQ強(qiáng)拆型優(yōu)先權(quán)系統(tǒng)也簡(jiǎn)稱(chēng)為兩類(lèi)：一類(lèi)為強(qiáng)拆繼續(xù)型優(yōu)先權(quán)系統(tǒng)（PPSCDQ，Preemptive Priority and Service Continuous Discipline Queue），該類(lèi)系統(tǒng)服務(wù)臺(tái)在中斷低優(yōu)先權(quán)信息服務(wù)轉(zhuǎn)而對(duì)高優(yōu)先權(quán)信息進(jìn)行服務(wù)完成后，恢復(fù)到對(duì)低優(yōu)先權(quán)的信息服務(wù)時(shí)，服務(wù)從前次服務(wù)的中斷點(diǎn)開(kāi)始執(zhí)行，即強(qiáng)拆繼續(xù)型優(yōu)先權(quán)系統(tǒng). 另一類(lèi)為強(qiáng)拆重復(fù)型優(yōu)先權(quán)系統(tǒng)（PPSRDQ，Preemptive Priority and Service Repeat Discipline Queue），該類(lèi)系統(tǒng)服務(wù)臺(tái)在恢復(fù)到對(duì)低優(yōu)先權(quán)的信息服務(wù)時(shí)，服務(wù)從被中斷服務(wù)的信息服務(wù)過(guò)程的初始階段開(kāi)始執(zhí)行.

2 統(tǒng)計(jì)決策的風(fēng)險(xiǎn)函數(shù)分析

3 通信信息隊(duì)列的優(yōu)先權(quán)決策優(yōu)化處理

3.1 優(yōu)先權(quán)處理優(yōu)化的流程

將統(tǒng)計(jì)決策的風(fēng)險(xiǎn)函數(shù)概念引入M/M/1/∞/∞/PS信息隊(duì)列系統(tǒng)，可實(shí)現(xiàn)優(yōu)先權(quán)策略的優(yōu)化. 在對(duì)優(yōu)先權(quán)策略進(jìn)行風(fēng)險(xiǎn)函數(shù)評(píng)估之前，需要做一些準(zhǔn)備工作，包括對(duì)信息的初步簡(jiǎn)化分類(lèi)，信息先驗(yàn)概率的估算等等. 本文提出的優(yōu)化處理流程如圖1所示.

圖1 信息隊(duì)列優(yōu)先權(quán)決策優(yōu)化過(guò)程

實(shí)際上整個(gè)優(yōu)化過(guò)程中，處理工作量最大的一步是在依據(jù)先驗(yàn)概率分布對(duì)信息隊(duì)列進(jìn)行簡(jiǎn)單分類(lèi)預(yù)處理. 根據(jù)風(fēng)險(xiǎn)函數(shù)定義，本文可以給出以下推論：

以上兩個(gè)條件在現(xiàn)實(shí)中很難完全相同，主要原因是實(shí)際控制現(xiàn)場(chǎng)不確定因素較多，很多情況下無(wú)有效的先驗(yàn)樣本且無(wú)先驗(yàn)概率分布可追尋. 因此優(yōu)化過(guò)程中需要對(duì)頻率與損失影響相近的幾類(lèi)信息做近似處理.

3.2 優(yōu)先權(quán)信息隊(duì)列分布分析

等待信息隊(duì)列中A類(lèi)信息數(shù)量的分布概率為：

同時(shí)B類(lèi)信息在等待信息隊(duì)列中的平均值為：

該結(jié)果與M/M/1/∞/∞/PS信息系統(tǒng)常識(shí)一致：低優(yōu)先權(quán)信息的存在對(duì)高優(yōu)先權(quán)信息的隊(duì)列長(zhǎng)度無(wú)影響，而高優(yōu)先權(quán)信息的分布對(duì)低優(yōu)先權(quán)信息的隊(duì)列長(zhǎng)度產(chǎn)生了影響.

3.3 一致最小風(fēng)險(xiǎn)函數(shù)與決策優(yōu)化的應(yīng)用

表1 示例3類(lèi)信息的分布情況

決策目標(biāo)描述為：若優(yōu)先權(quán)A具有高于優(yōu)先權(quán)B的強(qiáng)拆繼續(xù)型優(yōu)先權(quán)，為1、2、3類(lèi)信息賦予A或B優(yōu)先權(quán)使得系統(tǒng)的損失數(shù)學(xué)期望值最小.

由于B類(lèi)信息在隊(duì)列中的存在不影響A類(lèi)信息的處理等待，因此由式（5）得具有A類(lèi)優(yōu)先權(quán)的信息在系統(tǒng)隊(duì)列中等待時(shí)長(zhǎng)的數(shù)學(xué)期望為：

由式（6）得具有B類(lèi)優(yōu)先權(quán)的信息在系統(tǒng)隊(duì)列中等待時(shí)長(zhǎng)的數(shù)學(xué)期望為：

根據(jù)定義3的損失函數(shù)定義有:

同理，可計(jì)算出其他7種決策函數(shù)對(duì)應(yīng)的風(fēng)險(xiǎn)函數(shù)為：

在該仿真系統(tǒng)中，各個(gè)決策行動(dòng)對(duì)應(yīng)的風(fēng)險(xiǎn)函數(shù)值如圖2所示：

4 結(jié)論

本文提出了一種優(yōu)先級(jí)決策優(yōu)化方法，將統(tǒng)計(jì)決策及風(fēng)險(xiǎn)函數(shù)引入信息系統(tǒng)的優(yōu)先級(jí)設(shè)定中，從而計(jì)算出在不同優(yōu)先級(jí)行動(dòng)決策下的系統(tǒng)損失期望，選擇出最優(yōu)的優(yōu)先級(jí)處理方案，以降低模擬通信系統(tǒng)的運(yùn)行風(fēng)險(xiǎn). 該方法可擴(kuò)展到其他應(yīng)用場(chǎng)合信息控制系統(tǒng)的決策優(yōu)化設(shè)計(jì).

[1] 張柏生，任劍鋒，孟相如. 基于排隊(duì)論的網(wǎng)絡(luò)通信系統(tǒng)的建模與分析[J]. 空軍工程大學(xué)學(xué)報(bào)：自然科學(xué)版，2002(3): 59-62.

[2] 唐應(yīng)輝，劉曉云. 延遲多重休假M(fèi)~x/G/1排隊(duì)系統(tǒng)的隊(duì)長(zhǎng)分布[J]. 系統(tǒng)工程學(xué)報(bào)，2004(6): 583-588.

[3] 陳春東. 數(shù)字排隊(duì)調(diào)度系統(tǒng)的可靠性分析[J]. 電信快報(bào)，2012(6): 3-4.

[4] 余潤(rùn)仙，高愛(ài)乃，丁永生. RFID系統(tǒng)中反碰撞處理的排隊(duì)建模與分析[J]. 計(jì)算機(jī)仿真，2005(8): 286-288.

[5] 金海波，仲崇權(quán). 基于排隊(duì)論的實(shí)時(shí)以太網(wǎng)緩存隊(duì)列優(yōu)化算法[J]. 大連理工大學(xué)學(xué)報(bào)，2012(1): 95-99.

[6] 唐應(yīng)輝，唐小我. 排隊(duì)論—基礎(chǔ)與分析技術(shù)[M]. 北京：科學(xué)出版社，2006.

[7] 王梓坤. 隨機(jī)過(guò)程[M]. 北京：科學(xué)出版社，1978.

[8]BERGER J O. Statistical decision theory and Bayesian analysis [M]. New York: Springer, 1985.

[責(zé)任編輯：韋 韜]

Optimizations of the Service Priority Strategy for M/M/1/∞/∞/PS Communication Systems

LIHua-song, LUOBing, YUJian-song

(School of Information Engineering, Wuyi University, Jiangmen 529020, China)

In this paper, the risk function is introduced into the priority decision-making of the M/M/1/∞/∞/PS information system and the uniformly minimum risk function is used to evaluate the loss expectation of decision-making in action spaces, thereby reducing the loss risk in the design of mass communication systems and ensuring the safety and rationality of long-term system operations.

system priority; message queue process; information priority strategy

1006-7302（2013）02-0048-06

TN911

A

2012-09-05

廣東省自然科學(xué)基金博士啟動(dòng)項(xiàng)目（S2011040005275）

李華嵩（1975—），男，廣東新會(huì)人，講師，博士，研究方向?yàn)橹悄茈娋W(wǎng)檢測(cè)技術(shù)及自動(dòng)化.