關于通信結點連接問題的優化模型?

桂改花

（廣東科學技術職業學院 珠海 519090）

關于通信結點連接問題的優化模型?

桂改花

（廣東科學技術職業學院 珠海 519090）

論文運用Kruskal算法，求出通信網絡的最小化連接成本。出于安全可靠性考慮，要求網絡中除某固定的兩個結點外，其它任意三個結點被破壞時，仍然能夠保持這兩個結點之間的通信，論文用LINGO程序遍歷出最優解，論文還用Matlab軟件，以窮舉法為核心，以Dijkstra迪克斯特拉算法和0-1規劃作為輔助，編寫程序，盡可能地遍歷所有的可能解，最終得出的結果與用LINGO軟件得出的結果一致，充分證明了答案的準確性。

最小生成樹；Kruskal算法；窮舉法；0-1規劃

1 引言

結點是指一臺電腦或其他設備與一個有獨立地址和具有傳送或接收數據功能的網絡相連。結點可以是工作站、客戶、網絡用戶或個人計算機，還可以是服務器、打印機和其他網絡連接的設備。每一個工作站、服務器、終端設備、網絡設備，即擁有自己唯一網絡地址的設備都是網絡結點［1］。整個網絡就是由這許許多多的網絡結點組成的，把許多的網絡結點用通信線路連接起來，形成一定的幾何關系，這就是計算機網絡拓撲［2］。

通信網絡［3］結構也是計算機網絡拓撲中在實際中的一個應用，通信網絡的網絡終端之間都是由電纜連接的，求解一個通訊網絡的最小連接成本其實就是最優連線問題，又稱最小生成樹［4］問題，是求網絡中長度最小的生成樹。對于最小生成樹問題，可采用“避圈法”的推廣，Kruskal算法［5］。出于安全可靠性［6］考慮，要求網絡中除某固定的兩個結點外，其它任意三個結點被破壞時，仍然能夠保持這兩個結點之間的通信，本文用LINGO［7］程序遍歷出最優解，存在局部最優解的可能，因此，本文用Matlab［8］軟件，以窮舉法［9］為核心，以迪克斯特拉（Dijkstra）算法［10］和0-1規劃［11］作為輔助，編寫程序，盡可能地遍歷所有的可能解，最終得出的結果與用LINGO軟件得出的結果一致，充分證明了答案的準確性。給出連接方案。

2 算法簡介

2.1 Kruskal算法

第1步 選e1∈T；

第2步 考慮e2，如果e2加入T不會產生回路，則把e2加入T，否則放棄e2；再考慮e3，如果e3加入T不會產生回路，則把e3加入T，否則放棄e3；如此反復下去，直到無邊可選為止。這樣選出的T就是賦權圖G的最小生成樹。

2.2 求最短路的算法-迪克斯特拉（E.W.Dijkstra）算法

基本思想：把圖中所有點分為兩組，第一組包含已確定最短路徑的結點，第二組包含尚未確定最短路徑的結點。然后把第二組的點逐個加到第一組中去，直到從某點出發可以到達的所有點都包含在第一組中。

計算賦權圖中各對頂點之間最短路徑，顯然可以調用Dijkstra算法。具體方法是：每次以不同的頂點作為起點，用Dijkstra算法求出從該起點到其余頂點的最短路徑，反復執行次這樣的操作，就可得到從每一個頂點到其它頂點的最短路徑。

3 案例分析

圖1是一個擬建的通信網絡，11個小圓圈代表網絡終端結點，終端結點通過地下電纜雙向連接，以進行數據傳輸；結點間的數字表示距離，單位：km。

1）終端間的連接方案，以最小化總連接成本；

2）出于安全可靠性考慮，除10、11結點外，其它任意三個結點被破壞時，仍然能夠保持結點10和11之間的通信，給出連接方案。

圖1 通信網絡圖

3.1 問題一：求解

按照上文的表達式，寫出相應的LINGO程序，根據輸出結果，畫出連接圖，如下：

圖2 LINGO結果1連接圖

3.2 問題二：建模過程

3.2.1 LINGO方法程序思路

網絡中除10、11結點外，其它任意三個結點被破壞時，仍然能夠保持結點10和11之間的通信，則網絡中至少存在4條通路，才能保證連通10、11兩點，且11只出，10只進，對于任意兩點的通路進行標記，有通過的標為1，否則為0，為確保10、11連通，就必須保證1到9中每個點進路和出路都至少為1，最后算總路徑：所有有經過的路之和。

3.2.2 LINGO程序結果

依據程序思路，寫出LINGO程序的約束條件，依據結果，畫出最優的連接方案：

圖3 LINGO程序結果2連接圖

3.2.3 Matlab方法程序思路N-S圖

圖4 N-S圖

3.2.4 Matlab方法程序思路流程圖

圖5 流程圖

3.2.5 Matlab程序結果

將以上程序思路轉化為Matlab代碼，運行結果如下：

11→1；11→3；11→5；114；1→4；310；5→9；46；2→8；910；67；810；710；

結果與用LINGO得出的結果一致，總路徑均為2347，成功驗證了LINGO方法。

4 結語

本模型由于分別采用了LINGO和Matlab兩種方法，避免了由于主觀意識所導致的結果不準確，程序分別得出了一致的結果，證明方法的正確性。

由于本模型中采用Matlab方法的程序并未涉及太多對于該問題的局限性，因此對于其他網絡結點問題，只要代入相應數據并修改部分代碼，可實現該模型推廣的可能，對于降低工程建設的成本有很大的幫助。

［1］李全崗，劉嶠，秦志光.基于主體模型的通信網絡建模與仿真［J］.計算機研究與發展，2016，53（1）：206-215.LI Quangang，LIU Qiao，QIN Zhiguang.Modeling and Simulation Network Based on Topic Model［J］.Journal of Computer Research and Development，2016，53（1）：206-215.

［2］包學才，戴伏生，韓衛占.基于拓撲的不相交路徑抗毀性評估方法［J］.系統工程與電子技術，2012，34（1）：168-174.BAO Xuecai，DAI Fusheng，HAN Weizhan.Evaluation method of network invulnerability based on disjoint paths in topology［J］.Systems Engineering and Electronics，2012，34（1）：168-174.

［3］余新，李艷和，鄭小平，等.基于網絡性能變化梯度的通信網絡節點重要程度評價方法［J］.清華大學學報（自然科學版），2008，48（4）：541-544.YU Xin，LI Yanhe，ZHENG Xiaoping，et al.Node importance evaluation based on communication network performance grads［J］.Tsinghua Univ（Sci&Tech），2008，48（4）：541-544.

［4］孫小軍，劉三陽，王志強.一種求解最小生成樹問題的算法［J］.計算機工程，2011，37（23）：241-243.SUN Xiaojun，LIU Sanyang，WANG Zhiqiang.Algorithm for Solving Minimum Spanning Tree Problem［J］.Computer Engineering，2011，37（23）：241-243.

［5］司守奎，孫兆亮.數學建模算法與應用［M］.北京：國防工業出版社，2015.48-49.SI Shoukui，SUN Zhaoliang.MathematicalModeling Algorithms and Application［M］.Beijing：National Defense Industry Press，2015.48-49.

［6］劉普寅，張維明.通信網絡可靠性研究中的數學問題［J］.通信學報，2000，21（10）：50-57.LIU Puyin，ZHANG Weiming.Mathematical problems in research on reliability of communication networks［J］.Journal of China Institute of communications，2000，21（10）：50-57.

［7］謝金星，薛毅.優化建模與LINDO/LINGO軟件［M］.北京：清華大學出版社，2005.XIE Jinxing，XUE Yi.Optimization Modeling and LINDO/LINGO［M］.Beijing：Tsinghua University Press，2005.

［8］卓金武，李必文，魏永生，等.MATLAB在數學建模中的應用［M］.北京：北京航空航天大學出版社，2014.ZHUO Jinwu，LI Biwen，WEI Yongsheng，et al.Application of MATLAB in Mathematical Modeling［M］.Beijing：Beijing University of Aeronautics and Astronautics press，2014.

［9］孫義欣，馮娜.窮舉法在程序設計中的應用［J］.計算機時代，2012，8：50-52.SUN Yixin，FENG Na.Application of exhaustion method in programming［J］.Computer Era，2012，8：50-52.

［10］司守奎，孫兆亮.數學建模算法與應用［M］.北京：國防工業出版社，2015.40-44.SI Shoukui，SUN Zhaoliang.MathematicalModeling Algorithms and Application［M］.Beijing：National Defense Industry Press，2015.40-44.

［11］張玉蘭，曹亞萍.基于0-1規劃的高校選課策略［J］.高師理科學刊，2014，34（6）：14-15.ZHANG Yulan，CAO Yaping.Strategy of college course selection based on 0-1planning［J］.Journal of Science of Teachers'College and University，2014，34（6）：14-15.

Optimization Model For Communications Node Connection Problem

GUI Gaihua
（Guangdong Institute of Science，Zhuhai 519090）

This paper uses Kruskal algorithm to get the communication network connection cost minimization.For the sake of safety and reliability，requirements in addition to a fixed two nodes in the network，any other three nodes are destroyed，it will still be able to keep this communication between two nodes.In this paper，LINGO program is used to traversal the optimal solution.This article also use the Matlab software，using exhaustive method as the core，to terra dix Dijkstra algorithm and 0-1 programming as auxiliary and write a program，as far as possible to iterate through all possible solutions.Final results are consistent with the results using LINGO software，fully proved the accuracy of the answers.

minimum spanning tree，Kruskal algorithm，exhaustive method，0-1 programming

TP391

10.3969/j.issn.1672-9722.2017.10.002

Class Number TP391

2017年4月10日，

2017年5月20日

廣東省高職教育一類品牌專業資助項目（編號：2016gzpp007）資助。

桂改花，女，碩士研究生，講師，研究方向：應用數學。