限定K=1非對(duì)稱(chēng)輪詢系統(tǒng)的FPGA實(shí)現(xiàn)

路秀迎，丁洪偉，楊志軍，保利勇，何 敏

（云南大學(xué) 信息學(xué)院，昆明 650500）

無(wú)線傳感器網(wǎng)絡(luò)WSN（wireless sensor network）是由大規(guī)模隨機(jī)分布在監(jiān)控區(qū)域的微型傳感器節(jié)點(diǎn)組成的以數(shù)據(jù)為中心的任務(wù)型網(wǎng)絡(luò)，媒體接入控制 MAC（media access control）協(xié)議是聯(lián)接 WSN物理層與網(wǎng)絡(luò)層的紐帶，是保證節(jié)點(diǎn)之間高效通信的重要因素。

文獻(xiàn)[1-8]基于概率母函數(shù)與嵌入式馬爾可夫鏈的方法就平均排隊(duì)隊(duì)長(zhǎng)、輪詢周期、等待時(shí)延等性能指標(biāo)對(duì)對(duì)稱(chēng)式輪詢系統(tǒng)展開(kāi)分析，忽略了多樣性業(yè)務(wù)的信息非對(duì)稱(chēng)性與服務(wù)器處理差異性，僅適用于單一服務(wù)類(lèi)型的網(wǎng)絡(luò)應(yīng)用，大大限制了該技術(shù)的使用范圍和適用空間。研究非對(duì)稱(chēng)輪詢系統(tǒng)對(duì)WSN多業(yè)務(wù)應(yīng)用具有重要的理論意義與研究?jī)r(jià)值[9]。

FPGA基于硬件并行機(jī)制工作，具有半定制、非固化的特點(diǎn)，控制靈活，開(kāi)發(fā)周期短，運(yùn)行速度相比傳統(tǒng)串行計(jì)算CPU提高近100倍[10]，可將其作為異構(gòu)加速資源應(yīng)用于WSN，實(shí)現(xiàn)節(jié)點(diǎn)數(shù)據(jù)的實(shí)時(shí)處理，滿足了非對(duì)稱(chēng)WSN在軟硬件延展性、可移植性方面的要求。

系統(tǒng)采用限定K=1服務(wù)策略進(jìn)行輪詢調(diào)度，保證了簇內(nèi)傳感器節(jié)點(diǎn)之間訪問(wèn)介質(zhì)的公平性?；赒UARTUSⅡ平臺(tái)進(jìn)行功能測(cè)試，并對(duì)系統(tǒng)性能展開(kāi)理論與統(tǒng)計(jì)分析，結(jié)果表明該非對(duì)稱(chēng)輪詢系統(tǒng)能夠滿足多樣性業(yè)務(wù)服務(wù)質(zhì)量的彈性要求，具有更好的普適性。

1 理論介紹

非對(duì)稱(chēng)限定K=1輪詢系統(tǒng)的基本模型如圖1所示，系統(tǒng)由1個(gè)中央控制器與N個(gè)排隊(duì)隊(duì)列（終端）組成，各終端隨機(jī)變量所服從的概率分布不同，具體表現(xiàn)為以下幾點(diǎn)：

圖1 非對(duì)稱(chēng)輪詢系統(tǒng)示意Fig.1 Schematic diagram of asymmetric polling system

（1）到達(dá)各終端的信息分組服從泊松分布，其到達(dá)速率λi表示i號(hào)終端單位時(shí)間內(nèi)接收到信息分組的個(gè)數(shù)。終端之間信息分組到達(dá)率的隨機(jī)變量λi相互獨(dú)立且遵從不同的概率分布。其分布的概率母函數(shù)、均值、方差分別是

（2）各終端的服務(wù)時(shí)間βi表示各終端發(fā)送單位信息分組需要的時(shí)間，各終端服務(wù)時(shí)間的隨機(jī)變量βi相互獨(dú)立且服從不同的概率分布。其分布的概率母函數(shù)、均值、方差分別是

（3）控制器訪問(wèn)空閑終端i或服務(wù)完終端i后經(jīng)過(guò)時(shí)間γi查詢?cè)L問(wèn)終端i+1，相鄰終端之間的轉(zhuǎn)換時(shí)間的隨機(jī)變量γi相互獨(dú)立且服從不同的概率分布。其分布的概率母函數(shù)、均值、方差分別為R（z），

中央控制器按照物理連接的邏輯順序?qū)Ω鹘K端進(jìn)行輪詢?cè)L問(wèn)，訪問(wèn)到的非空終端享有信息發(fā)送權(quán)，否則經(jīng)過(guò)設(shè)定的轉(zhuǎn)換時(shí)間訪問(wèn)下一終端。獲得服務(wù)權(quán)限的終端按照限定K=1的服務(wù)規(guī)則發(fā)送數(shù)據(jù)，即每次只發(fā)送該終端緩存的1個(gè)信息分組。

評(píng)估輪詢系統(tǒng)性能的參數(shù)主要有平均排隊(duì)對(duì)長(zhǎng)和平均時(shí)延，文中采用內(nèi)嵌馬爾可夫鏈與概率母函數(shù)的方法對(duì)系統(tǒng)展開(kāi)理論分析，定義的隨機(jī)變量有：vi（n）為服務(wù)器對(duì) i號(hào)終端服務(wù)的時(shí)間，ui（n）為服務(wù)器從第i號(hào)終端轉(zhuǎn)向第i+1號(hào)終端的輪詢轉(zhuǎn)換時(shí)間，μj（ui）為在 ui（n）時(shí)間內(nèi)進(jìn)入第 j號(hào)終端的信息分組數(shù)，ηj（vi）為在 vi（n）時(shí)間內(nèi)進(jìn)入第 j號(hào)終端中的信息分組數(shù)。定義隨機(jī)變量ξi（n）為第i號(hào)終端站點(diǎn)在tn時(shí)刻其存儲(chǔ)器內(nèi)存儲(chǔ)的信息分組數(shù)，各終端服務(wù)強(qiáng)度 ρi（ρi=λiβi）。 那么排隊(duì)系統(tǒng)在 tn時(shí)刻的狀態(tài)可表示為［ξ1（n），ξ2（n），…，ξN（n），ξh（n）］，分布函數(shù)為

定義gi（j）為tn時(shí)刻第i號(hào)節(jié)點(diǎn)接受服務(wù)時(shí)，第j號(hào)節(jié)點(diǎn)平均存儲(chǔ)信息分組數(shù)，則有：

式中：i=1，2，…，N；j=1，2，…，N。

定義：

對(duì)式（1）求二階偏導(dǎo)可得：

由式（5）～式（8）求得：

圖2～圖4分別為非對(duì)稱(chēng)限定K=1服務(wù)輪詢系統(tǒng)的性能參數(shù)與到達(dá)率、服務(wù)時(shí)間、轉(zhuǎn)換時(shí)間之間的關(guān)系圖。圖2 中 N=4，λ2=0.0498，λ3=0.03，λ4=0.01，β1=4，β2=2，β3=1，β4=2，γ1=2，γ2=1，γ3=3，γ4=4；圖3 中N=4，λ1=0.0195，λ2=0.0498，λ3=0.03，λ4=0.01， β2=2，β3=1，β4=2，γ1=2，γ2=1，γ3=3，γ4=4； 圖4 中 N=4，λ1=0.0195，λ2=0.0498，λ3=0.03，λ4=0.01，β1=4，β2=2，β3=1，β4=2，γ2=1，γ3=3，γ4=4。

2 硬件實(shí)現(xiàn)

圖2 系統(tǒng)性能參數(shù)與到達(dá)率的關(guān)系Fig.2 Relation between system performance parameters and arrival rate

圖3 系統(tǒng)性能參數(shù)與服務(wù)時(shí)間的關(guān)系Fig.3 Relation between system performance parameters and service time

圖4 系統(tǒng)性能參數(shù)與轉(zhuǎn)換時(shí)間的關(guān)系Fig.4 Relation between system performance parameters and conversion time

設(shè)計(jì)中按照WSN簇內(nèi)通信的工作原理、采用“自頂向下”的設(shè)計(jì)方法把系統(tǒng)分為信源、節(jié)點(diǎn)、控制、接收4個(gè)模塊部分進(jìn)行硬件設(shè)計(jì)，圖5為系統(tǒng)設(shè)計(jì)框圖，表1為非對(duì)稱(chēng)系統(tǒng)相關(guān)參數(shù)值。

圖5 系統(tǒng)設(shè)計(jì)框圖Fig.5 Block diagram of the system

表1 系統(tǒng)設(shè)定參數(shù)值Tab.1 Values of the system parameters

2.1 信源模塊

信源模塊用于產(chǎn)生滿足馬爾科夫特性的信息分組，但在FPGA時(shí)序電路中難以實(shí)現(xiàn)“單位時(shí)隙產(chǎn)生具有泊松特性的多個(gè)信息分組”的精確控制，故設(shè)計(jì)中利用分頻技術(shù)并借助Matlab工具產(chǎn)生泊松文檔協(xié)同解決這一難題。利用自加1計(jì)數(shù)器原理設(shè)計(jì)地址譯碼電路，使得RAM在50 MHz時(shí)鐘源觸發(fā)下讀取泊松分布.mif文檔并完成原始信息在時(shí)序電路中的映射轉(zhuǎn)換，為便于區(qū)分，設(shè)計(jì)中基于計(jì)數(shù)器原理將讀取到的λ數(shù)值映射到電路中的λ個(gè)報(bào)文分組10 100 110，無(wú)效信息分組則轉(zhuǎn)換為00 000 000，信源產(chǎn)生的原始數(shù)據(jù)混合了有效信息分組與無(wú)效信息分組。

2.2 節(jié)點(diǎn)模塊

非對(duì)稱(chēng)輪詢系統(tǒng)中服務(wù)器對(duì)各終端業(yè)務(wù)服務(wù)效率不同，各終端實(shí)時(shí)緩存到達(dá)信息分組并在獲得服務(wù)權(quán)限時(shí)按照FCFS順序發(fā)送，實(shí)現(xiàn)時(shí)通過(guò)調(diào)用FPGA異步fifo解決讀寫(xiě)過(guò)程的速度匹配問(wèn)題和獨(dú)立控制問(wèn)題，其工作流程分緩存與發(fā)送兩部分分別進(jìn)行描述。

2.2.1 緩存功能

終端緩存信息分組過(guò)程即該終端dcfifo寫(xiě)入過(guò)程，各終端寫(xiě)時(shí)鐘源皆為50 MHz時(shí)鐘源，其工作過(guò)程：

（1）信源產(chǎn)生的混合數(shù)據(jù)經(jīng)過(guò)濾波電路，檢測(cè)到有效信息分組置寫(xiě)使能信號(hào)有效，否則無(wú)效；

（2）寫(xiě)使能信號(hào)有效時(shí)，dcfifo在寫(xiě)時(shí)鐘源觸發(fā)下把相應(yīng)的有效數(shù)據(jù)寫(xiě)入存儲(chǔ)器，從根本上杜絕了信息冗余問(wèn)題。

2.2.2 發(fā)送功能

非空節(jié)點(diǎn)獲得服務(wù)權(quán)限后按照 “先到先出”的順序發(fā)送已緩存數(shù)據(jù)，其讀時(shí)鐘源頻率特性與系統(tǒng)設(shè)定服務(wù)時(shí)間一致，其工作流程：

（1）根據(jù)控制信號(hào)與dcfifo工作特性設(shè)置下溢保護(hù)電路，防止存儲(chǔ)器讀空；

（2）節(jié)點(diǎn)服務(wù)信號(hào)有效時(shí)，dcfifo開(kāi)始輸出數(shù)據(jù)；

（3）各節(jié)點(diǎn)設(shè)置限定指示器，通過(guò)邊緣檢測(cè)判定該節(jié)點(diǎn)進(jìn)入服務(wù)狀態(tài)后，根據(jù)服務(wù)時(shí)間與系統(tǒng)工作頻率特性設(shè)計(jì)計(jì)數(shù)器，保證該節(jié)點(diǎn)發(fā)送一個(gè)信息分組（即經(jīng)過(guò)單位服務(wù)時(shí)間）后指示器指示信號(hào)為由高電平變?yōu)榈碗娖?，結(jié)束當(dāng)前服務(wù)。圖6為終端1限定指示器工作流程。

2.3 數(shù)據(jù)融合

輪詢系統(tǒng)基于資源共享理論控制各節(jié)點(diǎn)無(wú)競(jìng)爭(zhēng)接入網(wǎng)絡(luò)，保證同一時(shí)間內(nèi)只有1個(gè)通信節(jié)點(diǎn)占用信道，有效避免了各終端發(fā)送數(shù)據(jù)的碰撞問(wèn)題。簇首接收到簇內(nèi)節(jié)點(diǎn)的數(shù)據(jù)后按照相應(yīng)的算法進(jìn)行融合發(fā)送至總線上。

圖6 限定指示器工作流程Fig.6 Work flow chart of the limited indicator

2.4 控制模塊

按照WSN簇內(nèi)輪詢控制原理，利用有限狀態(tài)機(jī)在控制模塊分別設(shè)置了4個(gè)節(jié)點(diǎn)服務(wù)狀態(tài)與4個(gè)相鄰節(jié)點(diǎn)輪詢轉(zhuǎn)換狀態(tài)， 分別記為 s1，s2，s3，s4，jishu1，jishu2，jishu3，jishu4。 圖7 為控制模塊的狀態(tài)轉(zhuǎn)移圖，其中各狀態(tài)表示：

sn：站點(diǎn) n服務(wù)狀態(tài)，高電平有效；jishun：相鄰站點(diǎn)間轉(zhuǎn)換狀態(tài)；Crn：站點(diǎn)n限定指示器指示信號(hào)；Cntn：相鄰站點(diǎn)間轉(zhuǎn)換時(shí)間計(jì)時(shí)信號(hào)；kn：站點(diǎn)nFIFO空信號(hào)。

圖7 控制模塊狀態(tài)轉(zhuǎn)移圖Fig.7 State transition diagram of the control module

其具體工作過(guò)程：

（1）轉(zhuǎn)換時(shí)間γi到，控制器訪問(wèn)站點(diǎn)i+1的存儲(chǔ)容量，若該容量顯示非0，系統(tǒng)進(jìn)入si+1服務(wù)狀態(tài)，否則進(jìn)入jishui+1的轉(zhuǎn)換狀態(tài)。

（2）若站點(diǎn)i+1進(jìn)入si+1服務(wù)狀態(tài)，控制器根據(jù)該終端限定指示信號(hào)控制狀態(tài)轉(zhuǎn)移，若指示信號(hào)cri+1為低電平，系統(tǒng)進(jìn)入γi+2的轉(zhuǎn)換狀態(tài)，否則表示該終端的1個(gè)信息分組尚未發(fā)送完成，系統(tǒng)繼續(xù)si+1的服務(wù)狀態(tài)。

2.5 接收模塊

接收模塊利用同步控制信號(hào)進(jìn)行各節(jié)點(diǎn)發(fā)送數(shù)據(jù)信息的恢復(fù)，系統(tǒng)發(fā)送部分控制信號(hào)包含節(jié)點(diǎn)傳輸信息分組的時(shí)序信息，在接收端用同步控制信號(hào)作為同步fifo寫(xiě)使能信號(hào)便可從總線數(shù)據(jù)中正確恢復(fù)出各節(jié)點(diǎn)數(shù)據(jù)信息。

3 實(shí)驗(yàn)結(jié)果

按照上述硬件實(shí)現(xiàn)描述方法，對(duì)FPGA非對(duì)稱(chēng)限定服務(wù)輪詢系統(tǒng)編譯后于QUARTUSⅡ進(jìn)行功能仿真，圖8為系統(tǒng)仿真圖。

圖8 系統(tǒng)仿真圖Fig.8 System simulation diagram

仿真圖中clk信號(hào)是系統(tǒng)時(shí)鐘，clk1是clk四分頻后的時(shí)鐘信號(hào)，也是系統(tǒng)工作的基準(zhǔn)時(shí)鐘；cp信號(hào)是服務(wù)器輪詢相鄰站點(diǎn)的轉(zhuǎn)換時(shí)間信號(hào)，高電平有效；s信號(hào)是站點(diǎn)服務(wù)信號(hào)，高電平有效；cr信號(hào)為限定指示器的繼續(xù)讀取信號(hào)，高電平有效；d信號(hào)是服務(wù)器輸出信號(hào)；r信號(hào)是接收端恢復(fù)信號(hào)；pbus信號(hào)是總線信號(hào)；use信號(hào)是各站點(diǎn)存儲(chǔ)器緩存的數(shù)據(jù)容量信號(hào)；

由仿真圖得：

（1）各終端的服務(wù)時(shí)間設(shè)定值是 4、2、1、2，限定指示器在檢測(cè)到服務(wù)信號(hào)有效后變?yōu)楦唠娖?，在相?yīng)節(jié)點(diǎn)單位服務(wù)時(shí)間到達(dá)前電平置低?？刂颇K在時(shí)鐘源觸發(fā)下檢測(cè)到cr信號(hào)失效后置其服務(wù)信號(hào)為低電平。仿真圖中發(fā)送單位信息分組占據(jù)時(shí)隙數(shù)與設(shè)定值一致，表明系統(tǒng)實(shí)現(xiàn)了限定K=1服務(wù)規(guī)則的要求。

（2）系統(tǒng)服務(wù)過(guò)程中各終端服務(wù)信號(hào)與其輸出信號(hào)在時(shí)鐘控制下同步動(dòng)作，高電平有效，相應(yīng)的終端輸出信息分組，實(shí)現(xiàn)了各終端存儲(chǔ)器緩存與發(fā)送的功能。

（3）輪詢系統(tǒng)工作過(guò)程分為相鄰站點(diǎn)轉(zhuǎn)換過(guò)程與站點(diǎn)服務(wù)過(guò)程，圖中cp信號(hào)與s信號(hào)交互出現(xiàn)，cp信號(hào)占據(jù)時(shí)隙個(gè)數(shù)分別為2、1、3、4，驗(yàn)證了控制模塊設(shè)計(jì)的正確性；

（4）系統(tǒng)接收信號(hào)與發(fā)送信號(hào)一致，時(shí)間延時(shí)2時(shí)隙，實(shí)現(xiàn)了系統(tǒng)對(duì)發(fā)送數(shù)據(jù)的正確接收功能。

表2～表3為系統(tǒng)性能參數(shù)（平均排隊(duì)對(duì)長(zhǎng)與平均時(shí)延）理論值與統(tǒng)計(jì)值的對(duì)比表。

表2 各節(jié)點(diǎn)平均排隊(duì)隊(duì)長(zhǎng)理論值與統(tǒng)計(jì)值對(duì)比表Tab.2 Comparison of theoretical value and statistical value of average queue length of each node

表3 各節(jié)點(diǎn)平均時(shí)延統(tǒng)計(jì)值與理論值對(duì)比表Tab.3 Comparison of theoretical value and statistical value of average time delay of each node

根據(jù)表2～表3中，得出：

（1）系統(tǒng)參數(shù)統(tǒng)計(jì)值與理論值在誤差允許范圍內(nèi)相一致，驗(yàn)證了設(shè)計(jì)的可行性與正確性；

（2）系統(tǒng)各節(jié)點(diǎn)平均排隊(duì)隊(duì)長(zhǎng)與平均時(shí)延均隨著到達(dá)率增加而提高，不會(huì)出現(xiàn)高并發(fā)忙碌節(jié)點(diǎn)的相位滯留，反映了系統(tǒng)為各節(jié)點(diǎn)提供服務(wù)的公平性；

（3）各節(jié)點(diǎn)平均排隊(duì)隊(duì)長(zhǎng)與平均時(shí)延均隨著到達(dá)率增加而非線性提高，這是由于系統(tǒng)節(jié)點(diǎn)工作的非對(duì)稱(chēng)性決定的，更適用于多業(yè)務(wù)應(yīng)用。

4 結(jié)語(yǔ)

本文根據(jù)WSN網(wǎng)絡(luò)應(yīng)用中服務(wù)類(lèi)型多樣化、信息傳遞不對(duì)稱(chēng)的工作特點(diǎn)，首次基于FPGA對(duì)非對(duì)稱(chēng)限定K=1輪詢系統(tǒng)進(jìn)行了硬件實(shí)現(xiàn)，對(duì)系統(tǒng)信息分組到達(dá)率、服務(wù)時(shí)間、轉(zhuǎn)換時(shí)間等工作特性參數(shù)設(shè)置非一致性數(shù)值，采用限定K=1服務(wù)策略實(shí)現(xiàn)WSN的輪詢MAC層控制，保證了簇區(qū)域內(nèi)節(jié)點(diǎn)之間介質(zhì)訪問(wèn)的公平性，時(shí)延特性優(yōu)良。功能測(cè)試與統(tǒng)計(jì)分析結(jié)果驗(yàn)證了設(shè)計(jì)的可行性，穩(wěn)定性強(qiáng)，可拓展性高，對(duì)WSN多業(yè)務(wù)應(yīng)用有更大的實(shí)用價(jià)值。