[發明專利]基于圖染色法的RFID多讀寫器防沖突方法

有效

• 申請號: 200810032490.8
• 申請日: 2008-01-10
• 公開（公告）號: CN101216875A
• 公開（公告）日: 2008-07-09
• 發明（設計）人: 王俊宇;劉丹;魏鵬;周曉方;閔昊
• 申請（專利權）人: 復旦大學
• 主分類號: G06K7/00
• 分類號: G06K7/00
• 代理公司: 上海正旦專利代理有限公司
• 代理人: 陸飛;盛志范

1.一種基于圖染色法的RFID多讀寫器防沖突方法，其特征在于，包括：

步驟一，以二維坐標(x，y)表示每個讀寫器的位置，并向中央控制器輸入每個讀寫器天線坐標的分布信息；

步驟二，中央控制器計算讀寫器之間的標簽沖突矩陣T、頻率沖突矩陣F；

步驟三，根據圖染色理論，及標簽沖突矩陣T，計算參數約束數t(v)、度數d(v)；

步驟四，調用時隙分配算法，計算所需最大時隙數max_slot，并為每個讀寫器分配相應的時隙編號slot_num；

步驟五，根據圖染色理論、頻率沖突矩陣F，及相關參數約束數t(v)，度數d(v)；

步驟六，調用信道分配算法，為每個讀寫器分配相應的信道編號channel_num；

步驟七，將時隙分配算法、信道分配算法的計算結果(最大時隙數max_slot、每個讀寫器分配所得的時隙編號slot_num，每個讀寫器分配所得的信道編號channel_num)發送給每個讀寫器。

2.根據權利要求1所述的基于圖染色法的RFID多讀寫器防沖突方法，所述步驟一的標簽沖突矩陣T，其特征在于：用于描述任意兩個讀寫器之間是否存在標簽沖突，假設讀寫器數目為n，則該矩陣為n×n，當讀寫器i，j之間存在標簽沖突時，即當讀寫器i，j之間的距離D(I，j)＜2R，則元素T(i，j)＝1；否則，T(i，j)＝0；其中，R為讀寫器閱讀標簽的半徑。

3.根據權利要求1所述的基于圖染色法的RFID多讀寫器防沖突方法，所述步驟一的頻率沖突矩陣F，其特征在于：表示存在且僅存在頻率沖突的讀寫器之間的最小信道約束數，假設讀寫器數目為n，則該矩陣為n×n，。頻率距離約束條件為，相隔就n個信道，兩讀寫器不發生頻率沖突的距離為dn，

讀寫器i，j的距離d1＜D(i，j)，則F(i，j)＝0，表示讀寫器i，j之間不存在頻率沖突；

讀寫器i，j的距離d2＜D(i，j)＜＝d1，則F(i，j)＝1；

讀寫器i，j的距離d3＜D(i，j)＜＝d2，則F(i，j)＝2；

讀寫器i，j的距離d4＜D(i，j)＜＝d3，則F(i，j)＝3；

讀寫器i，j的距離D(i，j)＜＝d4，則F(i，j)＝4。

4.根據權利要求1所述的基于圖染色法的RFID多讀寫器防沖突方法，所述步驟二中約束數t(v)為1，度數d(v)為與頂點v相連的邊的條數。

5.根據權利要求1所述的基于圖染色法的RFID多讀寫器防沖突方法，所述步驟四中時隙分配算法包括，

步驟一，根據讀寫器分布和標簽沖突矩陣T，將存在標簽沖突的讀寫器之間用邊e連接起來，邊的取值為1；根據約束數t(v)對讀寫器進行排序；

步驟二，給約束數t(v)最大的讀寫器選擇時隙編號1，若不止一個，則選擇其中度數d(v)最大的，若還不止一個，則任意選一個讀寫器，并且更新相應的參數，包括：可用時隙集R(v)、可用時隙個數r(v)、不可用時隙集Uf(v)、不可用時隙個數1f(v)、讀寫器的序號n(v)；

步驟三，在未著色的讀寫器中，不可用顏色個數1f(v)最大的，若不止一個，選擇約束數t(v)最大的，若還不止一個，選擇度數d(v)最大的，若還不止一個，則任意選一個讀寫器，設該讀寫器為v；

步驟四，若讀寫器v的著色序號n(v)≤4，則轉至步驟五；否則，n(v)＞4，判斷讀寫器v的類型：若r(v)＞＝1，則執行步驟五，否則，執行回溯換色子程序；

步驟五，對選出的讀寫器v著以可選用的，色號盡可能小的顏色，若R(v)不為空集合，則R(v)中的顏色優先；

步驟六，若所有的讀寫器都已著色，則停止；否則，返回步驟三。

6.根據權利要求1所述的基于圖染色法的RFID多讀寫器防沖突方法，所述步驟五中約束數t(v)為與頂點v相連的邊中取值最大的邊的值，度數d(v)為與頂點v相連的邊的條數。