祁士東

（蘭州交通大學(xué) 電子與信息工程學(xué)院， 甘肅蘭州 730070）

0 引言

RFID（Radio Frequency Identification），即射頻識(shí)別技術(shù)，是自動(dòng)識(shí)別技術(shù)的一種，通過無線射頻方式進(jìn)行非接觸雙向數(shù)據(jù)通信，對目標(biāo)加以識(shí)別并獲得相關(guān)數(shù)據(jù)。該技術(shù)作為本世紀(jì)十大重要技術(shù)之一，在國外的應(yīng)用已經(jīng)越來越普及，新加坡、韓國等國家都明確指出要重點(diǎn)發(fā)展電子標(biāo)簽技術(shù)和應(yīng)用，而中國是世界生產(chǎn)中心之一和最具潛力的消費(fèi)市場，對RFID的應(yīng)用需求也將越來越強(qiáng)烈。

目前，在多個(gè)標(biāo)簽和閱讀器應(yīng)用的場合，會(huì)產(chǎn)生標(biāo)簽和標(biāo)簽或者閱讀器和閱讀器之間的干擾，這種干擾我們叫作碰撞，本文就是應(yīng)用圖染色理論設(shè)計(jì)一種算法以避免閱讀器和閱讀器之間發(fā)生的碰撞。

1 RFID防沖突算法研究現(xiàn)狀

純ALOHA算法又稱為應(yīng)答器控制法,屬于隨機(jī)算法,是一種最簡單最基本的防沖突算法,屬于時(shí)分多址(TDMA)方式,易于實(shí)現(xiàn)多標(biāo)簽讀寫．電子標(biāo)簽只是循環(huán)地將ID發(fā)送給閱讀器，且標(biāo)簽發(fā)送數(shù)據(jù)（序列號(hào)）的重復(fù)周期幾乎相同，一個(gè)數(shù)據(jù)包即一串ID的傳輸時(shí)間t很短，僅占周期的一小部分，所以數(shù)據(jù)之間的傳輸會(huì)存在相對較長的時(shí)間間隔。因此，存在一定的概率，使得若干個(gè)電子標(biāo)簽?zāi)茉诓煌瑫r(shí)間段上傳輸數(shù)據(jù)，從而避免了沖突。

采用ALOHA算法的RFID系統(tǒng)特點(diǎn)是：系統(tǒng)簡單，隨機(jī)性大，沖突率高，系統(tǒng)利用率低，存在錯(cuò)誤判斷問題，僅適用于只讀型標(biāo)簽。

能使ALOHA法對比較的吞吐率最佳化的途徑就是時(shí)隙ALOHA法，此算法要求電子標(biāo)簽擁有一個(gè)唯一的序列號(hào)并且所有的標(biāo)簽必須由讀寫器控制，在規(guī)定的同步時(shí)隙內(nèi)傳輸數(shù)據(jù)包。讀寫器在周期性循環(huán)時(shí)隙內(nèi)發(fā)送讀寫信號(hào)，處于讀寫器工作范圍的標(biāo)簽被隨機(jī)分配到各個(gè)時(shí)隙。在每個(gè)時(shí)隙中，標(biāo)簽收到指令后把ID傳給讀寫器，當(dāng)一個(gè)時(shí)隙內(nèi)分配了多個(gè)標(biāo)簽時(shí)，就會(huì)產(chǎn)生沖突，讀寫器會(huì)跳過發(fā)生沖突的時(shí)隙直接找到有唯一標(biāo)簽的時(shí)隙。讀完后，繼續(xù)將時(shí)隙隨機(jī)地分配給標(biāo)簽，直到讀完所有標(biāo)簽。

采用時(shí)隙算法的ALOHA算法RFID系統(tǒng)的特點(diǎn)是：SA算法因?yàn)橛勺x寫器控制在同步時(shí)隙內(nèi)傳送數(shù)據(jù)，可能發(fā)生沖突的時(shí)間區(qū)就縮短了一半，吞吐率可達(dá)更高，較ALOHA算法增加了一倍，但仍局限于只讀型電子標(biāo)簽。

2 模型的建立

本模型基于TDMA（時(shí)分復(fù)用）模式，基于圖染色的RFID多閱讀器的防沖突算法，該技術(shù)方案主要包括：中央處理器、多個(gè)RFID讀寫器、電子標(biāo)簽。利用圖染色理論為每個(gè)閱讀器分配工作時(shí)隙，接著由中央處理器把時(shí)隙指令發(fā)送給每個(gè)閱讀器，以便每個(gè)閱讀器在其工作時(shí)隙時(shí)接收或發(fā)送數(shù)據(jù)。

將整個(gè)網(wǎng)絡(luò)看成一個(gè)無向圖，閱讀器則是這個(gè)網(wǎng)絡(luò)中的一個(gè)頂點(diǎn)，這里我們假設(shè)每個(gè)閱讀器的功率都是一樣的，其輻射的范圍自然全部一致，我們用半徑R來表示每個(gè)閱讀器的輻射范圍，當(dāng)兩個(gè)閱讀器之間的直徑距離大于2R時(shí)，這兩個(gè)閱讀器便不會(huì)產(chǎn)生沖突，我們把距離小于2R的兩個(gè)頂點(diǎn)之間連接一條邊，根據(jù)圖染色理論相鄰的兩個(gè)頂點(diǎn)不能染相同的顏色，這樣最后形成的圖中相沖突的點(diǎn)都染成不同的顏色，中央處理器根據(jù)各個(gè)沖突點(diǎn)為每個(gè)閱讀器分配時(shí)隙，使得在相同時(shí)隙工作的閱讀器都不沖突，以提高識(shí)別標(biāo)簽效率。

2.1 具體步驟：

1) 以二維坐標(biāo)（x，y）標(biāo)記每個(gè)閱讀器的位置，并向中央處理器輸入每個(gè)閱讀器的的位置信息；

2) 讓中央處理器形成閱讀器之間的沖突矩陣F；

3) 根據(jù)染色理論及沖突矩陣F，計(jì)算圖的度數(shù) d（v）；

4) 根據(jù)時(shí)隙分配算法，計(jì)算所需要的最大時(shí)隙數(shù)MaxSlot．

中央處理器根據(jù)輸入的閱讀器位置信息，閱讀器閱讀的半徑R，計(jì)算沖突矩陣F。該閱讀器沖突矩陣用于描述任意閱讀器之間是否存在沖突，假設(shè)閱讀器數(shù)目為n，則該矩陣為n×n，當(dāng)閱讀器i，j之間存在標(biāo)簽沖突時(shí)，即當(dāng)閱讀器i，j之間的距離 D（i，j）＜2R,則元素 F(i,j)=1;否則 F(i,j)=0。

2.2 時(shí)隙分配算法流程：

1) 在中處理器中用二維數(shù)組的形式把圖的各個(gè)頂點(diǎn)之間的關(guān)系聯(lián)系起來；

2) 對頂點(diǎn)的集合根據(jù)頂點(diǎn)的度數(shù)值從大到小的順序進(jìn)行排列；

3) 初始化色集合數(shù)和每個(gè)色集合的門限值,都用一維數(shù)組表示；

4) 從頂點(diǎn)集合中依次取出待染色的頂點(diǎn),進(jìn)入下一步,如果子頂點(diǎn)集合中待染色頂點(diǎn)全部取出,轉(zhuǎn)入步驟8)；

5) 將取出的頂點(diǎn)存入到第一個(gè)色集合中，從子頂點(diǎn)集合中刪除此頂點(diǎn)，返回步驟4)；

6) 添加一個(gè)新的色集合，添加其對應(yīng)的門限值;

7) 按照色集合中存入頂點(diǎn)數(shù)的多少，對色集合進(jìn)行從小到大的順序進(jìn)行排序,如果有新頂點(diǎn)進(jìn)入到色集合中，則返回到步驟4)，否則，進(jìn)入下一步；

8) 算法結(jié)束，輸出染色結(jié)果。

2.3 程序流程圖

算法的程序流程圖如圖1所示。

圖1 算法流程圖

輸出的染色結(jié)果就是我們需要給閱讀器分配的時(shí)隙，經(jīng)過本算法之后，能夠同時(shí)獲得時(shí)隙的閱讀器被分配到了同一個(gè)顏色集合當(dāng)中，而且本算法確保用最少的顏色給全部閱讀器分配時(shí)隙，保證了每個(gè)閱讀器在每個(gè)周期內(nèi)都至少能獲得一個(gè)時(shí)隙，不會(huì)出現(xiàn)死鎖的情況。

2.4 程序部分代碼

對無向圖進(jìn)行遍歷,利用兩個(gè)循環(huán)語句實(shí)現(xiàn):

For(m=0;m＜N;m++);

{

For(n=0;n＜N;n++)

{

If(adj[m][n]==1)

VCollection[n]=n;

If(m==VCollection[n])

Continue;

}

}

利用兩個(gè)循環(huán)語句來求出每個(gè)節(jié)點(diǎn)的度：

For（m=0 ；m＜N;m++）

{

Vdegree[0][m]=i+1;

For(n=0;n＜N;n++)

{

If(adj[m][n]==1)

{

Vdegree[1][m]=Vdegree[1][m]+1;

}

}

}

2.5 算法仿真及實(shí)驗(yàn)結(jié)果分析

由仿真結(jié)果可以看出采用基于染色思想的防沖突算法在標(biāo)簽數(shù)目越多，實(shí)驗(yàn)情況相同的前提下，其產(chǎn)生沖突的可能性越低，能更好地消除標(biāo)簽數(shù)目多時(shí)閱讀器產(chǎn)生沖突而帶來的降低信道利用率情況的發(fā)生。在實(shí)際情況中，標(biāo)簽的數(shù)量將遠(yuǎn)遠(yuǎn)多于實(shí)驗(yàn)所用的標(biāo)簽數(shù)量，基于圖染色思想防沖突算法的閱讀器之間的沖突比例比之前將進(jìn)一步降低。由仿真結(jié)果（見圖2）可看出在基于圖染色思想的防沖突算法的效率明顯得到提高，滿足本提出本算法最初的愿望，為RFID防沖突算法提供了一個(gè)新的研究方向。

圖2 仿真結(jié)果

2.6 算法評析

算法優(yōu)劣的一個(gè)評判標(biāo)準(zhǔn)就是算法的復(fù)雜度，本算法的算法復(fù)雜性主要集中在第二步～第五步，算法在第二步中對頂點(diǎn)度數(shù)由大到小整理的時(shí)間復(fù)雜度為O(n2) ，算法優(yōu)劣的另一個(gè)主要的指標(biāo)就是能否高效地解決亟待處理的問題，本文給出的算法不但能夠切實(shí)地解決沖突問題，還能夠解決其他算法難以解決的隱藏終端問題和暴露終端問題，并且本算法具有一定的可行性，基于TDMA方式的圖染色的時(shí)隙調(diào)度算法有效的提高了時(shí)隙的利用率。

3 結(jié)束語

本文只是針對多閱讀器識(shí)別沖突問題進(jìn)行了探討，實(shí)際上圖染色算法由于其確定性也得到了比較廣泛的應(yīng)用，所以在這方面應(yīng)該可以有更進(jìn)一步的研究。另外，沖突問題中不僅包括多閱讀器之間的沖突，還有多標(biāo)簽的沖突，閱讀器與電子標(biāo)簽之間的沖突，要使防沖突問題得到徹底的解決，需要根據(jù)實(shí)際應(yīng)用情況結(jié)合3類沖突問題綜合考慮，這條路還比較艱辛，需要在以后的工作中繼續(xù)研究，繼續(xù)學(xué)習(xí)，繼續(xù)鉆研。

[1] 張雷．基于均勻圖染色的無線傳感網(wǎng)絡(luò)廣播調(diào)度算法研究[D]．蘭州:蘭州交通大學(xué),2011．

[2] 陳衛(wèi)東．求圖著色問題的新算法[J]．微計(jì)算機(jī)應(yīng)用,2004,25(4):391-395．

[3] 趙煥平．若干圖的點(diǎn)可區(qū)別全染色的算法研究[D]．蘭州:蘭州交通大學(xué),2009．

[4] 許進(jìn),張軍英,保崢．基于Hopfield網(wǎng)絡(luò)的圖的染色算法[J]．電子學(xué)報(bào),1996,24(10):8-10．

[5] 田雙亮,李敬文,張忠輔．聯(lián)圖Cn∨Kn的鄰強(qiáng)邊色數(shù)[J]．山東大學(xué)學(xué)報(bào),2005,40(1):7-10．

[6] 唐宏,謝靜,魯玉芳,唐倫．無線傳感網(wǎng)絡(luò)原理及應(yīng)用[M]．北京:人民郵電出版社,2010．

[7] 李敬文,徐保根,李沐春,等．Pm∨ Cn的點(diǎn)可區(qū)別邊色數(shù)[J]．山東大學(xué)學(xué)報(bào),2008,43(8):24-30．

[8] Qin L,Hu Rongqiang．Intelligent Gain System Based on Complex and Dynamical Networks Model[C]．2007 IEEE Interna-tional Conference on Robotics and Biomimetics,ROB IO,2008:2018-2022．