基于圖染色思想的RFID防沖突算法研究

祁士東

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

0 引言

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

目前，在多個標簽和閱讀器應用的場合，會產生標簽和標簽或者閱讀器和閱讀器之間的干擾，這種干擾我們叫作碰撞，本文就是應用圖染色理論設計一種算法以避免閱讀器和閱讀器之間發生的碰撞。

1 RFID防沖突算法研究現狀

純ALOHA算法又稱為應答器控制法,屬于隨機算法,是一種最簡單最基本的防沖突算法,屬于時分多址(TDMA)方式,易于實現多標簽讀寫．電子標簽只是循環地將ID發送給閱讀器，且標簽發送數據（序列號）的重復周期幾乎相同，一個數據包即一串ID的傳輸時間t很短，僅占周期的一小部分，所以數據之間的傳輸會存在相對較長的時間間隔。因此，存在一定的概率，使得若干個電子標簽能在不同時間段上傳輸數據，從而避免了沖突。

采用ALOHA算法的RFID系統特點是：系統簡單，隨機性大，沖突率高，系統利用率低，存在錯誤判斷問題，僅適用于只讀型標簽。

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

采用時隙算法的ALOHA算法RFID系統的特點是：SA算法因為由讀寫器控制在同步時隙內傳送數據，可能發生沖突的時間區就縮短了一半，吞吐率可達更高，較ALOHA算法增加了一倍，但仍局限于只讀型電子標簽。

2 模型的建立

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

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

2.1 具體步驟：

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

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

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

4) 根據時隙分配算法，計算所需要的最大時隙數MaxSlot．

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

2.2 時隙分配算法流程：

1) 在中處理器中用二維數組的形式把圖的各個頂點之間的關系聯系起來；

2) 對頂點的集合根據頂點的度數值從大到小的順序進行排列；

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

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

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

6) 添加一個新的色集合，添加其對應的門限值;

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

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

2.3 程序流程圖

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

圖1 算法流程圖

輸出的染色結果就是我們需要給閱讀器分配的時隙，經過本算法之后，能夠同時獲得時隙的閱讀器被分配到了同一個顏色集合當中，而且本算法確保用最少的顏色給全部閱讀器分配時隙，保證了每個閱讀器在每個周期內都至少能獲得一個時隙，不會出現死鎖的情況。

2.4 程序部分代碼

對無向圖進行遍歷,利用兩個循環語句實現:

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;

}

}

利用兩個循環語句來求出每個節點的度：

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 算法仿真及實驗結果分析

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

圖2 仿真結果

2.6 算法評析

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

3 結束語

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

[1] 張雷．基于均勻圖染色的無線傳感網絡廣播調度算法研究[D]．蘭州:蘭州交通大學,2011．

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

[3] 趙煥平．若干圖的點可區別全染色的算法研究[D]．蘭州:蘭州交通大學,2009．

[4] 許進,張軍英,保崢．基于Hopfield網絡的圖的染色算法[J]．電子學報,1996,24(10):8-10．

[5] 田雙亮,李敬文,張忠輔．聯圖Cn∨Kn的鄰強邊色數[J]．山東大學學報,2005,40(1):7-10．

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

[7] 李敬文,徐保根,李沐春,等．Pm∨ Cn的點可區別邊色數[J]．山東大學學報,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．