周趙斌，章紅艷，汪曉丁

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

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

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

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

1 引言

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

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

Chen等[11]提出基于四邊形構(gòu)造的近似算法，不僅證明此算法近似比為3，并且證明了單純采用斯坦納化最小生成樹（MST）的方法來修復(fù)連通性的近似比也為3。在此基礎(chǔ)上，Cheng等[8]提出基于三角形構(gòu)造結(jié)合斯坦納化MST的近似算法，以及基于3-超圖最小生成樹的隨機(jī)近似算法，并證明這兩者的近似比分別為3和2.5。盡管后者近似比較低，但其算法復(fù)雜度偏高。Lloyd等[9]提出一種改進(jìn)的斯坦納化MST法，近似比在6~7之間。Tang等[10]將部署區(qū)域劃分成網(wǎng)絡(luò)并對網(wǎng)絡(luò)分簇，對于每個網(wǎng)格部署一個節(jié)點作為簇頭負(fù)責(zé)簇內(nèi)與簇間通信，從而恢復(fù)網(wǎng)絡(luò)的1-連通性，此算法的近似比為4.5。Efrat等[3]、Yang等[6]、Misra等[5,7]對于節(jié)點與節(jié)點、節(jié)點與中繼、中繼與中繼這3種不同連接方式給予相應(yīng)的權(quán)值并以此構(gòu)造賦權(quán)完全圖，然后根據(jù)網(wǎng)絡(luò)不同的應(yīng)用場景，結(jié)合目前最優(yōu)的最小權(quán)斯坦納樹構(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]通過仿真實驗驗證算法性能。Ranga等[13]提出一個基于0梯度點的修復(fù)算法。此算法首先利用連通分支構(gòu)造一個凸殼，然后構(gòu)造凸殼內(nèi)各點與連通分支之間的距離函數(shù)并計算出能夠使該函數(shù)梯度為0的點，最后以這個點為中心部署中繼節(jié)點來連接各個分支。Joshi等[12]利用網(wǎng)絡(luò)的直骨架并結(jié)合節(jié)點的傳輸半徑，規(guī)劃出一條最優(yōu)的中繼節(jié)點部署路線。陳洪生等[14]給出了一個基于四邊形的連通度修復(fù)算法并證明了其時間和信息復(fù)雜度。

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

3 預(yù)備知識

4 系統(tǒng)模型

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

5 RSFP策略

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

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

圖1 一個RSFP示例

6 理論分析

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

證明

證明

證明

證畢。

證明

證畢。

7 仿真實驗

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

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

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

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

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

8 結(jié)束語

[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] 陳洪生, 石柯. 基于四邊形斯坦納樹的無線傳感器網(wǎng)絡(luò)連通恢復(fù)[J].計算機(jī)學(xué)報,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é)實驗師，主要研究方向為網(wǎng)絡(luò)與信息安全和網(wǎng)絡(luò)編碼。

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

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

TP393

A

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

2019?01?09；

2019?06?06

汪曉丁，wangdin1982@ fjnu. edu. cn

國家自然科學(xué)基金資助項目（No.61702103）；福建省自然科學(xué)基金資助項目（No.2016J01289）；福建省教育廳基金資助項目（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)

周趙斌, 章紅艷, 汪曉丁. 基于費馬點的網(wǎng)絡(luò)連通性修復(fù)策略[J]. 網(wǎng)絡(luò)與信息安全學(xué)報, 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.