基于費(fèi)馬點(diǎn)的網(wǎng)絡(luò)連通性修復(fù)策略

周趙斌，章紅艷，汪曉丁

基于費(fèi)馬點(diǎn)的網(wǎng)絡(luò)連通性修復(fù)策略

周趙斌1,2，章紅艷3，汪曉丁1,2

（1. 福建師范大學(xué)數(shù)學(xué)與信息學(xué)院，福建 福州 350117；2. 福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室，福建 福州 350117；3. 福建師范大學(xué)協(xié)和學(xué)院，福建 福州 350117）

網(wǎng)絡(luò)有效性；連通性修復(fù)；三角剖分；費(fèi)馬點(diǎn)

1 引言

2 國(guó)內(nèi)外研究現(xiàn)狀

現(xiàn)有的1-連通性修復(fù)策略主要可分為兩類(lèi)。其中，一部分策略[1-11]利用構(gòu)造SMT-MSP所消耗的資源(中繼節(jié)點(diǎn))與理論上最優(yōu)SMT-MSP所需資源(中繼節(jié)點(diǎn))的比(即近似比)作為衡量標(biāo)準(zhǔn)，近似比越小算法的性能越好，而另一部分策略[12-14]則采用仿真實(shí)驗(yàn)來(lái)驗(yàn)證算法性能。

Chen等[11]提出基于四邊形構(gòu)造的近似算法，不僅證明此算法近似比為3，并且證明了單純采用斯坦納化最小生成樹(shù)（MST）的方法來(lái)修復(fù)連通性的近似比也為3。在此基礎(chǔ)上，Cheng等[8]提出基于三角形構(gòu)造結(jié)合斯坦納化MST的近似算法，以及基于3-超圖最小生成樹(shù)的隨機(jī)近似算法，并證明這兩者的近似比分別為3和2.5。盡管后者近似比較低，但其算法復(fù)雜度偏高。Lloyd等[9]提出一種改進(jìn)的斯坦納化MST法，近似比在6~7之間。Tang等[10]將部署區(qū)域劃分成網(wǎng)絡(luò)并對(duì)網(wǎng)絡(luò)分簇，對(duì)于每個(gè)網(wǎng)格部署一個(gè)節(jié)點(diǎn)作為簇頭負(fù)責(zé)簇內(nèi)與簇間通信，從而恢復(fù)網(wǎng)絡(luò)的1-連通性，此算法的近似比為4.5。Efrat等[3]、Yang等[6]、Misra等[5,7]對(duì)于節(jié)點(diǎn)與節(jié)點(diǎn)、節(jié)點(diǎn)與中繼、中繼與中繼這3種不同連接方式給予相應(yīng)的權(quán)值并以此構(gòu)造賦權(quán)完全圖，然后根據(jù)網(wǎng)絡(luò)不同的應(yīng)用場(chǎng)景，結(jié)合目前最優(yōu)的最小權(quán)斯坦納樹(shù)構(gòu)造算法[15]，提出近似比分別為3.11、6.43、6.2和12.4的修復(fù)算法。在文獻(xiàn)[4]中，Wang等提出了一種結(jié)合Voronoi圖和重心的算法。近期，Wang等[1]、Lalouani等[2]先后提出在網(wǎng)絡(luò)中存在障礙物情況下基于直骨架的修復(fù)算法。

文獻(xiàn)[12-14]通過(guò)仿真實(shí)驗(yàn)驗(yàn)證算法性能。Ranga等[13]提出一個(gè)基于0梯度點(diǎn)的修復(fù)算法。此算法首先利用連通分支構(gòu)造一個(gè)凸殼，然后構(gòu)造凸殼內(nèi)各點(diǎn)與連通分支之間的距離函數(shù)并計(jì)算出能夠使該函數(shù)梯度為0的點(diǎn)，最后以這個(gè)點(diǎn)為中心部署中繼節(jié)點(diǎn)來(lái)連接各個(gè)分支。Joshi等[12]利用網(wǎng)絡(luò)的直骨架并結(jié)合節(jié)點(diǎn)的傳輸半徑，規(guī)劃出一條最優(yōu)的中繼節(jié)點(diǎn)部署路線。陳洪生等[14]給出了一個(gè)基于四邊形的連通度修復(fù)算法并證明了其時(shí)間和信息復(fù)雜度。

表1 各算法在近似比和復(fù)雜度方面的對(duì)比

3 預(yù)備知識(shí)

4 系統(tǒng)模型

針對(duì)此問(wèn)題，本文提出了一種高效的連通性修復(fù)策略（RSFP，restoration strategy based on fermat point）。

5 RSFP策略

該策略通過(guò)7個(gè)步驟來(lái)實(shí)現(xiàn)網(wǎng)絡(luò)1-連通性的修復(fù)，具體執(zhí)行步驟如下。

以下將給出一個(gè)RSFP修復(fù)網(wǎng)絡(luò)連通性的例子。

圖1 一個(gè)RSFP示例

6 理論分析

本節(jié)對(duì)策略RSFP在近似比與復(fù)雜度方面進(jìn)行分析。

證明

證明

證明

證畢。

證明

證畢。

7 仿真實(shí)驗(yàn)

本節(jié)利用工具NS2.34對(duì)策略RSFP、RRLC-GBP[13]、GSR[12]和OASS[1]進(jìn)行性能比較。首先，將50~70個(gè)節(jié)點(diǎn)隨機(jī)部署在一個(gè)2 000 m× 2 000 m的區(qū)域內(nèi)。然后，分別通過(guò)固定節(jié)點(diǎn)個(gè)數(shù)變化半徑的方式和固定半徑變化節(jié)點(diǎn)個(gè)數(shù)的方式比較4種策略所消耗的平均中繼節(jié)點(diǎn)數(shù)量。

如圖2所示，各策略消耗的中繼節(jié)點(diǎn)數(shù)量隨著中繼節(jié)點(diǎn)半徑的增加而減少。本文提出的策略RSFP所需的中繼節(jié)點(diǎn)數(shù)量明顯少于其他3種策略。這是因?yàn)椋菏紫龋琑RLC-GBP這種超區(qū)域中心部署節(jié)點(diǎn)的方式所生成的內(nèi)接樹(shù)的長(zhǎng)度長(zhǎng)于直骨架；其次，盡管策略O(shè)ASS和GSR都采用基于直骨架的連接方式，RSFP構(gòu)造的基于費(fèi)馬點(diǎn)的最短內(nèi)接樹(shù)更短（注：基于費(fèi)馬點(diǎn)的最短內(nèi)接樹(shù)是直骨架的一個(gè)特例）。如圖3(a)所示，當(dāng)中繼節(jié)點(diǎn)半徑等于50 m時(shí)，各策略所消耗的中繼節(jié)點(diǎn)數(shù)量隨著節(jié)點(diǎn)數(shù)的增加而增加。

圖2 節(jié)點(diǎn)個(gè)數(shù)為50、70時(shí)，各算法性能比較

在圖3(b)中可以看到，當(dāng)中繼節(jié)點(diǎn)半徑增加到100 m時(shí)，其消耗數(shù)量隨著節(jié)點(diǎn)個(gè)數(shù)的增加呈現(xiàn)出先增后減的趨勢(shì)。這是因?yàn)椴渴饏^(qū)域的大小固定，節(jié)點(diǎn)半徑越大節(jié)點(diǎn)數(shù)量越多，那么更多的節(jié)點(diǎn)會(huì)直接相連。這意味著更少的節(jié)點(diǎn)需要通過(guò)部署中繼節(jié)點(diǎn)的方式相連。此外，無(wú)論節(jié)點(diǎn)半徑等于50 m或100 m，本文提出的策略RSFP所需的中繼節(jié)點(diǎn)數(shù)量都是最少的。

圖3 半徑為50 m和100 m時(shí)，各算法性能比較

8 結(jié)束語(yǔ)

[1] XIAODING W, LI X, ZHOU S M. A straight skeleton based connectivity restoration strategy in the presence of obstacles for WSN[J]. Sensors, 2017, 17(10):2299.

[2] LALOUANI W, YOUNIS M, BADACHE N. Optimized repair of a partitioned network topology[J]. Computer Networks, 2017, 128: 63-77.

[3] EFRAT A, FEKETE S P, MITCHELL J S B, et al. Improved approximation algorithms for relay placement[J]. ACM Transactions on Algorithms (TALG), 2016, 12(2): 20.

[4] WANG X D, LI X, ZHOU S M. Restoration strategy based on optimal relay node placement in wireless sensor networks[J]. International Journal of Distributed Sensor Networks, 2015, 11(7): 409085.

[5] MISRA S, MAJD N E, HUANG H. Approximation algorithms for constrained relay node placement in energy harvesting wireless sensor networks[J]. IEEE Transactions on Computers,2014, 63(12): 2933-2947.

[6] YANG D, MISRA S, FANG X, et al. Two-tiered constrained relay node placement in wireless sensor networks: computational complexity and efficient approximations[J]. IEEE Transactions on Mobile Computing, 2012, 11(8): 1399-1411.

[7] MISRA S, HONG S D, XUE G, et al. Constrained relay node placement in wireless sensor networks: formulation and approximations[J]. IEEE/ACM Transactions on Networking (TON), 2010, 18(2): 434-447.

[8] CHENG X, DU D Z, WANG L, et al. Relay sensor placement in wireless sensor networks[J].Wireless Networks, 2008, 14(3): 347-355.

[9] LLOYD E L, XUE G. Relay node placement in wireless sensor networks[J]. IEEE Transactions on Computers, 2007, 56(1): 134-138.

[10] TANG J, HAO B, SEN A. Relay node placement in large scale wireless sensor networks[J]. Computer Communications, 2006, 29(4): 490-501.

[11] CHEN D, DU D Z, HU X D, et al. Approximations for steiner trees with minimum number of Steiner points[J]. Journal of Global Optimization, 2000, 18(1): 17-33.

[12] JOSHI Y K, YOUNIS M. Exploiting skeletonization to restore connectivity in a wireless sensor network[J]. Computer Communications, 2016, 75: 97-107.

[13] RANGA V, DAVE M, VERMA A K. Relay node placement to heal partitioned wireless sensor networks[J]. Computers & Electrical Engineering, 2015, 48: 371-388.

[14] 陳洪生, 石柯. 基于四邊形斯坦納樹(shù)的無(wú)線傳感器網(wǎng)絡(luò)連通恢復(fù)[J].計(jì)算機(jī)學(xué)報(bào),2014,37(2):457-469. CHEN H S, SHI K. Quadrilateral steiner tree based connectivity restoration for wireless sensor networks[J]. Chinese Journal of Computers, 2014,37(2):457-469.

[15] SENEL F, YOUNIS M. Novel relay node placement algorithms for establishing connected topologies[J]. Journal of Network and Computer Applications, 2016, (70): 114-130.

[16] ROBINS G,ZELIKOVSKY A. Tighter bounds for graph Steiner tree approximation[J]. SIAM Journal on Discrete Mathematics, 2005, 19(1): 122-134.

Fermat point based connectivity restoration strategy in networks

ZHOU Zhaobin1,2, ZHANG Hongyan3, WANG Xiaoding1,2

1. College of Mathematics and Informatics, Fujian Normal University, Fuzhou 350117, China 2. Fujian Provincial Key Lab of Network Security & Cryptology, Fuzhou 350117, China 3. Concord University College, Fujian Normal University, Fuzhou 350117, China

network availability, connectivity restoration, triangulation, fermat point

周趙斌（1989? ），男，江西南昌人，福建師范大學(xué)實(shí)驗(yàn)師，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全和網(wǎng)絡(luò)編碼。

章紅艷（1982? ），女，江蘇南通人，福建師范大學(xué)講師，網(wǎng)絡(luò)安全與計(jì)算。

汪曉丁（1982? ），男，福建安溪人，博士，福建師范大學(xué)副教授，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全、無(wú)線通信網(wǎng)絡(luò)、云計(jì)算與物聯(lián)網(wǎng)。

TP393

A

10.11959/j.issn.2096?109x.2019048

2019?01?09；

2019?06?06

汪曉丁，wangdin1982@ fjnu. edu. cn

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61702103）；福建省自然科學(xué)基金資助項(xiàng)目（No.2016J01289）；福建省教育廳基金資助項(xiàng)目（No.JAT160123）

The National Natural Science Foundation of China (No.61702103), The Natural Science Foundation of Fujian Province(No.2016J01289), Fujian Provincial Education Department Project (No.JAT160123)

周趙斌, 章紅艷, 汪曉丁. 基于費(fèi)馬點(diǎn)的網(wǎng)絡(luò)連通性修復(fù)策略[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 2019, 5(5): 32-38.

ZHOU Z B, ZHANG H Y, WANG X D. Fermat point based connectivity restoration strategy in networks[J]. Chinese Journal of Network and Information Security, 2019, 5(5): 32-38.