共查询到20条相似文献,搜索用时 15 毫秒
1.
In this paper, we present a Dantzig-Wolfe reformulation for the Minimum Cost Hop-and-root Constrained Forest Problem and discuss a Column Generation (CG) method to evaluate its Linear Programming (LP) bounds. For solving one of two types of pricing problems that arise in CG, we compared two solution strategies: Dynamic Programming and a Branch-and-cut (BC) algorithm. In general, CG performed much better when BC was used. Not only the LP bounds implied by the proposed reformulation are much stronger than the multi-commodity flow bounds from the literature, but also could be evaluated with less computational time. A Column Generation Heuristic was discussed and implemented, providing upper bounds that are, on average, within 2.3% of optimality. 相似文献
2.
Roberto Montemanni Parvaz Mahdabi 《Journal of Mathematical Modelling and Algorithms》2011,10(2):145-162
A matheuristic approach, where concepts from linear programming are integrated into an evolutionary algorithm, is proposed. It is tested on a problem arising in wireless sensor networks: a topology with minimum total power expenditure, that connects a source node to all the other nodes of the network, has to be identified. Experimental results are presented. 相似文献
3.
This paper considers variations of the minimum connected vertex cover problem to be found in the study of wireless network design. A simple, theoretic formulation is followed by a discussion of practical constraints. Two algorithms are given and results compared. 相似文献
4.
无线传感器网络传输可靠性计算 总被引:3,自引:0,他引:3
无线传感器网络是由传感器节点和汇聚节点组成的以数据为中心的无线网络.汇聚节点根据一个或多个源节点传送的采集数据对事件进行监测和判断,而数据传输的可靠性直接影响到监测和判断的准确性.在无线传感器网络中,一方面,网络拓扑结构是动态变化的,数据传输的可靠性与网络拓扑结构有关;另一方面,网络中的传感器节点是能最受限的,因此传输的可靠性还与节点的能昔密切相关-针对无线传感器网络的特点,给出了无线传感器网络的传输可靠性概念,提出一种传输可靠性度量,分别在有数据融合和无数据融合两种情况下,对网络节点的能耗情况进行了分析,获得r网络节点正常工作的概率随时间的变化关系,并导出数学表达式,用于计算节点所产生的数据包成功传输给汇聚节点的概率,从而获得了求整个网络传输可靠性的计算方法. 相似文献
5.
基于在传感器网络中基站能够测量未知节点(M)S发出的辐射到达不同基站的时间差和它们之间的相对角度,提出了一种基于TDOA/AOA混合三维定位算法,根据基站测得的到达时间差(TDOA)和到达角度(AOA),将两种信息进行融合,建立节点位置估计值的混合算法,得到三维空间内的无线传感器节点坐标.仿真结果表明:在AOA测量值精度比较高时,此种混合算法能够实现比其他算法更好的定位性能 相似文献
6.
7.
《数学的实践与认识》2015,(19)
利用微积分计算和Brun's筛法,得到了部署在在单位正方形区域上服从均匀分布n个传感器节点构成的无线安全传感器网络孤立点数目的近似分布.我们证明了对于某个常数c,如果任意两个传感器节点之间最大通信半径rn满足nπr_n~2p'=ln n+c,这里p'是两个传感器节点至少有一个公共密钥的概率,则无线传感器网络孤立点数目近似服从参数为e~(-c)的Poisson分布. 相似文献
8.
多无线WMN中干扰最小化信道分配算法研究 总被引:1,自引:1,他引:0
侯春雨 《数学的实践与认识》2010,40(7)
为了提高无线迈适网的通信容量,网络中的每个路由节点均配备有多个无线网卡,并提供多个可用的无线信道.如何将这些信道合理地分配到网络的各个通信链路上,使得整个网络的干扰最小是一个至关重要问题.分析了基于禁忌搜索的信道分配算法,并针对该算法存在的问题,提出了初步的改进算法. 相似文献
9.
《Journal of computational science》2013,4(4):199-208
Wireless Sensor Networks lifetime mainly depends on energy saving efficiency. In this paper, we propose an energy-efficient self-stabilizing topology control protocol for WSN. We reduce the transmission power of each node so as to maintain network connectivity while saving maximum energy. Besides, we propose an approximation algorithm for minimum weighted connected dominating set that builds a virtual backbone formed by sensors with maximum energy. This backbone is used for efficient routing purpose. We proved the algorithm correctness and through our simulation results, we showed the efficiency of our proposed solution. 相似文献
10.
José F. Martínez Miguel S. Familiar Iván Corredor Ana B. García Sury Bravo Lourdes López 《Mathematical and Computer Modelling》2011,53(3-4):485-503
Providing necessary background for provisioning of a new generation of enriched services over Wireless Sensor Networks is the main effort that the scientific community is currently carrying out. These services have improved a great number of aspects related to pervasive systems such as saving resources, efficiency, reliability, scalability and low power consumption. In this paper, SMS middleware, using an event-based service model, is presented. This novel approach makes up the design requirements previously mentioned by implementing a dynamic memory kernel and a variable payload multiplexing mechanism for the information events in order to provide advanced services. The results obtained over real-world deployments, especially those related with provision of e-Health services, reflect a significant improvement over other similar proposals, such as the RUNES approach: 50% lower memory overhead, 53% lower software components load time and 12% lower event’s propagation time. 相似文献
11.
本文利用(υ_s,υ_t)平面双流网络的平面性,找出并证明了该网络中最小费用双流的充要条件,最后给出了一个算法并估计了复杂性. 相似文献
12.
目前无限传感器网络K覆盖问题的解决机制大都有颇为苛刻的假设条件,如要求节点具有很强的能量、节点的感知区域能被精确定义等.提出了一个基于布尔感知理论的分布式网格模型及相应的K区域覆盖算法,能够很好地处理感知区域形状不规则及大小发生变化的K覆盖问题,算法时间复杂度小,适用范围广泛.仿真实验证明了算法的有效性. 相似文献
13.
14.
运用图论理论,提出分布式无线传感器网络有效网络划分算法(RMIS)以实现WSN可靠数据传输需求.算法各节点间连通度和能量为优化约束,采用随机分布式极大独立集理论进行监测网格划分.数学证明算法在经过期望松弛同步轮数为O(log n)轮收敛.通过仿真分析,依RMIS算法划分网格可有效提高数据融合效率,减少数据传输平均距离,提高网络运行稳定性. 相似文献
15.
Improving Construction for Connected Dominating Set with Steiner Tree in Wireless Sensor Networks 总被引:2,自引:0,他引:2
Manki Min Hongwei Du Xiaohua Jia Christina Xiao Huang Scott C.-H. Huang Weili Wu 《Journal of Global Optimization》2006,35(1):111-119
The connected dominating set plays an important role in ad hoc wireless networking. Many constructions for approximating the minimum connected dominating set have been proposed in the
literature. In this paper, we propose a new one with Steiner tree, which produces approximation solution within a factor of
6.8 from optimal. This approximation algorithm can also be implemented distributedly. 相似文献
16.
Jeroen Kuipers 《International Journal of Game Theory》1997,26(3):367-377
In this paper we consider a generalization of the minimum cost spanning tree game. The generalized model allows for more than one supplier, where each supplier offers a different type of service to the customers and each customer specifies a non-empty subset of these suppliers to which he wishes to be connected. We show that the core of such a game may be empty, but that it is always non-empty if there is at least one customer who wants to be connected to all suppliers. Furthermore, the core is always non-empty if there are at most two suppliers. 相似文献
17.
Rahul Varshney A. H. Ansari M. J. Ahsan 《Journal of Mathematical Modelling and Algorithms》2013,12(4):373-381
When more than one (say p) characteristics in multivariate stratified population are defined on each unit of the population, the individual optimum allocations may differ widely and can not be used practically. Moreover, there may be a situation such that no standard allocation is advisable to all the strata, for one reason or another. In such a situation, Clark and Steel (J R Stat Soc, Ser D Stat 49(2):197–207, 2000) suggested that different allocations may be used for different groups of strata having some common characteristics for double sampling in stratification. Later on, Ahsan et al. (Aligarh J Stat 25:87–97, 2005) used the same concept in univariate stratified sampling. They minimized the variance of the stratified sample mean for a fixed cost to obtain an allocation and called this allocation “mixed allocation”. In the present paper, a “compromise mixed allocation” is worked out for the fixed precisions of the estimates of the p-population means of a multivariate stratified population. A numerical example is also presented. 相似文献
18.
无容量限制的最小费用流问题 总被引:2,自引:0,他引:2
本文研究了无容量限制的带固定费用和可变费用的单物资和二物资的最小费用流问题,并分别给出了多项式算法.最后应用该算法,计算了一个二物资的最小费用流问题的实例. 相似文献
19.
Yanbing Liu Simei TianWenping Hu Congcong Xing 《Communications in Nonlinear Science & Numerical Simulation》2012,17(8):3267-3278
Security issue is a vital and active topic in the research of Wireless Sensor Networks (WSN). After surveying the existing encryption algorithms for WSN briefly, we propose a new chaotic block cipher for WSN and then compare the performance of this cipher with those of RC5 and RC6 block ciphers. Simulation result demonstrates that better performance in WSN encryption algorithms can be achieved using the new cipher. 相似文献