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

有效

• 申請號: 201310332813.6
• 申請日: 2013-08-02
• 公開（公告）號: CN103415021A
• 公開（公告）日: 2013-11-27
• 發明（設計）人: 邵澤輝;葉安勝
• 申請（專利權）人: 成都大學
• 主分類號: H04W16/14
• 分類號: H04W16/14;H04W72/04;H04W84/18
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及信息通信領域如無線傳感網，尤其是一種基于可滿足性問題規約的無線頻率分配方法。

背景技術

隨著無線電技術的廣泛應用，無線傳感器網絡的快速發展，頻譜需求急速增長，頻譜資源日漸緊缺，無線傳感器網絡頻率的高效分配已成為一個亟需解決的難題。對于大規模無線通信網的組織可能會涉及到成百上千或更多的無線子網的規劃和維護，如何高效合理地利用有效的頻率資源，減少各子網之間的頻率干擾，提高無線通信網絡的服務質量，便于組織和運營將非常重要。那么如何提高頻譜的利用效率和應對無線傳感網絡中多節點頻率信息動態配置問題是其中的核心問題。

頻率分配問題作為資源優化問題急待人們的研究與解決，在國際上，人們提出了不少對頻率分配問題的算法，其主要思想是將其建立成圖的頂點著色模型和圖的L(2，1)標號問題。其中圖L(p，q)標號在通信網絡頻道設計方面有廣泛的應用，得到了國內外同行的高度重視和廣泛研究。頻率分配問題最早是由W.K.Hale于1980年提出的，即對每個無線電發射臺分配一個頻率使得相互干擾的無線電發射臺的頻率間隔在允許的范圍之內。Hale將此問題歸結為T-染色問題。T-染色問題在近二十年來得到廣泛的研究。為了解決無線電頻率分配問題，J.R.Griggs和R.K.Yeh于1992年提出了L(p，q)標號的概念.他們證明了對于一般圖的L(p，q)-標號問題是NP-完全問題。

目前頻率分配算法主要啟發式的搜索算法、貪心算法、回溯法、圖形理論算法、遺傳算法和神經網絡算法等，有些算法在固定的網絡結構如移動通信的蜂窩通信系統中得到了成功應用，但是不適合無線自組織的頻率規劃需求。現有的無線頻率分配技術有采用窮舉搜索的方法或多項式時間內求得頻率分配的最優解或基于圖著色模型的無線頻率分配方法，這些方法或無法保證得到沒有頻率沖突的最優解或求解周期長等。隨著無線傳感器網絡的快速發展，頻譜需求急速增長，頻譜資源日漸緊缺，無線傳感器網絡頻率的高效分配已成為一個亟需解決的難題。

發明內容

本發明的目的在于提供一種基于可滿足性問題規約的無線頻率分配方法，該方法提出一種新的求解無線傳感器網絡頻率的分配方法，并通過仿真實驗和理論分析來評價所設計系統的各項性能，其指標效果和性能均取得較大進展。

本發明通過下述技術方案實現：

一種基于可滿足性問題規約的無線頻率分配方法，包括以下步驟：

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

B)將無線子網抽象為無向網格圖的頂點，每一個子網對應一個頂點V_i(i＝1…n)，該無向網格圖的頂點集為{1，2，…，n}，無線子網之間的關聯被抽象為無向網格圖的邊E_j(j＝1…m)，將構成一個無向網格圖為G＝(V，E)；

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

進一步的，所述步驟C)的算法包括以下步驟：

D)設一組布爾變量x_i，j，其中1≤i≤n，1≤j≤k；x_i，j＝1，當且僅當頂點i著顏色j；

E)構建可滿足性規約問題模型

構造如下可滿足性規約問題的字句：

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

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

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

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

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

更進一步的，還包括以下步驟：

G)在可滿足性規約問題模型的基礎上加上新的約束，通過求解圖的獨立集問題可以得到每一種顏色最多的頂點個數；設顏色i的頂點數至多為c_i，加入下列約束：