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

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

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

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

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

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

1 理論介紹

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

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

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

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

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

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

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

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

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

定義：

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

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

圖2～圖4分別為非對稱限定K=1服務(wù)輪詢系統(tǒng)的性能參數(shù)與到達率、服務(wù)時間、轉(zhuǎn)換時間之間的關(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 硬件實現(xiàn)

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

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

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

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

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

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

2.1 信源模塊

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

2.2 節(jié)點模塊

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

2.2.1 緩存功能

終端緩存信息分組過程即該終端dcfifo寫入過程，各終端寫時鐘源皆為50 MHz時鐘源，其工作過程：

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

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

2.2.2 發(fā)送功能

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

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

（2）節(jié)點服務(wù)信號有效時，dcfifo開始輸出數(shù)據(jù)；

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

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

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

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

2.4 控制模塊

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

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

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

其具體工作過程：

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

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

2.5 接收模塊

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

3 實驗結(jié)果

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

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

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

由仿真圖得：

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

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

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

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

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

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

表3 各節(jié)點平均時延統(tǒng)計值與理論值對比表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)計值與理論值在誤差允許范圍內(nèi)相一致，驗證了設(shè)計的可行性與正確性；

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

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

4 結(jié)語

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