一種信道分配方法及裝置製造方法
2023-06-01 20:22:51 3
一種信道分配方法及裝置製造方法
【專利摘要】本發明公開了一種信道分配方法及裝置，主要內容為：確定與無線網狀網中每一節點對應的候選節點集，根據約束條件，確定所有候選節點集信道分配方案；從中選擇一個信道分配方案，在選擇的信道分配方案下，所有候選節點集間的鏈路幹擾最小，將為節點所屬的每一候選節點集分配的信道均作為給該節點分配的信道。由於採用候選節點集為信道分配單位，且選擇的信道分配方案是使所有候選節點集間的鏈路幹擾最小的候選節點集信道分配方案，最後，再根據候選節點集的信道分配方案確定節點的信道分配方案，因此，獲得的節點的信道分配方案減少了候選節點集間的路由衝突，在保留候選節點和偷聽機會的同時，兼顧了多信道的並發傳輸，進而提高了信道的吞吐量。
【專利說明】一種信道分配方法及裝置
【技術領域】
[0001]本發明涉及無線網狀網絡【技術領域】，尤其涉及一種信道分配方法及裝置。
【背景技術】
[0002]多跳無線網絡是無線區域網(Wireless Local Area Networks, WLAN)的擴展,能有效彌補WLAN覆蓋範圍小、傳輸距離有限、自由組網和施工困難的問題，具有更低部署成本，更大覆蓋範圍，能提供經濟的網絡接入服務。如何通過有效的技術手段，如路由協議和信道分配來提升多跳無線網絡的容量是一直以來備受關注的熱門領域。
[0003]其中機會路由是多跳無線網絡中新興的路由方式，它利用無線媒介廣播性質和多用戶分集，不事先確定路由的下一跳，直接廣播發送數據包，周圍可能有多個鄰居節點都正確收到數據包。在收到數據包的節點間進行某種協調，由其中一個離目的節點最「近」的節點繼續轉發。當然並不是所有的節點都參與，機會路由按某種規則選擇其中的一部分參加，這些被選中的鄰居節點稱為候選節點或候選轉發節點。經多方驗證，與只有一個預先設定下一跳的傳統固定路由相比，機會路由這種使用多個候選節點轉發數據包的方式更能適應不可靠的無線鏈路，尤其能充分利用遠距離和高丟失率的無線鏈路，能明顯提升多跳無線網絡，尤其是無線網狀網的端到端吞吐量。
[0004]然而，機會路由的一對多傳輸方式使得利用現有的統一信道分配方法進行信道分配或與傳統路由兼容的傳統信道分配方法時，存在信道分配的吞吐量不高的問題。
[0005]例如:在4個節點的網絡拓撲中每個節點配備2個無線射頻，可用信道數為3。源節點為S，目的節點為D，S的候選節點為D，A，B。圖1為傳統最小化鏈路幹擾的信道分配結果，圖2為統一信道分配結果，網絡中所有節點都使用完全相同的信道，例中所有節點都只使用信道I和信道2。其中，節點間的虛線邊表示鏈路，邊上的值為鏈路包投遞率，實線表示信道Cl，帶一點的虛線表示信道C2，帶兩點的虛線表示信道C3。使用多射頻多信道機會路由吞吐量EMORE分析模型對兩種信道分配下的吞吐量進行分析，傳統信道分配的吞吐量可達0.5，統一信道分配可達0.6475。
[0006]傳統信道分配利用多信道的並發傳輸來獲得更高的吞吐量，但從圖1中可看出傳統信道分配後可能出現以下缺點:I)切斷節點與某些候選節點的鏈路，如鏈路AB，這是節點與候選節點沒有共享信道造成的；2)以某信道發送時，候選節點數目變少，如S以Cl發送，B無法成為其候選節點，候選節點只剩A和D，導致機會路由的偷聽機會減少；主要原因是傳統信道分配是通過最小化邊與邊之間的幹擾來增加並發傳輸進而獲得更高的吞吐量。這是是基於鏈路的幹擾模型，這與傳統路由的一對一的傳輸方式和以一條鏈路為傳輸單元的性質完全吻合。但機會路由利用無線傳輸的廣播特性，是一對多的傳輸方式，一個傳輸單元存在多條鏈路，因此傳統信道分配方式與機會路由需要多個候選節點衝突。
[0007]統一信道分配完全使用相同的信道，雖然與傳統信道分配相比存在較多信道衝突，可並發的傳輸較少，但卻保留了候選節點和偷聽機會。在這個例子中雖然保留候選節點的統一信道分配比利用並發傳輸傳統信道分配吞吐量高，但是傳統信道分配只關注了多信道，統一信道分配只關注了機會路由，也就只獲得了其中一種技術帶來的好處，因而現有技術的信道分配方案在針對使用機會路由及多信道的無線網絡網中存在不能兼顧並發傳輸和保留候選節點和偷聽機會的問題，這在某種程度上使得無線網狀網的吞吐量較低。
【發明內容】
[0008]本發明實施例提供一種信道分配方法及裝置，用以解決現有的信道分配方案中存在不能兼顧並發傳輸和保留候選節點和偷聽機會的問題。
[0009]一種信道分配方法，所述方法包括:
[0010]確定與無線網狀網中每一節點對應的候選節點集，所述與每一節點對應的候選節點集包含該節點和該節點的候選節點；
[0011 ] 根據候選節點集信道分配數目約束條件和各節點的射頻接口數目約束條件，確定所有可行的候選節點集信道分配方案；
[0012]從所有可行的候選節點集信道分配方案中選擇一個信道分配方案，其中，在選擇的所述信道分配方案下，所有候選節點集間的鏈路幹擾最小，所有候選節點集間的鏈路幹擾是指候選節點集中兩兩個候選節點集間的鏈路幹擾的總和，所述兩兩候選節點集間的鏈路幹擾是指一候選節點集中包含的節點構成的鏈路與另一候選節點集中包含的節點構成的鏈路之間的幹擾；
[0013]將為節點所屬的每一候選節點集分配的信道均作為給該節點分配的信道。
[0014]一種信道分配裝置，所述裝置包括:
[0015]候選節點集確定模塊，用於確定與無線網狀網中每一節點對應的候選節點集，所述與每一節點對應的候選節點集包含該節點和該節點的候選節點；
[0016]候選節點集信道分配方案確定模塊，用於根據候選節點集信道分配數目約束條件和各節點的射頻接口數目約束條件，確定所有可行的候選節點集信道分配方案；
[0017]信道分配方案選擇模塊，用於從所有可行的候選節點集信道分配方案中選擇一個信道分配方案，其中，在選擇的所述信道分配方案下，所有候選節點集間的鏈路幹擾最小，所有候選節點集間的鏈路幹擾是指候選節點集中兩兩個候選節點集間的鏈路幹擾的總和，所述兩兩候選節點集間的鏈路幹擾是指一候選節點集中包含的節點構成的鏈路與另一候選節點集中包含的節點構成的鏈路之間的幹擾；
[0018]節點信道分配模塊，用於將為節點所屬的每一候選節點集分配的信道均作為給該節點分配的信道。
[0019]在本發明實施例的方案中，由於在進行信道分配時，採用候選節點集為信道分配單位，並且選擇的候選節點集信道分配方案是使所有候選節點集間的鏈路幹擾最小的候選節點集信道分配方案，最後，再根據候選節點集的信道分配方案確定節點的信道分配方案，因此，獲得的節點的信道分配方案減少了候選節點集間的路由衝突，在保留候選節點和偷聽機會的同時，兼顧了多信道的並發傳輸，進而提高了信道的吞吐量。
【專利附圖】
【附圖說明】
[0020]圖1為本發明【背景技術】中傳統最小化鏈路幹擾的信道分配結果示意圖；
[0021]圖2為本發明【背景技術】中的統一信道分配結果示意圖；
[0022]圖3為本發明實施例中的傳統路由的邊衝突示意圖；
[0023]圖4為本發明實施例中的機會路由的衝突示意圖；
[0024]圖5為本發明實施例一中的無線網狀網結構示意圖；
[0025]圖6為本發明實施例一中的信道分配方法流程圖；
[0026]圖7 Ca)為本發明實施例一中的節點鄰居示意圖；
[0027]圖7 (b)為本發明實施例一中的鏈路幹擾示意圖；
[0028]圖7 (C)為本發明實施例一中的候選節點集幹擾示意圖；
[0029]圖7 Cd)為本發明實施例一中的候選節點集幹擾示意圖；
[0030]圖8為本發明實施例一中的確定候選節點集之間的幹擾關係的流程圖；
[0031]圖9為本發明實施例二中的無線網狀網拓撲結構示意圖；
[0032]圖10為本發明實施例三中的信道分配裝置結構示意圖；
[0033]圖11為本發明實施中不同信道分配方法平均為CFS分配的信道數；
[0034]圖12為本發明實施中不同信道分配方法的平均幹擾值；
[0035]圖13為本發明實施中不同信道分配方法在重負載下吞吐量；
[0036]圖14為本發明實施中所有匯聚吞吐量的累積分布圖。
【具體實施方式】
[0037]為清楚地說明本發明實施例的方案，首先結合基於【背景技術】中所述的網絡拓撲的傳統路由的邊衝突圖和基於【背景技術】中所述的網絡拓撲的機會路由的衝突圖對本發明實施例中的信道分配的基本原理進行說明。
[0038]基於鏈路或邊幹擾對應的邊衝突圖如圖3所示，網絡拓撲圖中的連結轉變成邊衝突圖中的節點，網絡拓撲圖相互幹擾的兩條鏈路對應到邊衝突圖中的兩個節點間存在一條邊。傳統信道分配基於這一種鏈路的衝突圖，通過給鏈路分配信道來最小鏈路之間存在的幹擾。
[0039]機會路由衝突圖如圖4所示，機會路由衝突圖中的節點還是網絡拓撲圖中的節點，但每個節點包含節點會使用到的鏈路集合，即機會路由的本節點為發送節點和候選節點間的鏈路集合，所以目的節點沒有對應的節點。只要節點間的鏈路集合存在幹擾，兩個節點對應存在一條邊。
[0040]在傳統的路由方式中鏈路SA和SB，AB和AD是相互衝突。而機會路由由於存在多個候選節點，允許鏈路SA和SB，AB和AD共存。根據機會路由衝突圖的分析，機會路由中進行信道分配時應該把一個節點的多個候選節點綁定為一個整體進行分配，如把節點和該節點的多個候選節點構成的整體稱為一個候選節點集，那麼主要解決地就問題就從給鏈路分配信道，變成了給候選節點集分配信道，進行信道分配時應該把候選節點集作為一個信道分配單元進行分配。通過給候選節點集分配信道來儘量減少候選節點集與候選節點集之間的幹擾，來提升機會路由性能。根據這一思路在面向使用一對多的傳輸方式的機會路由時，本發明實施例提出的信道分配方案是一種基於候選節點集的信道分配方案。
[0041]下面結合具體實施例詳細描述本發明方案。
[0042]通常的，可以用一個擴展的無向圖G=(V，E，R，K)來表示如圖5所示的包含N個節點的多射頻多信道無線網狀網，其中V表示N個節點集，E表示節點間鏈路的矩陣，R表示每個節點可配置個無線射頻數目(也即射頻接口或無線接口，假設所有節點配置的射頻數量相等時)，K表示無線網狀網中可使用的正交信道的數目。
[0043]針對上述描述的無線網狀網，本發明實施例一的信道分配方法流程圖，如圖6所示，包括以下步驟:
[0044]步驟101:確定與無線網狀網中每一節點對應的候選節點集。
[0045]所述與每一節點對應的候選節點集包含該節點和該節點的候選節點；在一條流的源節點和目的節點已知時，利用機會路由的路由判據即可確定與每一節點對應的候選節點，並且在與每一節點對應的候選節點已知時，機會路由可以確定該條流的路由。
[0046]所述路由機判據可以為:期望傳輸次數(Expected Transmiss1n Count,ETX)、期望任意傳輸次數(Expected Anypath Transmiss1n Count, EAX)、期望傳輸時間(ExpectedTransmiss1n Time, ETT)或期望任意傳輸時間(Expected Anypath Transmiss1n Time,EATT )等。
[0047]其中，路由判據是負責選路，機會路由是選好路後，來確定路上的節點之間如何傳輸。
[0048]所述ETX是路徑選擇過程中一個衡量鏈路質量的確切數值。單獨一條鏈路的ETX值定義為數據包在這條鏈路上成功發送時的期望發送次數(包括重傳)。
[0049]在機會路由中，每個節點i都對應多個候選節點FN(i)，那麼節點i與它的候選節點FN⑴可以構成一個候選節點集(Candidate Forwarder Set,CFS),這個候選節點集中的所有節點組成的鏈路構成一個候選鏈路集(也可以說候選節點集中的所有節點組成的邊構成一個候選邊集，本發明實施例中不區分邊和鏈路、頂點和節點)。若節點i的候選節點包括節點I和節點2，節點P的候選節點包括節點3和節點4。那麼節點1、節點2節點和節點i構成節點i的一個候選節點集，節點3、節點4和節點P構成節點P的候選節點集。所有候選節點集構成候選節點集的集合(Set of Candidate Forwarder Sets, CFSs)。
[0050]需要說明的是，並不是每一個節點均對應一個候選節點集，有的節點可能沒有候選節點集，例如，目的節點由於不需要轉發，故其沒有候選節點，進一步的，也不對應候選節點集。
[0051]用數學語言描述候選節點集時，在一個包括N個節點的無線網狀網存在M個候選節點集時，節點與候選節點集之間的關係可以用NXM的矩陣Snxm表示。如果節點i是第m個候選節點集的元素，記為i e m且S ^n0為1，否則igm且S (丄…為O。
[0052]
【權利要求】
1.一種信道分配方法，其特徵在於，所述方法包括: 確定與無線網狀網中每一節點對應的候選節點集，所述與每一節點對應的候選節點集包含該節點和該節點的候選節點； 根據候選節點集信道分配數目約束條件和各節點的射頻接口數目約束條件，確定所有可行的候選節點集信道分配方案； 從所有可行的候選節點集信道分配方案中選擇一個信道分配方案，其中，在選擇的所述信道分配方案下，所有候選節點集間的鏈路幹擾最小，所有候選節點集間的鏈路幹擾是指候選節點集中兩兩個候選節點集間的鏈路幹擾的總和，所述兩兩候選節點集間的鏈路幹擾是指一候選節點集中包含的節點構成的鏈路與另一候選節點集中包含的節點構成的鏈路之間的幹擾； 將為節點所屬的每一候選節點集分配的信道均作為給該節點分配的信道。
2.如權利要求1所述的方法，其特徵在於，所述兩兩候選節點集間的鏈路幹擾是通過以下方式確定的: 確定一候選節點集包含的節點構成的鏈路與另一候選節點集包含的節點構成的鏈路之間的幹擾的估計值，其中，所述估計值是在假定所有候選節點集使用同一信道的情況下得到的； 在候選節點集信道分配方案下，確定為所述一候選節點集分配的信道集合和為所述另一候選節點集分配的信道集合的交集，將確定的所述估計值與所述交集中元素的個數的乘積作為所述一候選節點集包含的節點構成的鏈路與另一候選節點集包含的節點構成的鏈路之間的幹擾值，其中，在確定的所述交集為空集時，該交集中元素的個數為O。
3.如權利要求2所述的方法，其特徵在於，通過以下方式確定一候選節點集包含的節點構成的鏈路與另一候選節點集包含的節點構成的鏈路之間的幹擾的估計值: 確定無線網狀網中包含的鏈路之間的幹擾； 根據無線網狀網中包含的鏈路之間的幹擾和各候選節點集中包含的節點構成的鏈路，確定一個候選節點集中包含的鏈路與另一個候選節點集中包含的鏈路之間的幹擾； 將確定的一個候選節點集中包含的鏈路與另一個候選節點集中包含的鏈路之間的幹擾作為所述估計值。
4.如權利要求3所述的方法，其特徵在於，所述確定無線網狀網中包含的鏈路之間的幹擾 ，具體為: 根據節點的位置，確定各節點的鄰居集，節點的鄰居集是指與該節點的物理傳輸距離小於設定距離的節點的集合，或者是指與該節點構成的鏈路的包投遞率大於設定閾值的節點的集合； 根據確定的各節點的鄰居集，確定與無線網狀網中包含的每一鏈路對應的鏈路幹擾集，其中，第一鏈路對應的鏈路幹擾集中的每一鏈路中包含的節點均為該第一鏈路包含的節點的鄰居節點。
5.如權利要求4所述的方法，其特徵在於，所述候選節點集信道分配數目約束條件為:為一個候選節點集至少分配一個信道； 所述各節點的射頻接口數目約束條件為:為每個節點所分配的信道數總和小於等於該節點具有的射頻數。
6.如權利要求5所述的方法，其特徵在於， 所述為一個候選節點集至少分配一個信道，具體為
所述為每個節點所分配的信道數總和小於等於該節點具有的射頻數，具體為:
其中，Amxk為候選節點集的信道分配矩陣，在第m個候選節點集使用了第k個信道時，該信道分配矩陣Amxk的元素A (m, k)=l ;否則，A (m, k)=0 ；SNXM為節點和候選節點集之間的關係矩陣SNXM，在節點i是第m個候選節點集的元素時，該節點和候選節點集之間的關係矩陣Snxm的元素S(i,m)=l ;否則S(i,m)=0 ;K為無線網絡網中可用的正交信道個數，k=U2-K；N為無線網絡網中節點的個數，i=l>2-N ；M為確定的候選節點集的個數，Ri為節點i具有的射頻數，X為節點的信道分配矩陣，X(i，k)=l表示節點i使用了第k個信道，X(i，k)=0表示節點i未使用第k個信道，πι=1、2...Μ。
7.如權利要求6所述的方法，其特徵在於， 所述從所有可行的候選節點集信道分配方案中選擇一個信道分配方案，該被選擇的信道分配方案使得所有候選節點集間的鏈路幹擾最小具體為:在滿足
和
的條件下，求取滿足
的候選節點集的信道分配矩陣； 其中，Imxm為第u個候選節點集和第V個候選節點集間幹擾的估計值矩陣，在估計出第U個候選節點集和第V個候選節點集間存在幹擾時，I(u；v) = I ;否則，I(u；v) = O ;ιι=1、2...Μ ；V=IU0
8.如權利要求7所述的方法，其特徵在於，所述將為節點所屬的每一候選節點集分配的信道均作為為該節點分配的信道具體為: 將節點和候選節點集之間的關係矩陣Snxm和候選節點集的信道分配矩陣Amxk代入公
，得到節點的信道分配矩陣。
9.一種信道分配裝置，其特徵在於，所述裝置包括: 候選節點集確定模塊，用於確定與無線網狀網中每一節點對應的候選節點集，所述與每一節點對應的候選節點集包含該節點和該節點的候選節點； 候選節點集信道分配方案確定模塊，用於根據候選節點集信道分配數目約束條件和各節點的射頻接口數目約束條件，確定所有可行的候選節點集信道分配方案； 信道分配方案選擇模塊，用於從所有可行的候選節點集信道分配方案中選擇一個信道分配方案，其中，在選擇的所述信道分配方案下，所有候選節點集間的鏈路幹擾最小，所有候選節點集間的鏈路幹擾是指候選節點集中兩兩個候選節點集間的鏈路幹擾的總和，所述兩兩候選節點集間的鏈路幹擾是指一候選節點集中包含的節點構成的鏈路與另一候選節點集中包含的節點構成的鏈路之間的幹擾； 節點信道分配模塊，用於將為節點所屬的每一候選節點集分配的信道均作為給該節點分配的信道。
10.如權利要求9所述的信道分配裝置，其特徵在於， 所述信道分配方案選擇模塊，具體用於確定一候選節點集包含的節點構成的鏈路與另一候選節點集包含的節點構成的鏈路之間的幹擾的估計值，在候選節點集信道分配方案下，確定為所述一候選節點集分配的信道集合和為所述另一候選節點集分配的信道集合的交集，將確定的所述估計值與所述交集中元素的個數的乘積作為所述一候選節點集包含的節點構成的鏈路與另一候選節點集包含的節點構成的鏈路之間的幹擾值，其中，所述估計值是在假定所有候選節點集使用同一信道的情況下得到的，在確定的所述交集為空集時，該交集中元素的個數為O。
11.如權利要求10所述的信道分配裝置，其特徵在於，所述信道分配方案選擇模塊，具體用於確定無線網狀網中包含的鏈路之間的幹擾；根據無線網狀網中包含的鏈路之間的幹擾和各候選節點集中包含的節點構成的鏈路，確定一個候選節點集中包含的鏈路與另一個候選節點集中包含的鏈路之間的幹擾；將確定的一個候選節點集中包含的鏈路與另一個候選節點集中包含的鏈路之間的幹擾作為所述估計值。
12.如權利要求11所述的信道分配裝置，其特徵在於，所述信道分配方案選擇模塊，具體用於根據節點的位置，確定各節點的鄰居集，根據確定的各節點的鄰居集，確定與無線網狀網中包含的每一鏈路對應的鏈路幹擾集，其中，節點的鄰居集是指與該節點的物理傳輸距離小於設定距離的節點的集合，或者是指與該節點構成的鏈路的包投遞率大於設定閾值的節點的集合，其中， 第一鏈路對應的鏈路幹擾集中的每一鏈路的節點均為該第一鏈路包含的節點的鄰居節點。
13.如權利要求12所述的信道分配裝置，其特徵在於，所述候選節點集信道分配數目約束條件為:為一個候選節點集至少分配一個信道； 所述各節點的射頻接口數目約束條件為:為每個節點所分配的信道數總和小於等於該節點具有的射頻數。
【文檔編號】H04W40/16GK104080088SQ201310101899
【公開日】2014年10月1日 申請日期:2013年3月27日 優先權日:2013年3月27日
【發明者】曾彬, 何施茗, 張大方 申請人:中國移動通信集團湖南有限公司