覆蓋型網(wǎng)絡(luò)的關(guān)鍵設(shè)施識別問題研究.pdf

1、隨著經(jīng)濟(jì)與科技的快速發(fā)展,電信通訊網(wǎng)絡(luò)、電力系統(tǒng)網(wǎng)絡(luò)、交通運(yùn)輸網(wǎng)絡(luò)等網(wǎng)絡(luò)系統(tǒng)已經(jīng)滲透到了人們生活、社會(huì)經(jīng)濟(jì)、國防安全的方方面面。網(wǎng)絡(luò)中的一些非常重要的服務(wù)設(shè)施,一旦遭到破壞不能正常運(yùn)行,對整個(gè)網(wǎng)絡(luò)造成的影響是最具破壞性的,甚至?xí)鹫麄€(gè)網(wǎng)絡(luò)的級聯(lián)故障,從而導(dǎo)致整個(gè)網(wǎng)絡(luò)系統(tǒng)的大面積癱瘓,這些設(shè)施就被視為網(wǎng)絡(luò)關(guān)鍵設(shè)施。通過識別網(wǎng)絡(luò)關(guān)鍵設(shè)施,采取有針對性的防御措施,對保障基礎(chǔ)設(shè)施安全及網(wǎng)絡(luò)正常運(yùn)行具有十分重要的意義。
　　本文首先對國內(nèi)

2、外擴(kuò)展覆蓋問題以及設(shè)施中斷問題相關(guān)研究進(jìn)行了綜述,主要介紹了包括集覆蓋問題模型、最大覆蓋問題等傳統(tǒng)的覆蓋問題;包括漸進(jìn)覆蓋問題模型、組合覆蓋問題模型等擴(kuò)展性覆蓋問題;以及設(shè)施中斷問題的研究。針對通訊類設(shè)施提供的服務(wù)漸進(jìn)衰減和信號組合覆蓋的特點(diǎn),在漸進(jìn)覆蓋模型和組合覆蓋模型的基礎(chǔ)上,建立比傳統(tǒng)的P-中位問題和最大覆蓋問題更符合實(shí)際情況且更具有普遍意義的漸進(jìn)覆蓋和組合覆蓋的中斷問題模型,并分別設(shè)計(jì)了拉格朗日松弛算法和遺傳算法,針對具體算例對