李世斌, 金彥亮, 姚 煒, 趙建龍, 熊 勇

(1.上海大學(xué) 通信與信息工程學(xué)院，上海 200072； 2.中國科學(xué)院 上海微系統(tǒng)與信息技術(shù)研究所，上海 200050；3.上海物聯(lián)網(wǎng)有限公司，上海 201899)

優(yōu)先權(quán)排隊在消防物聯(lián)網(wǎng)中的應(yīng)用

李世斌1,2, 金彥亮1, 姚 煒3, 趙建龍2, 熊 勇2

(1.上海大學(xué) 通信與信息工程學(xué)院，上海 200072； 2.中國科學(xué)院 上海微系統(tǒng)與信息技術(shù)研究所，上海 200050；3.上海物聯(lián)網(wǎng)有限公司，上海 201899)

針對消防物聯(lián)網(wǎng)系統(tǒng)中消防監(jiān)控中心收到的火警信息存在延遲，可能導(dǎo)致救火作戰(zhàn)時機延誤的問題，提出了一種火警信息優(yōu)先傳輸?shù)慕鉀Q方案；首先，推導(dǎo)出FCFS的M/M/1排隊系統(tǒng)的運行指標(biāo)；其次，將消防報警信息分為火警報警信息、火警消除信息、故障報警信息和故障消除信息等4個優(yōu)先級，建立非搶占優(yōu)先權(quán)排隊系統(tǒng)，并推導(dǎo)出各個優(yōu)先級的運行指標(biāo)；最后，從平均逗留時間和平均隊長兩個維度，比較了非搶占優(yōu)先權(quán)排隊系統(tǒng)和M/M/1系統(tǒng)的性能;提出的火警信息優(yōu)先傳輸方案，滿足了火警信息時延小的要求，同時實現(xiàn)復(fù)雜度低，為消防物聯(lián)網(wǎng)安全信息數(shù)據(jù)的獲取提供一定的理論支撐。

消防物聯(lián)網(wǎng)；優(yōu)先權(quán)排隊；火警；時延

0 引言

目前，我國各級城市大部分建筑都安裝了依據(jù)國家標(biāo)準(zhǔn)《火災(zāi)自動報警系統(tǒng)設(shè)計規(guī)范》(GB50116-2013)的火災(zāi)自動報警系統(tǒng)(FAS，F(xiàn)ire Alarm System)，由火災(zāi)報警監(jiān)控終端、報警監(jiān)控通信網(wǎng)、報警監(jiān)控中心三部分組成。FAS系統(tǒng)實現(xiàn)了基本的火災(zāi)報警功能。隨著物聯(lián)網(wǎng)、大數(shù)據(jù)等技術(shù)的發(fā)展，通過網(wǎng)絡(luò)化手段實現(xiàn)對建筑消防設(shè)施運行的實時監(jiān)控具備了技術(shù)可行性。2015年3月，公安部消防局印發(fā)《公安消防“四項建設(shè)”三年規(guī)劃(2015—2017年)》的通知，明確要求“充分利用云計算、大數(shù)據(jù)、物聯(lián)網(wǎng)等現(xiàn)代信息技術(shù)手段，提升信息主導(dǎo)、準(zhǔn)確研判、主動防控水平，為轉(zhuǎn)變戰(zhàn)斗力生成模式、服務(wù)消防現(xiàn)實斗爭提供支撐?！币虼耍瑐鹘y(tǒng)的FAS系統(tǒng)需要發(fā)展演進(jìn)，不僅要傳輸火災(zāi)報警信號，還要傳輸消防設(shè)施故障狀態(tài)等消防安全信息，通過數(shù)據(jù)挖掘后對樓宇防火安全等級評估以及進(jìn)行火災(zāi)預(yù)測等。

在樓宇內(nèi)部署的消防主機提供火警以及消防設(shè)施的狀態(tài)信息，是消防物聯(lián)網(wǎng)重要數(shù)據(jù)來源之一。由于發(fā)生火災(zāi)時，系統(tǒng)必須第一時間向消防監(jiān)控中心報告火警信息，以便提高消防部隊快速反應(yīng)能力，爭取寶貴時間迅速出警滅火[1]，因此火警信號是延遲敏感信息，相反，故障和設(shè)施狀態(tài)等信號是非延遲敏感信息。而在消防報警系統(tǒng)中，大部分為故障信號，由于大量的故障信號影響了火警信號的傳輸，從而延誤了最佳救火時機，造成不可挽回的損失。

優(yōu)先權(quán)排隊模型由于其在通信系統(tǒng)中的廣泛應(yīng)用而成為排隊論研究中的一個熱點，國內(nèi)外學(xué)者開展了大量的研究和實踐。文獻(xiàn)[2]將信號預(yù)測優(yōu)先級排隊算法用于無線接入網(wǎng)中，可以最大限度地減少資源預(yù)留延遲和信令開銷，提高了微移動區(qū)資源預(yù)留的效率和自適應(yīng)性；文獻(xiàn)[3]將一種基于動態(tài)優(yōu)先級的排隊方案應(yīng)用在蜂窩網(wǎng)絡(luò)多媒體服務(wù)中，解決了非優(yōu)先級數(shù)據(jù)丟包率高和平均排隊延時長的問題；文獻(xiàn)[4]提出了一種具有優(yōu)先級排隊規(guī)則和服務(wù)水平約束的車輛修理緊急服務(wù)中心選址模型，該模型可以最大限度的提高服務(wù)的覆蓋范圍；文獻(xiàn)[5]針對不斷增加的網(wǎng)絡(luò)高速連接的需求，提出一種流水線計數(shù)優(yōu)先指標(biāo)的隊列管理新方案，該方案保證有大量優(yōu)先級隊列時可以有效地調(diào)度包；文獻(xiàn)[6]針對互聯(lián)網(wǎng)中延遲敏感和非延遲敏感的不同服務(wù)，提出一種非搶占短分組優(yōu)先的策略從而確保網(wǎng)絡(luò)整體延遲的最小化。

消防物聯(lián)網(wǎng)中，消防主機的各類信號通過工控機處理后由網(wǎng)關(guān)傳輸?shù)皆破脚_。為保證火警信息能第一時間發(fā)送到云平臺，本文建立非搶占優(yōu)先權(quán)排隊模型，將火警信息放入高優(yōu)先權(quán)隊列，將故障等其他信息放入低優(yōu)先權(quán)隊列，推導(dǎo)和分析了平穩(wěn)狀態(tài)下系統(tǒng)各優(yōu)先級的平均逗留時間和平均隊長，將它們同基于FCFS的M/M/1系統(tǒng)的運行指標(biāo)相對比，結(jié)果證明非搶占優(yōu)先權(quán)排隊可以提高火警信息的快速響應(yīng)能力，同時保證了故障等狀態(tài)信息的正常傳輸，提高了系統(tǒng)整體性能。

1 M/M/1排隊

排隊論中M/M/1模型具有重要意義，因為這種排隊模型在實際工作中經(jīng)常遇到。該模型具有以下規(guī)則：

規(guī)則1：顧客按參數(shù)為λ的泊松分布到達(dá)。

規(guī)則2：服務(wù)臺為每個顧客服務(wù)的時間為負(fù)指數(shù)分布，平均服務(wù)率為μ。

規(guī)則3：系統(tǒng)只有一個服務(wù)臺，先到先服務(wù)。

規(guī)則4：隊列容量無限，顧客源數(shù)量無限。

由此可得到其狀態(tài)流圖如圖1所示，圖中狀態(tài)k表示系統(tǒng)中有k個顧客，服務(wù)臺正忙著，且有k-1個顧客排隊等待。

圖1 M/M/1模型的狀態(tài)流圖

由文獻(xiàn)[7]得知：平穩(wěn)時系統(tǒng)內(nèi)有k個顧客的概率為:

pk=ρk(1-ρ)

(1)

1)系統(tǒng)內(nèi)顧客的均值(包括正被服務(wù)和排隊等候的顧客)

(2)

2)系統(tǒng)內(nèi)排隊等候的平均顧客數(shù)

(3)

3)顧客在系統(tǒng)中的平均等待時間

W(t)=P(w≤t)=P(w=0)+P(0

1-ρ·e-μ(1-ρ)t(t>0)

(4)

其密度函數(shù)為：

(5)

因此可得平均等待時間為：

(6)

4)顧客在系統(tǒng)中的平均逗留時間(等待時間加服務(wù)時間)

Ws=E[w+V]=

(7)

2 消防報警主機信息優(yōu)先權(quán)排隊模型

如圖2 所示，消防單位的所有自動報警主機通過串口與一臺工控機相連，工控機對報警信息進(jìn)行處理，然后通過網(wǎng)關(guān)將信息傳輸?shù)竭h(yuǎn)程消防監(jiān)控中心服務(wù)器。消防監(jiān)控中心對數(shù)據(jù)進(jìn)行分析處理后，提供給業(yè)主/物業(yè)、維保部門以及消防部門進(jìn)行使用。

圖2 消防主機信息上報示意圖

自動報警主機中的報警信息分為火警信息和故障信息兩大類，基于事件緊急情況考慮，消防監(jiān)控中心要優(yōu)先收到火警信息。因此先到先服務(wù)的M/M/1排隊模型已不能滿足系統(tǒng)的需求，本文提出火警報警信息優(yōu)先傳輸方案，將火警信息和故障信息劃分為不同的等級區(qū)分服務(wù)?；鹁址譃榛鹁瘓缶畔⒑突鹁畔深?，同樣故障也分為故障報警信息和故障消除信息兩類，因此系統(tǒng)將需要傳輸?shù)男畔⒎譃?個等級?；鹁瘓缶畔⑾碛凶罡邇?yōu)先級，其次是火警消除信息，再次是故障報警信息，最低優(yōu)先級為故障消除信息。具體傳輸方案步驟如下：

1)信息分類：由工控機識別來自自動報警主機中的報警信息并歸類，火警報警信息歸為第一優(yōu)先級，火警消除信息歸為第二優(yōu)先級，故障報警信息歸為第三優(yōu)先級，故障消除信息歸為第四類。

2)信息排隊：在工控機內(nèi)存中，各優(yōu)先級的信息按照時間先后順序各自排序，整體按照第一優(yōu)先級、第二優(yōu)先級、第三優(yōu)先級和第四優(yōu)先級形成一條隊列，其中，第一優(yōu)先級的排在最前。最近發(fā)生的信息排在所在優(yōu)先級隊列最后。

3)信息傳輸：在工控機內(nèi)存中的隊列依次通過通信網(wǎng)關(guān)發(fā)送。

根據(jù)以上傳輸方案，可建立消防報警主機信息優(yōu)先權(quán)排隊模型，具體服務(wù)規(guī)則如下：

規(guī)則1：單服務(wù)臺。

規(guī)則2：顧客到達(dá)系統(tǒng)服從參數(shù)為λi的泊松分布，λ1表示第一優(yōu)先級顧客的平均到達(dá)率，λ2表示第二優(yōu)先級顧客的平均到達(dá)率，λ3表示第三優(yōu)先級顧客的平均到達(dá)率，λ4表示第四優(yōu)先級顧客的平均到達(dá)率。

規(guī)則3：服務(wù)臺為每一級別的顧客服務(wù)的時間均服從參數(shù)為μ的負(fù)指數(shù)分布。

規(guī)則4：當(dāng)優(yōu)先級高的顧客到達(dá)系統(tǒng)時，發(fā)現(xiàn)服務(wù)臺正忙著，它不能搶占服務(wù)臺，而只能在比它低一級優(yōu)先級顧客前面排隊等待服務(wù)。

圖3 M/M/1非搶占優(yōu)先權(quán)排隊模型圖

下面求平穩(wěn)狀態(tài)時，各優(yōu)先級排隊的運行指標(biāo)。

1)火警報警信息隊列：

當(dāng)新到達(dá)的顧客為第一優(yōu)先級顧客，即火警報警信息時，它在系統(tǒng)中的平均等待時間由兩部分組成：

一部分是正在排隊等待服務(wù)的所有第一優(yōu)先級顧客平均服務(wù)時間之和T1。記排隊等待的火警報經(jīng)信息平均個數(shù)為Lq1，則：

(8)

其中:Wq1為平均排隊等待時間。

這樣，可得：

(9)

所以平均等待時間為：

(10)

根據(jù)Little公式[10]：

可得第一優(yōu)先級顧客，即火警報警信息在系統(tǒng)中的平均逗留時間為：

(11)

平均等待隊長為：

(12)

平均隊長(等待顧客加上服務(wù)臺正在服務(wù)的顧客)為：

(13)

2)火警消除信息隊列：

當(dāng)新到達(dá)的顧客為第二優(yōu)先級顧客，即火警消除信息時，它的等待時間有三部分組成。

第一部分是正在排隊等待服務(wù)的第一和第二優(yōu)先級顧客的平均服務(wù)時間之和T1：

T1=ρ1Wq1+ρ2Wq2

(14)

第二部分為等待正在服務(wù)的服務(wù)臺空出的平均時間：

(15)

第三部分為在新的第二優(yōu)先級顧客排隊等待期間，陸續(xù)到達(dá)的第一優(yōu)先級顧客優(yōu)先插隊造成的平均耽誤時間之和T3：

T3=ρ1Wq2

(16)

聯(lián)合式(14)～(16)得：

(17)

整理得平均等待時間為：

(18)

根據(jù)Little公式可得，第二優(yōu)先級顧客，即火警消除信息在系統(tǒng)中的平均逗留時間為：

(19)

平均等待隊長為：

(20)

平均隊長(等待顧客加上服務(wù)臺正在服務(wù)的顧客)為：

Ls2=λ2Ws2

(21)

3)故障報警信息隊列：

與第二優(yōu)先級顧客隊列相似，第三優(yōu)先級顧客，即故障報警信息的等待時間也有三部分組成，T2同第二優(yōu)先級顧客隊列的T2一樣，T1和T3如下：

T1=ρ1Wq1+ρ2Wq2+ρ3Wq3

(22)

T3=Wq3(ρ1+ρ2)

(23)

所以:

(24)

得到第三優(yōu)先級顧客，即故障報警信息平均等待時間為：

(25)

同樣，根據(jù)Little公式，可以得到故障報警信息的另外3個運行指標(biāo)。

4)故障消除信息隊列：

由公式(10)、(18)、(25)，可得到第四優(yōu)先級顧客平均等待時間如下：

(26)

與通過計算T1、T2、T3求得的平均等待時間一致，證明公式(26)是正確的。根據(jù)Little公式可求得第四優(yōu)先級顧客，即故障消除信息隊列的平均逗留時間、平均等待隊長和平均隊長。

3 模型數(shù)值分析

消防單位的自動報警主機通過串口與工控機相連，工控機對報警信息進(jìn)行處理，然后通過網(wǎng)關(guān)將信息傳輸?shù)竭h(yuǎn)程服務(wù)器，對一些大型建筑體，包含有十臺以上消防主機，這些消防主機的報警信息匯總到同一臺工控機上，消防單位平均每秒產(chǎn)生2條報警信息。在消防主機報警信息中，一般20%為火警信息，80%為故障信息。網(wǎng)關(guān)采用GPRS通信信道，每秒可以傳送3條報警信息。模型參數(shù)如表1所示。

表1 模型參數(shù)表

根據(jù)以上參數(shù)，可以得到M/M/1隊列和非搶占優(yōu)先級隊列中各個優(yōu)先級的運行指標(biāo)結(jié)果如表2所示。

表2 μ=3,λ=2時的運行結(jié)果

從表2中可以看出，第1優(yōu)先級和第2優(yōu)先級的火警信息的平均逗留時間相對于M/M/1隊列降低了40%，平均隊長更是遠(yuǎn)遠(yuǎn)小于M/M/1隊列，達(dá)到了火警信息基本上不用排隊就能發(fā)送出去的良好效果。雖然第4優(yōu)先級的故障信息的平均逗留時間相對于M/M/1隊列增加了40%，但故障信息為非時延敏感信息，因此在系統(tǒng)可以接受的范圍之內(nèi)。令μ=3，λ為變量得到平均逗留時間對比圖如圖4所示，平均隊長對比圖如圖5所示。

圖5 平均隊長對比圖

從圖4可以看出，采用非搶占優(yōu)先級排隊模型可以縮短對實時性要求高的火警信息的平均逗留時間，便于消防監(jiān)控中心盡早發(fā)現(xiàn)警情。從圖5中可以看出各個優(yōu)先級的平均隊長明顯小于M/M/1排隊模型的平均隊長，表明非搶占優(yōu)先權(quán)排隊模型既可以保證火警信息的優(yōu)先發(fā)送又可以保證盡可能多的發(fā)送數(shù)據(jù)，減少隊列中排隊等待的信息個數(shù)。因此，在網(wǎng)絡(luò)通信中，有實時性和非實時性的多服務(wù)要求時，基于優(yōu)先權(quán)排隊模型的網(wǎng)絡(luò)性能明顯優(yōu)于FCFS排隊模型。由于搶占優(yōu)先權(quán)排隊復(fù)雜度高于非搶占優(yōu)先權(quán)排隊，占用較多的系統(tǒng)資源，在工程實踐中，算法復(fù)雜度也是一個重要的考查指標(biāo)，因此，我們建立的非搶占優(yōu)先權(quán)排隊模型既滿足了火警信息延遲小的需求又滿足了復(fù)雜度低的要求。

4 結(jié)束語

本文針對消防物聯(lián)網(wǎng)進(jìn)程中越來越多的消防信息通過網(wǎng)絡(luò)進(jìn)行傳輸，從而造成比較緊急的火警信息時延高的問題，將消防報警信息分為4個不同的優(yōu)先等級，建立了非搶占優(yōu)先的排隊系統(tǒng)，提出了火警信息優(yōu)先的傳輸方案，提高了火警傳輸效率，降低了時延。系統(tǒng)不僅實現(xiàn)了同時對火災(zāi)和消防設(shè)施運行狀態(tài)的監(jiān)控，而且保證了火警的優(yōu)先處理，為消防物聯(lián)網(wǎng)系統(tǒng)的架構(gòu)設(shè)計提供了理論支撐。

[1] 劉 靜．基于ZigBee技術(shù)的無線火災(zāi)報警信息傳輸系統(tǒng)的設(shè)計[D]．長沙：中南大學(xué)，2007．

[2]LiJ，WangX，JiaJ，etal．TheMechanismofWeakDynamicResourceReservationBasedonSignalPredictionPriorityQueuinginWirelessAccessNetworks[A].NinthInternationalConferenceonHybridIntelligentSystems[C]．IEEEComputerSociety，2009：219-222．

[3]CaiJ．ADynamicPriorityTime-Threshold-BasedQueuingSchemeforCellularMultimediaNetworks[A].InternationalConferenceonWirelessCommunicationsNetworkingandMobileComputing[C]．IEEE，2010：1-4．

[4]CaoLS，LiuZX．Anemergencyservicecenterlocationmodelforvehiclerepairwithpriorityqueuingrulesandservicelevelconstrains[A].IEEE，InternationalConferenceonIndustrialEngineeringandEngineeringManagement[C]．IEEE，2011：1333-1336．

[5]WangH，LinB．Per-flowQueueSchedulingwithPipelinedCountingPriorityIndex[A].HighPerformanceInterconnects[C]．IEEE，2011：19-26．

[6]KeP，LiW，WuY．ResearchonMultipleServicesSchedulingBasedonPriority-QueuingModel[A].IEEE，InternationalConferenceonDependable，AutonomicandSecureComputing[C]．IEEE，2014：372-376．

[7] 高德智．關(guān)于兩類M/M/1排隊系統(tǒng)的漸進(jìn)穩(wěn)定性[J]．?dāng)?shù)學(xué)的實踐與認(rèn)識，2008，38(17)：202-205．

[8] 張 旭，劉 聰，胡 勝，等．認(rèn)知無線電網(wǎng)絡(luò)中基于排隊論的集中式頻譜分配策略[J]．計算機應(yīng)用研究，2015，32(1)：187-190．

[9] 朱廣萍．優(yōu)先權(quán)排隊問題的分析[J]．西南民族大學(xué)學(xué)報:自然科學(xué)版，2004，30(2)：134-137．

[10] 黃業(yè)文，吳 紅，王遠(yuǎn)世．非強占有限優(yōu)先權(quán)M/M/1排隊系統(tǒng)[J]．計算機工程與應(yīng)用，2013，49(13)：80-84．

Application of Priority Queuing in FS IOT

Li Shibin1,2, Jin Yanliang1, Yao Wei3, Zhao Jianlong2, Xiong Yong2

(1.School of Communication and Information Engineering, Shanghai University, Shanghai 200072, China; 2.Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences, Shanghai 200050, China;3.Shanghai Internet of Things Company Limited, Shanghai 201899, China)

In view of the delay of the fire information received by the fire monitoring center in the FS IOT, the issue of the time delay of firefighting may be caused, and a solution of the priority transmission of the fire information is put forward. Firstly, the operation indices of M/M/1 queuing system based on FCFS is deduced. Secondly, the fire alarm information is divided into four priorities: fire alarm information, fire eliminate information, fault alarm information and fault eliminate information. The paper establishes the non-preemptive priority queuing system, and derives the operation indices of each priority. Finally, the performance of non-preemptive priority queueing system and M/M/1 system is compares from two dimensions of average length of stay and average queue length. The priority system not only meets the requirement of small time delay, but also has low complexity, which provides a theoretical support for the acquisition of the fire safety information data.

fire system IOT; priority queueing; fire alarm; time delay

2016-11-07；

2016-12-06。

上海市科技創(chuàng)新行動計劃項目(16DZ1200900)。

李世斌(1993-)，男，碩士研究生，主要從事消防物聯(lián)網(wǎng)系統(tǒng)的研究。

1671-4598(2017)04-0189-04

10.16526/j.cnki.11-4762/tp.2017.04.052

TP393

A