[發明專利]一種面向稀疏用戶分布的光接入網ODN智能聚類規劃方法

有效

• 申請號: 202110600825.7
• 申請日: 2021-05-31
• 公開（公告）號: CN113316038B
• 公開（公告）日: 2022-03-25
• 發明（設計）人: 李慧;聶天予;郭賢義;紀越峰
• 申請（專利權）人: 北京郵電大學
• 主分類號: H04Q11/00
• 分類號: H04Q11/00;G06K9/62;G06N5/00
• 代理公司: 北京永創新實專利事務所 11121
• 代理人: 易卜

1.一種面向稀疏用戶分布的光接入網ODN智能聚類規劃方法，其特征在于，具體步驟如下：

首先，針對某規劃區域，在ODN網絡的配線段，以區域內的用戶地理位置坐標為輸入，使用k-means聚類算法隨機生成k個初始質心的位置坐標，作為二級分光點；并構造代價函數T，利用代價函數T對初始質心的個數k以及各質心的位置坐標進行迭代優化，得到最優的二級分光點個數和位置坐標；進一步通過優化的二級分光點的個數和位置坐標，確定一級分光點的位置坐標；

所述的代價函數T，計算公式為：

n為規劃區域內的用戶個數；d(X_i,C(X_i))代表第i個用戶X_i到其所歸屬的二級分光點C(X_i)的歐式距離；0kn；d(Y_j,O)代表第j個二級分光點Y_j到一級分光點O的歐式距離；P_x代表二級分光點到用戶入戶光纖的單位成本；P_y代表一級分光點到二級分光點的光纖單位成本；所述的確定一級分光點的具體步驟為：

步驟401、利用優化后的各二級分光點的位置坐標，分別計算各二級分光點對應的弧度值，并將弧度值α按升序排序；

計算公式如下：

(x',y')為二級分光點的位置坐標；

步驟402、將排序后的二級分光點作為初始隊列Q₀，并復制該隊列為Q；

將復制隊列Q中的二級分光點依次設為{t₁,t₂,...,t_i,...,t_k'}，并設定各二級分光點對應的索引依次為{1,2,...,i,...,k'}；

步驟403、從復制隊列Q中逐個選擇索引，判斷索引i是否大于k'，如果是，則該輪分組結束，進入步驟407；否則，將索引對應的二級分光點t_i取出，進入步驟404；

步驟404、判斷二級分光點t_i的下掛用戶數u_i與下掛用戶數總和sum之和是否小于等于最大分光比F，如果是，進入步驟405；否則，進入步驟406；

步驟405、將二級分光點t_i更新到單個分組g中，將下掛用戶數u_i添加到下掛用戶數總和sum中，并將索引i加1，返回步驟403；

單個分組g初始為空；下掛用戶數總和sum初始值為0；

步驟406、將當前單個分組g更新到分組結果G的元素中，并將g和sum分別初始化為空，返回步驟405；

分組結果G集合為{G₁,G₂,...,G_n,...,G_N}，N≤k'，各元素初始均為空；每次將單個分組g分別更新到集合中的一個元素G中；

步驟407、從分組結果G中逐個選擇各元素，分別計算各元素對應的代價函數D；

代價函數D代表一個一級分光點下建設所用的光纖長度，計算公式為：

C為二級分光點到用戶的距離常量；(x_i',y_i')代表G中各元素包含的二級分光點的位置坐標；p代表G中各元素包含的二級分光點的個數；

當各組一級分光點的位置坐標(x,y)取時，代價函數D取值最小，由此得到各元素對應的代價函數集合為{D₁,D₂,...,D_n,...,D_N}，對應的各一級分光點位置坐標集合為：{(x₁,y₁),(x₂,y₂),...,(x_n,y_n),...,(x_N,y_N)}；

步驟408、對各代價函數D_n進行求和得到和值D_a，并判斷D_a是否小于設定的總代價函數D_0a，如果是，將總代價函數D_0a更新為D_a，并將各一級分光點的位置坐標保留，進入步驟409；否則，不予處理，直接進入步驟409；

總代價函數D_0a初始值為無窮大；

則各代價函數的求和公式為：

步驟409、將復制隊列Q進行移位操作，將首位二級分光點t₁，移到最后一位，形成新隊列{t₂,...,t_i,...,t_k',t₁}，將更新后隊列返回步驟402，依次計算，直至更新的隊列恢復為初始隊列Q₀，算法結束；

針對每次復制的隊列，均能得到各復制下的二級分光點分組，以及對應的一級分光點位置坐標，并根據各代價函數之和是否小于上一次復制隊列對應的代價函數之和，得到越來越小的代價函數之和，直至復制隊列Q回到初始隊列Q₀為止，選擇最后一次復制隊列中保留的一級分光點，即為最優的一級分光點的位置坐標；

然后，根據優化后的二級分光點和一級分光點的位置，計算每個用戶途經二級分光點，一級分光點到主干光交點的歐式距離，取距離的最長值作為該規劃區域的光纖預留長度，進而完成配線段的規劃；

針對ODN網絡的饋線段規劃，通過實地采集確定光匯聚點OLT和各個規劃區域的連通關系，得到權值連通圖；并求出連通點的光纖長度作為連通圖各邊的權值，對權值連通圖采用最小生成樹算法尋找最小生成樹；

所述的最小生成樹的具體步驟如下：

步驟601、調用Kruskal算法求權值連通圖的最小生成樹；

權值連通圖的頂點個數為r，則對應的最小生成樹頂點個數也為r，且最小生成樹的邊為r-1條；通過對權值連通圖所有邊上的權值進行升序排序，并逐個選擇各邊，利用Kruskal算法篩選出r-1條邊和對應的兩端點構成初始最小生成樹；

步驟602、驗證初始最小生成樹是否滿足PON最大距離傳輸，如果是，則完成規劃并輸出當前最小生成樹；否則，進入步驟603；

PON最大傳輸距離公式如下：

L≤(P-IL-A_c×H-A_wdm×M-M_c-β)/A_F

P為PON系統OLT到光網絡單元ONU之間允許的最大插損；IL為整個光纖鏈路中經過的所有光分路器的插入損耗之和；A_c為鏈路中一個活接頭的插入損耗；H為OLT到ONU之間活接頭的數量；A_wdm為WDM模塊的插入損耗；M為整個光纖鏈路中所使用的WDM器件的個數；M_c為線路的維護余量；β表示在光纖鏈路中，使用不同光纖種類帶來的損耗；A_F為衰減系數；

步驟603、對權值連通圖的所有邊進行編號，共得到m個編號信息；

編號對應的邊的信息包括兩端的頂點和權值信息；

步驟604、從m個不同的編號中取出r-1個形成組合即列出所有的邊組合；

步驟605、從中逐個選擇不同的邊組合進行遍歷，針對每個組合，判斷是否組合中所有的頂點都覆蓋了權值連通圖的所有頂點，且其中任意兩點間有且僅有一條通路，如果是，保留該組合，生成一個待選生成樹；否則，舍去當前組合；

步驟606、從中選擇下一個邊組合，重復步驟605，直至所有的組合遍歷完畢，得到若干待選生成樹，遍歷每個待選生成樹中所有的邊，并將對應的權值相加保存；

步驟607、將各待選生成樹的權值和進行升序排序，得到待選生成樹集合；

步驟608、對待選生成樹集合逐個選擇各生成樹進行驗證，判斷是否滿足PON最大距離傳輸，如果是，則結束驗證，并選擇當前滿足PON最大距離傳輸的待選生成樹，作為最優結果輸出，后續各待選生成樹不再驗證；否則，對PON最大傳輸距離進行修改，直至某個待選生成樹滿足PON最大傳輸距離即可，輸出滿足條件的該待選生成樹；

最后、根據配線段和饋線段的規劃結果，完成對稀疏用戶的光接入網ODN規劃。