|
引言 售貨機上除基本自動(dòng)售貨功能外，增加了諸多功能，如GPRS短信模塊以加強安全監控，在售貨機上播放視頻廣告以提高運營(yíng)商的經(jīng)濟效益等。這就使得存在于售貨機內部的控制器(Vencling Machine Controller，VMC)的復雜程度也迅速增加，先前的一套用于小規模嵌入式系統的分析設計方法、應用程序結構、運行效率與易維護程度在當前的售貨機需求面前顯得有些力不從心了。有限狀態(tài)機理論在計算機應用領(lǐng)域有著(zhù)廣泛的應用，狀態(tài)機對處理一些復雜情況也大有裨益。在設計階段，開(kāi)發(fā)人員可以利用狀態(tài)機模型來(lái)描述復雜的系統，從而大大縮短項目的開(kāi)發(fā)周期，且系統易于維護。魏先民提出了有限狀態(tài)機在嵌入式領(lǐng)域應用的一個(gè)基本框架，但是在這個(gè)框架中，系統中的所有狀態(tài)都是互斥的關(guān)系，盡管有些狀態(tài)之間存在著(zhù)緊密的關(guān)系。V．Ayvazyan等論述了狀態(tài)之間不僅存在互斥關(guān)系，還存在包含關(guān)系(父狀態(tài)與子狀態(tài))。本文應用有限狀態(tài)機的這些特性，提出一個(gè)層次型有限狀態(tài)機(Hierarchical FSM，HFSM)模型，對售貨機控制器(VMC)進(jìn)行改進(jìn)。 1 有限狀態(tài)機 有限狀態(tài)機是一種具有離散輸入輸出系統的模型，在任何時(shí)刻都處于一個(gè)特定的狀態(tài)。對于事件驅動(dòng)的程序設計，它是非常有用的設計模型。在某一個(gè)狀態(tài)下有事件發(fā)生時(shí)，根據當前狀態(tài)和輸入事件的不同，選擇如何處理該事件以及是否需要轉換到下一個(gè)狀態(tài)。一個(gè)有限狀態(tài)機(FSM)是一個(gè)五元組，M=(K，E，T，S，Z)。其中，K是一個(gè)有限的狀態(tài)集合，它的每個(gè)元素稱(chēng)為“狀態(tài)”；E表示該系統能接收的所有事件的集合，它的每個(gè)元素稱(chēng)為一個(gè)“事件”；T是狀態(tài)轉換函數，是K×E→K上的映射；S 是系統的一個(gè)特殊狀態(tài)，一般是系統啟動(dòng)時(shí)的初始狀態(tài)；Z是K的一個(gè)子集，是一個(gè)終態(tài)集。 有限狀態(tài)機一般有2種表示方式：狀態(tài)轉移表和狀態(tài)轉移圖。通常用有向圖來(lái)表示有限狀態(tài)機，其節點(diǎn)代表狀態(tài)。如圖1所示，若在狀態(tài)SO接收到某個(gè)輸入事件 e1后轉向S1狀態(tài)，就在圖中畫(huà)一條從SO到Sl的帶箭頭的弧線(xiàn)，并在弧線(xiàn)上標記e1。 
2 基本思想 2．1 必要性分析 有限狀態(tài)機是通過(guò)事件來(lái)觸發(fā)狀態(tài)的轉變的，其事件來(lái)源主要有2個(gè)：其一是外部觸發(fā)事件，如響應用戶(hù)鍵盤(pán)的輸入；其二是內部觸發(fā)事件，如系統所發(fā)出來(lái)的各種命令。有限狀態(tài)機這種事件驅動(dòng)的特性具有良好的開(kāi)放性，可以根據用戶(hù)的要求方便地增加相應的狀態(tài)與事件，完成系統功能的擴展。本文所研究的自動(dòng)售貨機配有1個(gè)5×5的管理鍵盤(pán)和1個(gè)3×7用戶(hù)鍵盤(pán)，二者復用了部分的鍵盤(pán)掃描線(xiàn)；另外有37個(gè)外部事件源，加上幾條內部命令，可能觸發(fā)的事件達45 個(gè)。如此多的事件，當某個(gè)事件發(fā)生時(shí)，如果采用if…else或switch…case語(yǔ)句進(jìn)行一一判斷，將非常復雜。而采用有限狀態(tài)機，每個(gè)狀態(tài)維護一張事件表，無(wú)需比較，大大提高了響應速度；并且就擴展需求較為頻繁的自動(dòng)售貨機而言，有限狀態(tài)機也是便于維護的。 2．2 實(shí)現方式 根據系統中各個(gè)狀態(tài)之間是否存在包含關(guān)系，有限狀態(tài)機可以分為常規狀態(tài)機與層次型狀態(tài)機(hierarchicalstate machine)。對于前者，系統中各個(gè)狀態(tài)是獨立的、互斥的，適合應用于那些存在狀態(tài)數量不多的簡(jiǎn)單系統；而對于后者，系統中的狀態(tài)除了互斥關(guān)系以外，還存在真包含的關(guān)系。 分析自動(dòng)售貨機這樣一個(gè)狀態(tài)機，圖2為自動(dòng)售貨機的狀態(tài)圖(不完整)。
從圖中可以看出，自動(dòng)售貨機控制器存在的狀態(tài)數量是比較多的，但是無(wú)論何時(shí)，自動(dòng)售貨機總處于空閑、售貨、商品價(jià)格設置、時(shí)間設置、測試等諸多狀態(tài)之中的一個(gè)．這些狀態(tài)之間是互斥的。同時(shí)，上面列舉的所有狀態(tài)都包含子狀態(tài)，例如：狀態(tài)S2(時(shí)間設置狀態(tài))包括日期設置、時(shí)分秒設置、星期設置等子狀態(tài)，而對于S3(日期設置狀態(tài))又包括S4(日期顯示狀態(tài))和S5(日期編輯狀態(tài))兩個(gè)子狀態(tài)。因此，對于自動(dòng)售貨機控制器這樣一個(gè)系統，其內部的狀態(tài)機是一種層次型狀態(tài)機。本文根據層次型狀態(tài)機的互斥與包含的雙重特性，提出層次型有限狀態(tài)機模型，并且用來(lái)實(shí)現自動(dòng)售貨機控制器。模型使用樹(shù)結構來(lái)描述狀態(tài)集，包含其他狀態(tài)的狀態(tài)稱(chēng)為“樹(shù)枝節點(diǎn)”，不包含其他狀態(tài)的狀態(tài)稱(chēng)為“葉子節點(diǎn)”。為方便用單樹(shù)結構描述，總是設計一個(gè)狀態(tài)包含所有的狀態(tài)節點(diǎn)，稱(chēng)為“根節點(diǎn)”，它是一個(gè)虛擬的節點(diǎn)，在系統中沒(méi)有狀態(tài)與其對應。狀態(tài)機只能停留在葉子節點(diǎn)，而不能停留在樹(shù)枝節點(diǎn)，每個(gè)樹(shù)枝節點(diǎn)需指定一個(gè)子節點(diǎn)為它的默認子節點(diǎn)，以便狀態(tài)機進(jìn)入樹(shù)枝節點(diǎn)時(shí)能停留到葉子節點(diǎn)。 3 層次型有限狀態(tài)機模型 3．1 數據結構定義 HFSM模型采用樹(shù)結構實(shí)現有限狀態(tài)機，樹(shù)上的每一個(gè)節點(diǎn)都對應了自動(dòng)售貨機狀態(tài)機的一個(gè)狀態(tài)。其中根節點(diǎn)是一個(gè)特殊的節點(diǎn)，它對應的是一個(gè)虛擬的并不存在的狀態(tài)，其目的是為了構造一棵單樹(shù)，而不是每一個(gè)功能對應一棵樹(shù)。節點(diǎn)的數據結構如下：
其中，id為狀態(tài)編號，每個(gè)狀態(tài)編號在整個(gè)系統狀態(tài)機中是唯一的；name為狀態(tài)名；enter_func為狀態(tài)進(jìn)入操作；exit_func為狀態(tài)退出操作；event_table為事件表；sub_state_table為子狀態(tài)表。因為葉子節點(diǎn)沒(méi)有子狀態(tài)，而樹(shù)枝節點(diǎn)沒(méi)有狀態(tài)事件表，所以結構中的事件表與子狀態(tài)可以共享一段存儲空間。事件表中每個(gè)元素是另外一個(gè)結構FSM_STATE_EVENT，它有事件id(與事件源一一對應)、事件操作 (func)和下一狀態(tài)編號(next_state_id)三個(gè)成員。圖2所示的狀態(tài)圖子集經(jīng)過(guò)處理形成圖3所示的狀態(tài)樹(shù)，它是整個(gè)自動(dòng)售貨機狀態(tài)樹(shù)的一部分。
3．2 狀態(tài)轉換算法 在有限狀態(tài)機中，是通過(guò)事件的驅動(dòng)而進(jìn)行狀態(tài)轉換的。狀態(tài)轉換算法的關(guān)鍵就在于查找下一狀態(tài)在狀態(tài)樹(shù)中的位置，也就是在狀態(tài)樹(shù)中查找下一狀態(tài)的時(shí)間復雜度的問(wèn)題。與常規狀態(tài)機不同，層次型狀態(tài)機中的各個(gè)狀態(tài)不僅存在互斥關(guān)系，還存在包含關(guān)系，特別是當前狀態(tài)與下一狀態(tài)關(guān)系就更為緊密了，不僅存在局部相關(guān)性，而且在很多情況下，它們之間在狀態(tài)樹(shù)中表現為兄弟節點(diǎn)關(guān)系。因此，要在狀態(tài)樹(shù)查找下一狀態(tài)，需先查找當前節點(diǎn)的兄弟節點(diǎn)，再查找父節點(diǎn)的兄弟節點(diǎn)。如此循環(huán)，直到找到下一狀態(tài)或試圖查找根節點(diǎn)的兄弟節點(diǎn)(根節點(diǎn)沒(méi)有父節點(diǎn)，所以要查找的下一狀態(tài)是不存在的)。 狀態(tài)查找算法如下：
有限狀態(tài)機的一般狀態(tài)轉換過(guò)程是：系統首先執行exit_func退出當前狀態(tài)，然后執行驅動(dòng)此次狀態(tài)轉換的事件操作func，最后執行 enter_func進(jìn)入新?tīng)顟B(tài)。為了便于遍歷狀態(tài)樹(shù)，系統為層次型有限狀態(tài)機建立一個(gè)狀態(tài)堆棧，堆棧中記錄的數據是當前狀態(tài)在狀態(tài)樹(shù)中對應的節點(diǎn)路徑上所有節點(diǎn)(自身除外，因為沒(méi)有必要人棧)的地址。堆棧的初始狀態(tài)如圖4所示，此時(shí)系統處于空閑S1狀態(tài)，棧中只有根節點(diǎn)信息。在某個(gè)事件或一系列事件的驅動(dòng)下(比如通過(guò)按鍵顯示系統的當前日期)，系統將要從空閑狀態(tài)轉換到日期顯示狀態(tài)S4。從圖3的自動(dòng)售貨機狀態(tài)樹(shù)可以看出，系統需要經(jīng)過(guò)S1一S2一S3 一S4的過(guò)程，中間的S2和S3是不可停留的狀態(tài)。當按下管理鍵盤(pán)的“Time”鍵時(shí)，系統先執行exit_idle函數退出S1(空閑狀態(tài))，然后根據空閑狀態(tài)的事件表得到下一狀態(tài)編號，再通過(guò)狀態(tài)查找算法搜索狀態(tài)樹(shù)，最后到達目的狀態(tài)S4。S2與S3是兩個(gè)中間狀態(tài)，但是這兩個(gè)狀態(tài)節點(diǎn)的地址需要入棧。
3．3 模型評價(jià) (1)擴展性 為層次型有限狀態(tài)機模型增加新功能，只需在其根節點(diǎn)下增加一個(gè)子節點(diǎn)，因為新的子節點(diǎn)與其他兄弟節點(diǎn)是互斥的，所以模型可以很方便地進(jìn)行系統功能擴展。 (2)查找算法時(shí)間復雜度 假設系統中存在的狀態(tài)數量為n。如果不采用層次型有限狀態(tài)機模型，那么系統中的各個(gè)狀態(tài)都是相互獨立、互斥的，相當于所有的狀態(tài)都是一個(gè)虛擬根節點(diǎn)的子節點(diǎn)。這樣的話(huà)，查找下一狀態(tài)的時(shí)間復雜度為：
然而，上面的情況忽略了狀態(tài)之間的相關(guān)性，很有可能當前狀態(tài)與下一狀態(tài)是兄弟關(guān)系，此時(shí)的比較次數就會(huì )明顯減少。如果采用層次型狀態(tài)機，假設系統子功能數目為m(m>1)，那么平均每個(gè)子功能的狀態(tài)數目為n／m，當前狀態(tài)與下一狀態(tài)為兄弟節點(diǎn)的概率為p(0
其中，t1為當前狀態(tài)與下一狀態(tài)不是兄弟節點(diǎn)的查找時(shí)間，與狀態(tài)樹(shù)的平均深度^有關(guān)。但是由于存在局部相關(guān)性，并且這種相關(guān)性越大(即p值越大)，平均時(shí)間復雜度就越集中在前面部分(p·n)／(m·2)，后面的表達式值可以忽略不計，即：
顯然，T(n)2 結語(yǔ) 通過(guò)建立層次型有限狀態(tài)機模型，并應用改進(jìn)的數據結構與狀態(tài)轉換算法，自動(dòng)售貨機控制器的程序結構更為清晰。原來(lái)存在于程序中的諸多標志變量，由狀態(tài)機的各個(gè)狀態(tài)所取代，使系統具有更好的擴展性；并且模型很好地利用了狀態(tài)的相關(guān)性，縮短了查找所花費的時(shí)間。但是，該模型也存在一定的局限性。比如，很大數量在構造狀態(tài)樹(shù)時(shí)需要的存儲空間給一般嵌入式系統的成本帶來(lái)了挑戰，不過(guò)可以試圖通過(guò)讓所有的狀態(tài)共享內存空間的方法來(lái)解決這個(gè)問(wèn)題。因此，層次型有限狀態(tài)機模型應用于較為復雜的嵌入式系統具有更普遍的意義。 作者：周澤鵬,Zhou Zepeng(中南大學(xué)) 金甌,Jin Ou(金融貨幣識別與自助服務(wù)平臺技術(shù)工程中心) 來(lái)源：單片機與嵌入式系統 2009 (3) |
|
2019廣州國際無(wú)人值守零售暨無(wú)人店展覽會(huì ) The Guangzhou International Unattended Retail Exhibitions 2019 組委會(huì )聯(lián)系方式： 廣州中電國際展覽有限公司 電 話(huà)：020-2919 8950 E-mail：2100343293@qq.com 聯(lián)系人/WeChat：徐妍 159 8923 3176 誠邀參加廣州無(wú)人值守零售展——URE 2019 新零售行業(yè)國際品牌盛會(huì )，展示交易最佳選擇，宣傳推廣首選平臺！ 智能改變零售 科技引領(lǐng)生活 時(shí)間：2019年4月9-11日 地點(diǎn)：廣州琶洲國際采購中心 組織單位：廣州中電國際展覽有限公司 ※ 展品范圍 ◆ 無(wú)人值守零售終端： 1.無(wú)人零售店/便利店，無(wú)人娛樂(lè )與休閑服務(wù)（迷你KTV、電影院、健身房、按摩椅、球房等）、無(wú)人餐飲廳，無(wú)人停車(chē)場(chǎng)，無(wú)人加油站，自助洗衣及相關(guān)無(wú)人便民服務(wù)等； 2.智能售貨機(飲料機、綜合機、便利柜、咖啡機、售飯機、自助派發(fā)機等)，開(kāi)放貨架及辦公室零售服務(wù)等。 ◆ 無(wú)人值守零售技術(shù)及產(chǎn)品： 1.視覺(jué)圖像識別技術(shù)，生物識別技術(shù)，目標跟蹤技術(shù)及相關(guān)的AI技術(shù)，結算意圖識別和交易系統，電子標簽、射頻識別（RFID）技術(shù)，自助檢測與跟蹤系統、商品信息采集技術(shù)，二維碼、條形碼技術(shù)，視頻安防解決方案等； 2.數字化門(mén)店、智能貨架、智能柜、智能購物車(chē)、智能包裝、服務(wù)機器人、商品快速裝袋設施、出入口設備、集裝箱盒子等； 3.智能收銀、自動(dòng)結算、及相關(guān)貨幣解決方案，相關(guān)打印技術(shù)及耗材等； 4.大數據分析、消費者形象刻畫(huà)、IOT（物聯(lián)網(wǎng)）、區塊鏈、語(yǔ)音助理、客戶(hù)感知技術(shù)、商品感知、客流分析等。 ◆ 商品及供應鏈服務(wù)：各類(lèi)快消品（含食品、飲料、酒水、農產(chǎn)品、生鮮等），日用百貨，文創(chuàng )產(chǎn)品，商品配送服務(wù)及設備等。 ◆ 其它：專(zhuān)業(yè)配套服務(wù)、空間設計、場(chǎng)景營(yíng)造、培訓、媒體、招聘等。 ※ 展會(huì )日程 報到布展：2019年4月7-8日 展出時(shí)間：2019年4月9-11日 撤展時(shí)間：2019年4月11日下午 歡迎業(yè)界同仁踴躍報名參展，現正接受申請，請速與組委會(huì )聯(lián)系，索取參展申請表及展位平面圖！充分利用URE 2019，鞏固您的市場(chǎng)地位！ |
