计算机科学 ›› 2018, Vol. 45 ›› Issue (7): 110-115.doi: 10.11896／j.issn.1002-137X.2018.07.018
徐涛1,2,杜昱萱1,吕宗磊1,2
XU Tao1,2,DU Yu-xuan1,LV Zong-lei1,2
摘要： 针对用最少的传感器节点覆盖感兴趣区域并确保传感器节点之间连通的最优化问题,提出了基于线性规划的传感器节点布局模型。该模型通过传递闭包计算连通性,将命题逻辑式转化为线性方程组,从而求得该模型的精确解。同时,设计了在不同网格规模下的全覆盖实验验证了该模型的正确性。该模型可以自行设定最大跳数、感兴趣区域和汇聚节点的位置,求得的精确解可作为传感器节点布局模型近似解的比较基准。
中图分类号:
| [1]QIAN Z H,WANG Y J.Internet of Things-oriented Wireless Sensor Networks Review[J].Journal of Electronics and Information Technology,2013,35(1):215-227.(in Chinese) 钱志鸿,王义君.面向物联网的无线传感器网络综述[J].电子与信息学报,2013,35(1):215-227. [2]DEYAB T M,BAROUDI U,SELIM S Z.Optimal Placement of Heterogeneous Wireless Sensor and Relay Nodes[C]∥2011 7th International Wireless Communications and Mobile Computing Conference (IWCMC).IEEE,2011:65-70. [3]BAROUDI U,YOUNIS M.Optimal Node Repositioning for To-lerating Node Failure in Wireless Sensor Actor Network[C]∥2010 25th Biennial Symposium on Communications (QBSC).IEEE,2010:67-71. [4]BARI A,JAEKEL A,JIANG J,et al.Design of Fault Tolerant Wireless Sensor Networks Satisfying Survivability and Lifetime Requirements[J].Comput Communications,2012,35(3):320-333. [5]BASAGNI S,B L NI L,GJANCI P,et al.Maximizing the Valueof Sensed Information in Underwater Wireless Sensor Networks via an Autonomous Underwater Vehicle[C]∥IEEE INFOCOM 2014-IEEE Conference on Computer Communications.IEEE,2014:988-996. [6]HE T,CHIN K W,SOH S.On Wireless Power Transfer and Max Flow in Rechargeable Wireless Sensor Networks [J].IEEE Access,2016,4:4155-4167. [7]SUN Z,SHU Y,XING X,et al.LPOCS:A Novel Linear Programming Optimization Coverage Scheme in Wireless Sensor Networks[J].Adhoc & Sensor Wireless Networks,2016,33(1-4):173-197. [8]DANTZIG G B.Linear Programming and Extensions [M].Princeton:Princeton University Press,2016. [9]LUENBERGER D G,YE Y.Linear and nonlinear programming[M].Reading,MA:Addison-wesley,1984. [10]MORRISON D R,JACOBSON S H,SAUPPE J J,et al.Branch-and-bound algorithms:A survey of recent advances in searching,branching,and pruning[J].Discrete Optimization,2016,19:79-102. [11]BEZERRA M A,DOS SANTOS Q O,SANTOS A G,et al.Simplex optimization:A tutorial approach and recent applications in analytical chemistry[J].Microchemical Journal,2016,124:45-54. [12]ABIDIN H Z,DIN N M,JALIL Y E.Multi-Objective Optimization (MOO) Approach for Sensor Node Placement in WSN[C]∥2013 7th International Conference on Signal Processing and Communication Systems (ICSPCS).IEEE,2013:1-5. [13]ROSEN K H.Discrete Mathematics and its Applications[M].NewYork:McGraw-Hill,2012. [14]FEARNLEY J,SAVANI R.The complexity of the simplex me-thod[C]∥Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing.ACM,2015:201-208. [15]CARNIELLI W,MARIANO H L,MATULOVIC M.Reconciling first-order logic to algebra[J].CLE e-Prints,2015,15(1):1-26. [16]CARNIELLI W,MATULOVIC M.The method of polynomialring calculus and its potentialities[J].Theoretical Computer Science,2015,606:42-56. [17]ZHANG H,HOU J C.Maintaining sensing coverage and connectivity in large sensor networks[J].Ad Hoc & Sensor Wireless Networks,2005,1(1／2):89-124. |
| [1] | 黄国兴, 杨泽铭, 卢为党, 彭宏, 王静文. 利用粒子滤波方法求解数据包络分析问题 Solve Data Envelopment Analysis Problems with Particle Filter 计算机科学, 2022, 49(6A): 159-164. https://doi.org/10.11896/jsjkx.210600110 |
| [2] | 朱丽花, 王玲, 唐麒, 魏急波. 一种针对动态部分可重构SoC软硬件划分的高效MILP模型 Efficient MILP Model for HW/SW Partitioning of Dynamic Partial Reconfigurable SoC 计算机科学, 2020, 47(4): 18-24. https://doi.org/10.11896/jsjkx.190300001 |
| [3] | 李珊珊, 陈黎, 唐裕婷, 王艺霖, 于中华. 利用整数线性规划自动抽取多样性关键短语 Automatic Extraction of Diversity Keyphrase by Utilizing Integer Liner Programming 计算机科学, 2019, 46(6A): 56-59. |
| [4] | 赵天骐, 陆佃杰, 刘一良, 张桂娟. 基于内容感知和团购策略的云视频分发网络 Content-aware and Group-buying Based Cloud Video Delivery Networks 计算机科学, 2018, 45(6A): 342-347. |
| [5] | 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究 Approximation Algorithm for Weighted Mixed Domination Problem 计算机科学, 2018, 45(4): 83-88. https://doi.org/10.11896/j.issn.1002-137X.2018.04.012 |
| [6] | 庞博,金乾坤,合尼古力·吾买尔,齐兴斌. 软件定义网络中基于网络切片和ILP模型的路由方案 Routing Scheme Based on Network Slicing and ILP Model in SDN 计算机科学, 2018, 45(4): 143-147. https://doi.org/10.11896/j.issn.1002-137X.2018.04.023 |
| [7] | 周杰,於志勇,郭文忠,郭龙坤,朱伟平. “t-时隙k-覆盖”群智感知任务的参与者选择方法 Participant Selection Algorithm for t-Sweep k-Coverage Crowd Sensing Tasks 计算机科学, 2018, 45(2): 157-164. https://doi.org/10.11896/j.issn.1002-137X.2018.02.028 |
| [8] | 吴秀丽,周永权. 一种基于混沌和单纯形法的水波优化算法 Improved Water Wave Optimization Algorithm Based on Chaos Optimization and Simplex Method 计算机科学, 2017, 44(5): 218-225. https://doi.org/10.11896/j.issn.1002-137X.2017.05.039 |
| [9] | 梅海涛,华继学,王毅. 求解非线性规划问题的改进直觉模糊遗传算法 Improved Intuitionistic Fuzzy Genetic Algorithm for Nonlinear Programming Problems 计算机科学, 2016, 43(9): 250-254. https://doi.org/10.11896/j.issn.1002-137X.2016.09.050 |
| [10] | 张航,佟晓筠,王 翥. WSN中考虑负载均衡的贪婪寻优中继节点布局算法的研究 Research on Relay Node Placement Considering Load Balancing Based on Greedy Optimization Algorithm in Wireless Sensor Networks 计算机科学, 2015, 42(6): 115-119. https://doi.org/10.11896/j.issn.1002-137X.2015.06.026 |
| [11] | 赖 锴,王新兵. 一种改进的WSN异常检测和定位算法研究 Research on Improved Anomaly Detection and Localization Algorithm in Wireless Sensor Networks 计算机科学, 2015, 42(4): 89-93. https://doi.org/10.11896/j.issn.1002-137X.2015.04.017 |
| [12] | 刘海平. 基于混合人工鱼群算法的凸多面体碰撞检测研究 Research on Collision Detection of Convex Polyhedron Based on Mixed Artificial Fish Swarm Algorithm 计算机科学, 2014, 41(Z6): 61-63. |
| [13] | 李贵,陈韶刚,韩子扬,李征宇,孙平,孙焕良. 基于Web的实例扩展与属性值扩充方法 Entities Expansion and Attribute Values Discovery Method Based on Web 计算机科学, 2014, 41(Z11): 411-418. |
| [14] | 陈翔,顾庆,陈道蓄,蒋峥峥. 回归测试中测试用例集缩减问题的研究 Systematic Review of Test Suite Minimization for Regression Testing 计算机科学, 2014, 41(9): 196-204. https://doi.org/10.11896/j.issn.1002-137X.2014.09.037 |
| [15] | 刘宴涛,汪博,安建平,刘珩. 采用随机移动模型的无线自组织仿真网络连通性分析 Analysis to Connectivity of Wireless Ad hoc Simulating Networks with Random Mobility Models 计算机科学, 2013, 40(Z6): 287-290. |
|
||
首页