[發(fā)明專利]一種基于可滿足性問題規(guī)約的無線頻率分配方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310332813.6
• 申請(qǐng)日: 2013-08-02
• 公開（公告）號(hào): CN103415021A
• 公開（公告）日: 2013-11-27
• 發(fā)明（設(shè)計(jì)）人: 邵澤輝;葉安勝
• 申請(qǐng)（專利權(quán)）人: 成都大學(xué)
• 主分類號(hào): H04W16/14
• 分類號(hào): H04W16/14;H04W72/04;H04W84/18
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于可滿足性問題規(guī)約的無線頻率分配方法，其特征在于，包括以下步驟：

A)在給定的頻率使用范圍內(nèi)，檢測(cè)或篩選出所有可用的頻率，設(shè)定K個(gè)可用頻率為1，2，3，4，…，k，用顏色集{1，…，k}表示；

B)將無線子網(wǎng)抽象為無向網(wǎng)格圖的頂點(diǎn)，每一個(gè)子網(wǎng)對(duì)應(yīng)一個(gè)頂點(diǎn)V_i(i＝1…n)，該無向網(wǎng)格圖的頂點(diǎn)集為{1，2，…，n}，無線子網(wǎng)之間的關(guān)聯(lián)被抽象為無向網(wǎng)格圖的邊E_j(j＝1…m)，將構(gòu)成一個(gè)無向網(wǎng)格圖為G＝(V，E)；

C)在給定網(wǎng)格圖上，建立一種算法給每一個(gè)頂點(diǎn)分配一種顏色，要求滿足：距離是2的兩個(gè)頂點(diǎn)的顏色差至少為1，距離是1的兩個(gè)頂點(diǎn)的顏色差至少為2；所述顏色號(hào)代表頻率，意味著無線傳感器網(wǎng)絡(luò)中距離近的結(jié)點(diǎn)頻率差要大于給定的值，且距離越近頻率差越大，從而避免網(wǎng)絡(luò)中因頻率較近產(chǎn)生的頻率干擾問題。

2.根據(jù)權(quán)利要求1所述一種基于可滿足性問題規(guī)約的無線頻率分配方法，其特征在于，所述步驟C)的算法包括以下步驟：

D)設(shè)一組布爾變量x_i，j，其中1≤i≤n，1≤j≤k；x_i，j＝1，當(dāng)且僅當(dāng)頂點(diǎn)i著顏色j；

E)構(gòu)建可滿足性規(guī)約問題模型

構(gòu)造如下可滿足性規(guī)約問題的字句：

1≤v≤n??????????????????????(1)

1≤v≤n，1≤i＜j≤k???????????????????(2)

當(dāng)|i-j|＜1且d(u，v)＝2或者|i-j|＜2且d(u，v)＝1時(shí)??(3)

字句(1)保證每個(gè)頂點(diǎn)至少著一種顏色，字句(2)保證每個(gè)頂點(diǎn)不能著兩種或兩種以上的顏色，字句(3)保證距離是2的兩個(gè)頂點(diǎn)的顏色差至少為1，距離是1的兩個(gè)頂點(diǎn)的顏色差至少為2；

F)當(dāng)所有的字句都滿足時(shí)，就得到了一種可滿足的解，從而通過解碼得到了圖的頂點(diǎn)的顏色分配方案。

3.根據(jù)權(quán)利要求2所述一種基于可滿足性問題規(guī)約的無線頻率分配方法，其特征在于，還包括以下步驟：

G)在可滿足性規(guī)約問題模型的基礎(chǔ)上加上新的約束，通過求解圖的獨(dú)立集問題可以得到每一種顏色最多的頂點(diǎn)個(gè)數(shù)；設(shè)顏色i的頂點(diǎn)數(shù)至多為c_i，加入下列約束：

Σv=1nxv,i≤ci,]]>

通過約束的增加，然后采用超級(jí)SAT求解器進(jìn)行求解，從而大大加快運(yùn)算速度。