苗永梅 楊 蘭 南 貌

（寶雞職業(yè)技術(shù)學(xué)院 寶雞 721304）

1 引言

互聯(lián)網(wǎng)讓世界變成了“雞犬之聲相聞”的地球村［1］，人們的生活幾乎離不開(kāi)互聯(lián)網(wǎng)，網(wǎng)民數(shù)量逐年劇增；思科2018 年12 月7 日發(fā)布的最新VNI 報(bào)告預(yù)測(cè)［2］，2016年中國(guó)網(wǎng)民總數(shù)量7.3億，2017年中國(guó)網(wǎng)民總數(shù)量7.7 億，2018 年中國(guó)網(wǎng)民總數(shù)量8.1億，預(yù)計(jì)到2022 年網(wǎng)民將占據(jù)全球人口的60%，超過(guò)280億設(shè)備將連入互聯(lián)網(wǎng)。

中國(guó)電信行業(yè)為改善用戶體驗(yàn)，提高信號(hào)覆蓋質(zhì)量，加大資金投入建設(shè)基站。根據(jù)《2018 年中國(guó)電信行業(yè)資本開(kāi)支及運(yùn)營(yíng)商4G 基站數(shù)量》［3］統(tǒng)計(jì)，電信行業(yè)資本開(kāi)支2017 年達(dá)到3920 億元，2018 年為3740 億元，2019 年預(yù)計(jì)將達(dá)3770 億元。2020 到2021 年將迎來(lái)5G 首輪投資高峰，兩年總資本開(kāi)支有望達(dá)到8400億元以上［4］。

隨著5G 時(shí)代到來(lái)，各運(yùn)營(yíng)商競(jìng)爭(zhēng)不斷加劇，為爭(zhēng)取更大優(yōu)勢(shì)，會(huì)加大5G 建設(shè)投資，5G 網(wǎng)絡(luò)信號(hào)頻段是高頻和超高頻，頻率高波長(zhǎng)短穿透能力弱，相對(duì)于4G 信號(hào)來(lái)說(shuō)覆蓋范圍大幅減小，原來(lái)一個(gè)4G基站覆蓋的范圍，5G基站可能需要5個(gè)、10個(gè)甚至更多［5］。依據(jù)傳統(tǒng)的用戶群分布位置布局基站［6］，需要設(shè)置更多的基站，投入更大的資金。

5G 基站密度增加，網(wǎng)絡(luò)結(jié)構(gòu)變得越來(lái)越復(fù)雜，傳統(tǒng)規(guī)劃模型已經(jīng)不能滿足網(wǎng)絡(luò)規(guī)劃科學(xué)指導(dǎo)的需要［8］。針對(duì)某一區(qū)域網(wǎng)絡(luò)設(shè)施的拓?fù)鋱D，用圖論對(duì)其結(jié)構(gòu)進(jìn)行分析，尋找Ramsey數(shù)，對(duì)網(wǎng)絡(luò)進(jìn)行精細(xì)化布局，減少基站數(shù)量，節(jié)約開(kāi)支。

2 網(wǎng)絡(luò)圖

圖是由點(diǎn)集和邊集組成的一對(duì)序偶，記為G=(V，E)；其中V 是頂點(diǎn)集合，記為V(G)，E 是邊集合，記為E(G)；E(vj，vi)表示從頂點(diǎn)vj 到頂點(diǎn)vi有一條直接通路。用圖這種數(shù)據(jù)結(jié)構(gòu)來(lái)描述生活實(shí)例，簡(jiǎn)化模型易于分析。圖1 網(wǎng)絡(luò)通信模型描述如下：

G=(V，E) ，其中V 表示點(diǎn)集，E 表示邊集（E1有線，E2無(wú)線）

其中E1、E2集合如下。

圖1 網(wǎng)絡(luò)拓?fù)鋱D

圖2 分析圖

網(wǎng)絡(luò)中各節(jié)點(diǎn)之間通信沒(méi)有方向、先后之分，G選擇無(wú)向圖。

3 優(yōu)化方案分析

網(wǎng)絡(luò)規(guī)模擴(kuò)大過(guò)程可類比于人群的聚集，先是兩個(gè)人互相認(rèn)識(shí)，再介紹其它的人相互認(rèn)識(shí)，依據(jù)三元閉包［9］定理，如果兩個(gè)互不相識(shí)的人有了一個(gè)共同的朋友，則他們倆成為朋友的可能性提高，如圖1 ac 認(rèn)識(shí)，af 認(rèn)識(shí)，fc 成為熟人的機(jī)會(huì)較大，經(jīng)過(guò)a 認(rèn)識(shí)的節(jié)點(diǎn)越多，a 凝聚力就大，在網(wǎng)絡(luò)規(guī)劃中，這些節(jié)點(diǎn)是要保留的。

網(wǎng)絡(luò)規(guī)模擴(kuò)大到一定程度，形成無(wú)向完全圖，任意兩個(gè)節(jié)點(diǎn)之間直接或間接有一條鏈路，把這些節(jié)點(diǎn)兩兩配對(duì)作為一個(gè)整體，保證某些鏈路出現(xiàn)故障時(shí)，任意兩兩配對(duì)的頂點(diǎn)間至少有一條通路可用，確保通信正常。這些通信鏈路由中繼站、微波塔等中間設(shè)施提供，隨著5G時(shí)代到來(lái)，這些中間設(shè)施數(shù)量增加，會(huì)有大量資金消耗。為了節(jié)約成本，對(duì)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化，保留凝聚力大的節(jié)點(diǎn)，減少中間設(shè)施數(shù)量，在任何一個(gè)中間設(shè)施損壞時(shí)，所設(shè)計(jì)的網(wǎng)絡(luò)中任兩配對(duì)的頂點(diǎn)間有一個(gè)可使用的鏈路。

Ramsey 理論是組合數(shù)學(xué)中的一個(gè)重要分支，它從不同方面揭示了任何一個(gè)足夠大的結(jié)構(gòu)中必定包含一個(gè)給定性質(zhì)的子結(jié)構(gòu)［10］，Ramsey 數(shù)是圖論的重要函數(shù)之一［11］，在圖論中［12］根據(jù)Ramsey 定理尋找無(wú)向圖上的Ramsey數(shù)，作為中間設(shè)施數(shù)量，簡(jiǎn)化結(jié)構(gòu)。

4 Ramsey定理及Ramsey數(shù)

4.1 Ramsey定理

給定兩個(gè)整數(shù)a，b ≥2，則一定存在一個(gè)最小整數(shù)R，使得用兩種（紅色、藍(lán)色）顏色給圖G 的每條邊如何染色，總能找到一個(gè)紅色的a 圖形或者藍(lán)色b圖形，記為R（a，b）。 R 可以看做一個(gè)a，b 的二元函數(shù)，即R(a，b)。

定理1R(C4，C4)=6 ，其中C4為4 個(gè)頂點(diǎn)的回路圖。

定理2R(C4，C4，C4)=11

定 理3［13］若 一 個(gè)n 個(gè) 頂 點(diǎn) 的 圖，至 少 有條邊，則它一定包含C4。

4.2 Ramsey數(shù)定義

設(shè)a，b 為正整數(shù)，令R(a，b)是保證有a個(gè)人彼此相識(shí)或者有b 個(gè)人彼此不相識(shí)所需要的最少人數(shù)，則稱為Ramsey 數(shù)［14］?？蓪amsey 定理簡(jiǎn)單描述為在人數(shù)為6 的人群中，一定有三個(gè)人彼此相識(shí)或者彼此不相識(shí)；由鴿籠原理［15］知，6 只鴿子飛向2個(gè)籠子，一個(gè)籠子至少有3 只，用公式表示為R(3，3)=6。

5 確定Ramsey數(shù)

隨著a，b 值增大，尋找R(a，b)數(shù)變得困難，可將問(wèn)題轉(zhuǎn)化為圖的著色問(wèn)題，根據(jù)著色要求，搜索可行的著色序列。將圖1 簡(jiǎn)化為圖2 分析結(jié)構(gòu)，求解Ramsey 數(shù)。圖2 是由6 個(gè)通信設(shè)備組成的網(wǎng)絡(luò)系統(tǒng)，設(shè)頂點(diǎn)a1a2組成一對(duì)，b1b2組成一對(duì)，c1c2組成一對(duì)，通信鏈路由中繼站、微波塔提供，圖中用同一類型的連線標(biāo)記共享同一個(gè)中間設(shè)施的鏈路，若以點(diǎn)線連線標(biāo)記的中間設(shè)施出現(xiàn)故障，那么頂點(diǎn)對(duì)a1a2和頂點(diǎn)對(duì)c1c2之間沒(méi)有可用的通途鏈路，即a1c1a2c2構(gòu)成一個(gè)單色的C4，在構(gòu)建網(wǎng)絡(luò)系統(tǒng)時(shí)盡可能地避免出現(xiàn)C4。

已知定理1 R(C4，C4)=6 ，因此R(C4，C4)＞5，即表示5 個(gè)節(jié)點(diǎn)的完全圖，用紅藍(lán)兩種顏色著色，既不存在紅色的C4，也不存在藍(lán)色的C4；如果有兩個(gè)（兩種顏色）中間施，那么由5 個(gè)通信設(shè)備（節(jié)點(diǎn)）組成的網(wǎng)絡(luò)著色方案不會(huì)出現(xiàn)單色的C4，滿足方案設(shè)計(jì)要求，但由6 個(gè)節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)，無(wú)論如何都會(huì)出現(xiàn)單色C4，不能滿足設(shè)計(jì)要求。定理2，網(wǎng)絡(luò)有11 個(gè)節(jié)點(diǎn)，三個(gè)中間設(shè)施，存在單色C4，要滿足鏈路設(shè)計(jì)要求，至少需要4個(gè)中間設(shè)施。

對(duì)完全無(wú)向圖G 的每條邊用r 種顏色e1、e2、…er任意邊著色，必定有個(gè)顏色為e1的c1邊形，或有個(gè)顏色為e2的c2邊形，或有個(gè)顏色為er的cr邊形。符合條件又最少的數(shù)記為R(C1，C2，…，Cr)。對(duì)n 個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，若要對(duì)其結(jié)構(gòu)優(yōu)化，不存在單色C4的條件下，中間設(shè)施最少需要多少個(gè)？即求R(C4，C4，…C4)＞n 的最小r。

6 結(jié)語(yǔ)

5G 網(wǎng)絡(luò)接入設(shè)備種類繁多、數(shù)量劇增，原來(lái)一個(gè)4G 基站覆蓋的范圍，5G 基站可能需要更多；5G基站密度增加，網(wǎng)絡(luò)結(jié)構(gòu)變得越來(lái)越復(fù)雜，傳統(tǒng)的依據(jù)用戶群分布位置布局基站已經(jīng)不能滿足網(wǎng)絡(luò)規(guī)劃科學(xué)指導(dǎo)的需要。將網(wǎng)絡(luò)通信模型簡(jiǎn)化為完全無(wú)向圖，用圖論的一個(gè)重要理論Ramsey 定理對(duì)其分析，依據(jù)定理1、2、3 推導(dǎo)出式（1），用式（1）計(jì)算Ramsey 數(shù)，作為網(wǎng)絡(luò)架構(gòu)中間設(shè)施數(shù)量的一個(gè)參考。例如對(duì)100 個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，依據(jù)公式計(jì)算，至少需要10 個(gè)中間設(shè)施才能保證在鏈路出故障時(shí)網(wǎng)絡(luò)正常通信。