孫首兵, 陸 陽
(合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 合肥 230009)
數(shù)字貨架是一種基于射頻識別[1](radio frequency identification,RFID)技術(shù)的、可完成對貨物的存儲和自動(dòng)識別的智能貨架。隨著RFID技術(shù)的不斷成熟,基于RFID技術(shù)的數(shù)字貨架廣泛用于倉儲系統(tǒng)中。但是,目前RFID技術(shù)在數(shù)字貨架應(yīng)用中存在嚴(yán)重不足,主要表現(xiàn)在貨品信息讀取依靠固定的RFID讀卡器[2-3]進(jìn)行、數(shù)字貨架成本昂貴等。文獻(xiàn)[2]提出的電子貨架系統(tǒng)在每個(gè)貨位上安裝RFID讀卡器用來讀取貨位中貨品信息,不但增加了安裝難度,而且大大增加了系統(tǒng)成本;文獻(xiàn)[3]提出一種智能貨架系統(tǒng)及其實(shí)現(xiàn)方法,在貨架的每層上安裝RFID讀卡器,雖然一定程度上減少了RFID讀卡器的數(shù)量,但是增加了對RIFD讀卡的距離,同時(shí)無法完成對單個(gè)貨位貨品信息的讀取,增加了工作量。
本文設(shè)計(jì)了一種基于RFID的數(shù)字貨架二維移動(dòng)節(jié)點(diǎn)[4],采用單片機(jī)控制、雙伺服電機(jī)驅(qū)動(dòng)的方法,使得數(shù)字貨架貨品信息讀取只需單個(gè)RFID讀卡器即可完成,同時(shí)可以實(shí)現(xiàn)對貨品信息的定向讀取,減少了數(shù)字貨架成本;并重點(diǎn)討論了復(fù)雜情況下節(jié)點(diǎn)路徑規(guī)劃問題,從而提供了一種通用的節(jié)點(diǎn)路徑規(guī)劃算法,使得信息讀取時(shí)間縮短很多。
二維移動(dòng)節(jié)點(diǎn)是指可在貨架垂直面內(nèi)運(yùn)動(dòng)的RFID讀卡器。RFID讀卡器通過在平面內(nèi)的運(yùn)動(dòng),自動(dòng)讀取貨架上貨品的信息,實(shí)現(xiàn)對貨品的盤點(diǎn)和定位。
二維移動(dòng)節(jié)點(diǎn)主要由貨架、節(jié)點(diǎn)導(dǎo)軌、移動(dòng)控制模塊、信息采集模塊、無線收發(fā)模塊、主控模塊和數(shù)據(jù)管理模塊構(gòu)成。
(1)貨架。貨架根據(jù)放置貨品的質(zhì)量選取,并將貨架每層都劃分為若干貨位,貨位大小人為選擇,以RFID讀卡器發(fā)射功率所達(dá)范圍為標(biāo)準(zhǔn)。
(2)節(jié)點(diǎn)導(dǎo)軌。在貨架的側(cè)立面上安裝導(dǎo)軌,2根水平導(dǎo)軌(1根驅(qū)動(dòng)導(dǎo)軌和1根從動(dòng)導(dǎo)軌)分別安裝在貨架最高層和最底層上,1根垂直導(dǎo)軌安裝在2根水平導(dǎo)軌上,可以在水平導(dǎo)軌上滑動(dòng)。垂直導(dǎo)軌上安裝有滑塊,RFID讀卡器固定在滑塊上。
(3)移動(dòng)控制模塊。包括單片機(jī)、伺服電機(jī)、伺服電機(jī)驅(qū)動(dòng)器和接近開關(guān)以及開關(guān)電源等。單片機(jī)通過無線模塊接收上位機(jī)發(fā)送的指令,發(fā)出控制電機(jī)指令,2個(gè)伺服電機(jī)帶動(dòng)RFID讀卡器運(yùn)動(dòng),再通過無線模塊將運(yùn)動(dòng)結(jié)果返回上位機(jī)。接近開關(guān)信號輸出端與單片機(jī)I/O口相連,接近開關(guān)動(dòng)作反映RFID讀卡器運(yùn)動(dòng)至導(dǎo)軌端部,單片機(jī)需將相應(yīng)電機(jī)反向。
(4)信息采集模塊。包括RFID讀卡器、電子標(biāo)簽等。RFID讀卡器固定在垂直導(dǎo)軌滑塊上,可實(shí)現(xiàn)在平面內(nèi)的運(yùn)動(dòng),從而用于讀取和更新電子標(biāo)簽信息。電子標(biāo)簽貼在貨品上,用于存儲貨品信息。
(5)無線收發(fā)模塊。單片機(jī)、RFID讀卡器和主控模塊上都安裝無線收發(fā)模塊,用于收發(fā)控制指令和數(shù)據(jù)信息。
(6)主控模塊。主要用于發(fā)送移動(dòng)控制指令給節(jié)點(diǎn)移動(dòng)模塊并接收返回結(jié)果,發(fā)送電子標(biāo)簽讀取指令給信息采集模塊并接收返回結(jié)果。
(7)數(shù)據(jù)管理模塊。用于存儲和更新貨品信息和存儲信息。
二維移動(dòng)節(jié)點(diǎn)結(jié)構(gòu)外觀如圖1所示。
節(jié)點(diǎn)移動(dòng)控制模塊[5]主要包括單片機(jī)、伺服電機(jī)、伺服電機(jī)驅(qū)動(dòng)器、接近開關(guān)以及開關(guān)電源。節(jié)點(diǎn)移動(dòng)控制主要是對水平方向和垂直方向電機(jī)的控制,電機(jī)由單片機(jī)控制。電機(jī)采用東元精電股份有限公司生產(chǎn)的交流伺服電機(jī),型號為TSC06401C,驅(qū)動(dòng)器型號為TSTA20C;單片機(jī)采用STC89C52單片機(jī);接近開關(guān)采用SNOD05-N方形npn型接近開關(guān)。移動(dòng)控制模塊硬件連接圖如圖2所示。
由圖2可知,單片機(jī)的P1.0和P1.1口分別控制X向電機(jī)的轉(zhuǎn)速和方向,P1.2和P1.3口分別控制Z向電機(jī)的轉(zhuǎn)速和方向,P1.4~P1.7口分別用來接收X向?qū)к壵?、?dǎo)軌反向和Z向?qū)к壵?、?dǎo)軌反向的接近開關(guān)動(dòng)作信號。為了使得接近開關(guān)輸出信號具有與單片機(jī)相同的電平,同時(shí)防止干擾,采用TLP521芯片進(jìn)行隔離。
節(jié)點(diǎn)采用2個(gè)伺服電機(jī),分別控制其在水平方向和垂直方向上的運(yùn)動(dòng),2個(gè)方向電機(jī)獨(dú)立運(yùn)行,互不影響。X向電機(jī)和Z向電機(jī)轉(zhuǎn)速分別通過單片機(jī)定時(shí)器T0和T2定時(shí)控制。下面以定時(shí)器T0為例,說明定時(shí)器裝入初值的計(jì)算方法。
假設(shè)電機(jī)運(yùn)行速度為r,每轉(zhuǎn)需要脈沖個(gè)數(shù)為n,則每秒鐘單片機(jī)需發(fā)送脈沖個(gè)數(shù)為:
由于1個(gè)脈沖分為正脈沖和0,所以單片機(jī)每秒鐘中斷次數(shù)為:
即中斷時(shí)間為:
圖2 移動(dòng)控制模塊硬件圖
單片機(jī)采用12M的外部晶振提供時(shí)鐘周期,所以機(jī)器周期時(shí)間為:
則有:
即每隔3×107/(nr)個(gè)機(jī)器周期,定時(shí)器需要中斷1次。
T0定時(shí)器為16位定時(shí)器,工作在方式1,則初值為:
Z向電機(jī)采用定時(shí)器T2進(jìn)行控制,初值計(jì)算方法同T0。通過對初值大小的改變,可以方便地控制節(jié)點(diǎn)運(yùn)動(dòng)的速度。系統(tǒng)共設(shè)置了2擋速度:① 低擋,用于采集信息;② 高擋,用于信息采集完成后節(jié)點(diǎn)迅速返回原點(diǎn)。
為了方便對節(jié)點(diǎn)運(yùn)動(dòng)的控制,將貨架人為地劃分成若干相同的貨位,并建立如圖3所示的直角坐標(biāo)系(圖中虛線交叉點(diǎn)代表貨位中間位置)。在每個(gè)貨位里存放貨品,調(diào)節(jié)RFID讀卡器的功率,只要每次讀取過程中RFID讀卡器處于貨位中心位置,就可以使讀卡器只能讀取到一個(gè)貨位里貨品的信息,從而防止相鄰貨位貨品的干擾。
圖3 貨架劃分圖
由圖3建立的直角坐標(biāo)系可以看出,貨架被劃分成若干個(gè)標(biāo)準(zhǔn)的單位正方形,并且每個(gè)貨位都有自己相應(yīng)的坐標(biāo)值。節(jié)點(diǎn)在初始狀態(tài)下停在原點(diǎn)(0,0)處,在需要讀取貨品信息時(shí),節(jié)點(diǎn)運(yùn)動(dòng)到相應(yīng)貨位的中間位置,打開RFID進(jìn)行讀取。
節(jié)點(diǎn)在二維平面內(nèi)的運(yùn)動(dòng)主要可以分為以下3種。
(1)單個(gè)盤點(diǎn)。如果需要對單個(gè)貨位的貨品信息進(jìn)行盤點(diǎn),只需發(fā)送“單個(gè)盤點(diǎn)”指令。例如,需要盤點(diǎn)圖3中右上角貨位中的貨品信息,節(jié)點(diǎn)運(yùn)動(dòng)方案如下:Z向電機(jī)正向啟動(dòng),節(jié)點(diǎn)沿Z軸正向運(yùn)動(dòng)至坐標(biāo)(0,3.5)處,Z 向電機(jī)停止,X 向電機(jī)正向啟動(dòng),節(jié)點(diǎn)運(yùn)動(dòng)至坐標(biāo)(4.5,3.5)處,開啟RFID讀卡器,進(jìn)行信息讀??;信息讀取完成后,同時(shí)啟動(dòng)X向和Z向電機(jī),節(jié)點(diǎn)以高擋返回原點(diǎn),完成貨位盤點(diǎn)。
(2)單排盤點(diǎn)。如果需要對貨架某一排的所有貨位的貨品信息進(jìn)行盤點(diǎn),則需要發(fā)送“單排盤點(diǎn)”指令。例如,需要對圖3中第1排的貨位進(jìn)行盤點(diǎn),節(jié)點(diǎn)運(yùn)動(dòng)方案如下:Z向電機(jī)啟動(dòng),節(jié)點(diǎn)沿Z軸正向運(yùn)動(dòng)至坐標(biāo)(0,0.5)處,Z向電機(jī)停止,X向電機(jī)正向啟動(dòng),節(jié)點(diǎn)運(yùn)動(dòng)至坐標(biāo)(0.5,0.5)處,開啟RFID讀卡器,進(jìn)行信息讀??;信息讀取完成后,X向電機(jī)繼續(xù)正向啟動(dòng),節(jié)點(diǎn)運(yùn)動(dòng)至下一貨位位置,繼續(xù)進(jìn)行信息讀??;重復(fù)以上過程,直到將所有貨位讀取完為止;同時(shí)啟動(dòng)X向和Z向電機(jī),節(jié)點(diǎn)以高擋返回原點(diǎn),完成單排盤點(diǎn)。
(3)多貨位盤點(diǎn)。如果需要對多個(gè)而又無規(guī)律的貨位進(jìn)行盤點(diǎn),為了敘述方便,圖3中直角坐標(biāo)系的位置相對于之前所述坐標(biāo)向右上方平移了0.5,即圖3中的實(shí)線交叉點(diǎn)代表貨位的中間位置(之前所述代表貨位輪廓),a0代表原點(diǎn)。例如,圖3中 分 布 有a1、a2、a3、a4、a5、a66 個(gè) 待 盤 點(diǎn) 的 貨位,現(xiàn)在需要節(jié)點(diǎn)從原點(diǎn)(a0處)開始,依次盤點(diǎn)各貨位后再返回原點(diǎn),并且要求整個(gè)盤點(diǎn)過程路徑最短[6-9]。
本文采用改進(jìn)A*算法計(jì)算路徑最短距離。A*算法是一種啟發(fā)式搜索算法,用于圖形平面上求解通過多個(gè)節(jié)點(diǎn)的最低成本,算法核心思想是在每次選擇下一個(gè)當(dāng)前搜索節(jié)點(diǎn)時(shí),從所有已經(jīng)探知的但未搜索過的節(jié)點(diǎn)中,選擇f值最小的節(jié)點(diǎn)進(jìn)行展開:f=g+h。f是A*算法的一個(gè)估值函數(shù),表示可能試探點(diǎn)的估值,f由2部分組成:①g表示從起始搜索點(diǎn)到當(dāng)前點(diǎn)的代價(jià);②h表示當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估值,本文中h采用節(jié)點(diǎn)的曼哈頓距離。
本文對A*算法的改進(jìn)主要包括以下幾點(diǎn):
(1)從某一節(jié)點(diǎn)出發(fā)到其他節(jié)點(diǎn)均可達(dá)(目標(biāo)節(jié)點(diǎn)不在closelist中),即所有節(jié)點(diǎn)開始時(shí)均在openlist中。
(2)由于起點(diǎn)和終點(diǎn)都是a0,為了方便說明,將終點(diǎn)定義成a0′。a0′對于所有節(jié)點(diǎn)均可達(dá),即a0′也在openlist中,但只有在所有的節(jié)點(diǎn)選擇完后,才能選擇a0′作為當(dāng)前節(jié)點(diǎn)。
(3)如果當(dāng)前節(jié)點(diǎn)的相鄰節(jié)點(diǎn)在openlist中,并且經(jīng)由當(dāng)前節(jié)點(diǎn)到達(dá)該相鄰節(jié)點(diǎn)的g值小于或者等于原來的g值,則將該相鄰節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn)。
(4)保存當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)數(shù)量(節(jié)點(diǎn)深度),在進(jìn)行g(shù)值比較時(shí),如果g值相等,則選擇深度較大的路徑。
(5)對于被選擇的當(dāng)前節(jié)點(diǎn)(在openlist中f值最小),若經(jīng)由該節(jié)點(diǎn)的相鄰節(jié)點(diǎn)的g值均不小于其原來的g值,則將該當(dāng)前節(jié)點(diǎn)繼續(xù)放入openlist中,選擇f值次小的節(jié)點(diǎn)繼續(xù)。
(6)如果openlist中剩余節(jié)點(diǎn)均未出現(xiàn)(3)中所述的情況,則選擇深度最大者作為當(dāng)前節(jié)點(diǎn)繼續(xù)。
多貨位盤點(diǎn)算法步驟如下:
(1)假設(shè)有a0,a1,…,an個(gè)節(jié)點(diǎn)需要盤點(diǎn),且節(jié)點(diǎn)坐標(biāo)為(xn,yn),則每個(gè)節(jié)點(diǎn)與起點(diǎn)的曼哈頓距離為h=xn+yn,節(jié)點(diǎn)之間的曼哈頓距離為h(am,an)=|xm-xn|+|ym-yn|。
(2)將所有節(jié)點(diǎn)放入openlist中(起始節(jié)點(diǎn)的f值和g值均為0)。
(3)在openlist中計(jì)算節(jié)點(diǎn)f值,選擇f值最小的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)。
(4)依次判斷當(dāng)前節(jié)點(diǎn)的每一個(gè)相鄰節(jié)點(diǎn),若該相鄰節(jié)點(diǎn)位于closelist中,則繼續(xù)檢驗(yàn)下一節(jié)點(diǎn);若該相鄰節(jié)點(diǎn)位于openlist中,則判斷經(jīng)由當(dāng)前節(jié)點(diǎn)到達(dá)該相鄰節(jié)點(diǎn)的g值是否不大于原來的g值,若是,則將該相鄰節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn),并重新設(shè)置該相鄰節(jié)點(diǎn)的g值和f值,且深度加1,轉(zhuǎn)到步驟(3)。
(5)若經(jīng)由當(dāng)前節(jié)點(diǎn)的所有相鄰節(jié)點(diǎn)的g值均不小于原來的g值,則將該節(jié)點(diǎn)繼續(xù)放入openlist中,但不參與下一次的f值比較;否則,將該當(dāng)前節(jié)點(diǎn)放入closelist中,并且深度加1。
(6)若openlist中剩余節(jié)點(diǎn)均不能使經(jīng)由它的相鄰節(jié)點(diǎn)的g值更小,則選擇深度最大的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)。
(7)當(dāng)openlist中只剩下a0′時(shí),循環(huán)結(jié)束。
(8)從a0′開始沿父節(jié)點(diǎn)遍歷,并保存整個(gè)遍歷到的節(jié)點(diǎn)坐標(biāo),遍歷所得節(jié)點(diǎn)即最后的路徑。
在給定節(jié)點(diǎn)的情況下,算法執(zhí)行時(shí)間與節(jié)點(diǎn)數(shù)量的關(guān)系如圖4所示。
由圖4可以看出,算法運(yùn)行時(shí)間隨著節(jié)點(diǎn)數(shù)量的增加而增加,在節(jié)點(diǎn)數(shù)量為120時(shí),算法運(yùn)行時(shí)間約為1s。由于導(dǎo)軌精度和安裝誤差的限制,節(jié)點(diǎn)的運(yùn)動(dòng)速度一般小于50cm/s,則盤點(diǎn)一個(gè)貨架上所有物品的時(shí)間需幾分鐘,所以算法的執(zhí)行時(shí)間滿足使用要求。事實(shí)上,當(dāng)倉庫規(guī)模較小,節(jié)點(diǎn)數(shù)量較大時(shí),節(jié)點(diǎn)分布成一定規(guī)律,往往可以采用單排盤點(diǎn)來完成部分貨位盤點(diǎn),再對剩下的少數(shù)貨位實(shí)行多貨位盤點(diǎn)。
圖4 算法執(zhí)行時(shí)間
節(jié)點(diǎn)原理圖如圖5所示。
圖5 節(jié)點(diǎn)原理圖
由圖5可知,二維移動(dòng)節(jié)點(diǎn)包括3個(gè)組成部分:PC無線節(jié)點(diǎn)、單片機(jī)無線節(jié)點(diǎn)和閱讀器無線節(jié)點(diǎn)。PC節(jié)點(diǎn)負(fù)責(zé)發(fā)送控制指令給單片機(jī)節(jié)點(diǎn)和閱讀器節(jié)點(diǎn);單片機(jī)控制通過發(fā)送指令給電機(jī),從而控制閱讀器的運(yùn)動(dòng);閱讀器讀取電子標(biāo)簽信息。節(jié)點(diǎn)工作基本流程如下(以單個(gè)盤點(diǎn)為例):PC節(jié)點(diǎn)接收單個(gè)盤點(diǎn)指令,通過無線模塊發(fā)送相應(yīng)的運(yùn)動(dòng)控制指令給單片機(jī),并設(shè)置等待時(shí)間wtime,若在等待時(shí)間內(nèi)沒有接收到應(yīng)答信號,則表示通信失敗,重新發(fā)送指令;如果單片機(jī)接收到指令,則會(huì)發(fā)送一個(gè)“接收成功”應(yīng)答信號,表示已接收到指令,并對伺服電機(jī)發(fā)送相應(yīng)的控制指令,控制節(jié)點(diǎn)移動(dòng);節(jié)點(diǎn)移動(dòng)完成后,單片機(jī)發(fā)送“操作成功”指令給PC節(jié)點(diǎn),表示閱讀器已經(jīng)運(yùn)動(dòng)到指定位置,可以開始讀卡操作;PC節(jié)點(diǎn)通過無線模塊發(fā)送信息讀取指令給閱讀器節(jié)點(diǎn),如果在等待時(shí)間內(nèi)未接收到應(yīng)答信號,則重新發(fā)送指令;如果閱讀器接收到指令,則發(fā)送“接收成功”應(yīng)答信號,開始進(jìn)行信息讀取,讀卡完成后,將讀取結(jié)果發(fā)送給PC節(jié)點(diǎn),PC節(jié)點(diǎn)對返回結(jié)果進(jìn)行相應(yīng)操作[10-11]。節(jié)點(diǎn)工作流程(主控模塊)如圖6所示。
圖6 節(jié)點(diǎn)工作流程圖
本文研究設(shè)計(jì)了一種基于RFID的數(shù)字貨架的二維移動(dòng)節(jié)點(diǎn),通過引入RFID技術(shù)、ZigBee通信技術(shù)和自動(dòng)控制技術(shù),降低了貨品信息獲取的成本,主要表現(xiàn)在:
(1)貨品信息讀取的自動(dòng)化。采用貨品信息的自動(dòng)讀取代替固定RFID讀卡器讀取方式。
(2)貨品定位,對貨架進(jìn)行劃分。通過節(jié)點(diǎn)的坐標(biāo)獲取貨品所在貨位的坐標(biāo)。
(3)貨品信息的實(shí)時(shí)盤點(diǎn)和更新。只需設(shè)置一個(gè)時(shí)間間隔,節(jié)點(diǎn)即可隨時(shí)對貨品進(jìn)行盤點(diǎn),并對貨品信息進(jìn)行更新。
同時(shí),在RFID讀卡器讀卡過程中,采用多次讀取方案,加上RFID讀卡器本身具有的防沖撞特性,使得讀卡成功率在99%以上,滿足實(shí)際應(yīng)用要求。
[1] 王建維,謝 勇,吳計(jì)生.基于RFID的數(shù)字化倉庫管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].物流技術(shù),2009,28(4):130-132.
[2] 朱俊英.電子貨架系統(tǒng)及物品監(jiān)控方法:中國,10117504.3[P].2010-03-04.
[3] 柳健龍.一種智能貨架系統(tǒng)及其實(shí)現(xiàn)方法:中國,10061936.0[P].2006-07-25.
[4] 汪鴻鵬,陸 陽,程運(yùn)安,等.基于Zigbee網(wǎng)絡(luò)的數(shù)字化倉庫設(shè)計(jì)[J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2011,34(12):1830-1835.
[5] 蔡志祥,劉冬生,曾曉雁.基于單片機(jī)的交流伺服電機(jī)控制系統(tǒng)[J].機(jī)械與電子,2005(5):28-30.
[6] 鄒 亮,徐建閩,朱玲湘.A*算法改進(jìn)及其在動(dòng)態(tài)最短路徑問題中的應(yīng)用[J].深圳大學(xué)學(xué)報(bào):理工版,2007,24(1):24,32-36.
[7] 石為人,王 楷.基于Floyd算法的移動(dòng)機(jī)器人最短路徑規(guī)劃研究[J].儀器儀表學(xué)報(bào),2009,30(10):2088-2092.
[8] 梁德恒,姚國祥,宮金龍.基于路由最短路徑樹的動(dòng)態(tài)多節(jié)點(diǎn)刪除算法[J].計(jì)算機(jī)工程,2011,37(5):121-123.
[9] 陳楚南,孫未未,陳 翀.基于圖嵌入框架的路網(wǎng)最優(yōu)路徑查詢算法[J].計(jì)算機(jī)研究與發(fā)展,2011,48(Z2):351-356.
[10] 韓金魯,孫同景.基于ZigBee技術(shù)的智能倉儲系統(tǒng)的研究[D].濟(jì)南:山東大學(xué),2008.
[11] 戚劍超,魏 臻.ZigBee樹型路由算法的改進(jìn)[J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2010,33(4):529-532,537.