共查询到20条相似文献,搜索用时 15 毫秒
1.
《Computer Networks》2008,52(3):542-562
Wireless sensor networks can be used to collect environmental data from the interested area using multi-hop communication. As sensor networks have limited and non-rechargeable energy resources, energy efficiency is a very important issue in designing the topology, which affects the lifetime of sensor networks greatly. In this paper, the energy consumption is modeled and compared under the flat scheme and the clustering scheme, respectively. Motivated by the analysis, we propose an energy-efficient multi-level clustering algorithm called EEMC, which is designed to achieve minimum energy consumption in sensor networks. The cluster head election scheme is also considered in EEMC. EEMC terminates in O(log log N) iterations given N nodes. When the path loss exponent is 2, EEMC also achieves minimum latency. We focus on the case where sink node is remotely located and sensor nodes are stationary. Simulation results demonstrate that our proposed algorithm is effective in prolonging the network lifetime of a large-scale network, as well as low latency and moderate overhead across the network. 相似文献
2.
《Information and Computation》2006,204(5):697-712
In many large, distributed or mobile networks, broadcast algorithms are used to update information stored at the nodes. In this paper, we propose a new model of communication based on rendezvous and analyze a multi-hop distributed algorithm to broadcast a message in a synchronous setting. In the rendezvous model, two neighbors u and v can communicate if and only if u calls v and v calls u simultaneously. Thus nodes u and v obtain a rendezvous at a meeting point. If m is the number of meeting points, the network can be modeled by a graph of n vertices and m edges. At each round, every vertex chooses a random neighbor and there is a rendezvous if an edge has been chosen by its two extremities. Rendezvous enable an exchange of information between the two entities. We get sharp lower and upper bounds on the time complexity in terms of number of rounds to broadcast: we show that, for any graph, the expected number of rounds is between ln n and O (n2). For these two bounds, we prove that there exist some graphs for which the expected number of rounds is either O (ln (n)) or Ω (n2). For specific topologies, additional bounds are given. 相似文献
3.
Diagnosis of reliability is an important topic for interconnection networks. Under the classical PMC model, Dahura and Masson [5] proposed a polynomial time algorithm with time complexity O(N2.5) to identify all faulty nodes in an N-node network. This paper addresses the fault diagnosis of so called bijective connection (BC) graphs including hypercubes, twisted cubes, locally twisted cubes, crossed cubes, and Möbius cubes. Utilizing a helpful structure proposed by Hsu and Tan [20] that was called the extending star by Lin et al. [24], and noting the existence of a structured Hamiltonian path within any BC graph, we present a fast diagnostic algorithm to identify all faulty nodes in O(N) time, where N = 2n, n ? 4, stands for the total number of nodes in the n-dimensional BC graph. As a result, this algorithm is significantly superior to Dahura–Masson’s algorithm when applied to BC graphs. 相似文献
4.
5.
为延长无线传感网的生命期,提出了一种能量空洞缓解方法。网络被划分为若干虚拟栅格,以便于多跳传输。树形结构的数据上传路径则由各个簇头和移动Sink构成。此外,为缓解能量空洞的出现,Sink的移动轨迹被设计为可控的,从而有效均衡了能耗。仿真结果表明,该方法在多跳传感网络的节能方面表现较为良好。 相似文献
6.
The hybrid wireless sensor network is a promising application of wireless sensor networking techniques. The main difference between a hybrid WSN and a terrestrial wireless sensor network is the wireless underground sensor network, which communicates in the soil. In this paper, a hybrid wireless sensor network architecture is introduced. The framework to deploy and operate a hybrid WSN is developed. Experiments were conducted using a soil that was 50% sand, 35% silt, and 15% clay; it had a bulk density of 1.5 g/cm3 and a specific density of 2.6 cm? 3. The experiment was conducted for several soil moistures (5, 10, 15, 20 and 25%) and three signal frequencies (433, 868 and 915 MHz). The results show that the radio signal path loss is smallest for low frequency signals and low moisture soils. Furthermore, the node deployment depth affected signal attenuation for the 433 MHz signal. The best node deployment depth for effective transmission in a wireless underground sensor network was determined. 相似文献
7.
《Journal of Network and Computer Applications》2012,35(6):1901-1917
A wireless sensor network (WSN) is a large collection of sensor nodes with limited power supply, constrained memory capacity, processing capability, and available bandwidth. The main problem in event gathering in wireless sensor networks is the formation of energy-holes or hot spots near the sink. Due to the restricted communication range and high network density, events forwarding in sensor networks is very challenging, and require multi-hop data forwarding. Improving network lifetime and network reliability are the main factors to consider in the research associated with WSN. In static wireless sensor networks, sensors nodes close to the sink node run out of energy much faster than nodes in other parts of the monitored area. The nodes near the sink are more likely to use up their energy because they have to forward all the traffic generated by the nodes farther away to the sink. The uneven energy consumption results in network partitioning and limit the network lifetime. To this end, we propose an on-demand and multipath routing algorithm that utilizes the behavior of real termites on hill building termed Termite-hill which support sink mobility. The main objective of our proposed algorithm is to efficiently relay all the traffic destined for the sink, and also balance the network energy. The performance of our proposed algorithm was tested on static, dynamic and mobile sink scenarios with varying speed, and compared with other state-of-the-art routing algorithms in WSN. The results of our extensive experiments on Routing Modeling Application Simulation Environment (RMASE) demonstrated that our proposed routing algorithm was able to balance the network traffic load, and prolong the network lifetime. 相似文献
8.
We address the problem of determining all extreme supported solutions of the biobjective shortest path problem. A novel Dijkstra-like method generalizing Dijkstra׳s algorithm to this biobjective case is proposed. The algorithm runs in O(N(m+n log n)) time to solve one-to-one and one-to-all biobjective shortest path problems determining all extreme supported non-dominated points in the outcome space and one supported efficient path associated with each one of them. Here n is the number of nodes, m is the number of arcs and N is the number of extreme supported points in outcome space for the one-to-all biobjective shortest path problem. The memory space required by the algorithm is O(n+m) for the one-to-one problem and O(N+m) for the one-to-all problem. A computational experiment comparing the performance of the proposed methods and state-of-the-art methods is included. 相似文献
9.
Data partitioning and scheduling is one the important issues in minimizing the processing time for parallel and distributed computing system. We consider a single-level tree architecture of the system and the case of affine communication model, for a general m processor system with n rounds of load distribution. For this case, there exists an optimal activation order, optimal number of processors m* (m * ≤ m), and optimal rounds of load distribution n* (n * ≤ n), such that the processing time of the entire processing load is a minimum. This is a difficult optimization problem because for a given activation order, we have to first identify the processors that are participating (in the computation process) in every round of load distribution and then obtain the load fractions assigned to them, and the processing time. Hence, in this paper, we propose a real-coded genetic algorithm (RCGA) to solve the optimal activation order, optimal number of processors m* (m * ≤ m), and optimal rounds of load distribution n* (n * ≤ n), such that the processing time of the entire processing load is a minimum. RCGA employs a modified crossover and mutation operators such that the operators always produce a valid solution. Also, we propose different population initialization schemes to improve the convergence. Finally, we present a comparative study with simple real-coded genetic algorithm and particle swarm optimization to highlight the advantage of the proposed algorithm. The results clearly indicate the effectiveness of the proposed real-coded genetic algorithm. 相似文献
10.
Mohamed K. Watfa Haitham Al-Hassanieh Samir Salmen 《Journal of Network and Computer Applications》2013,36(2):949-958
One major limitation in a Wireless Sensor Network (WSN) is the energy dissipation of the nodes and the lifetime of the node's battery. The traffic in a sensor network follows a many-to one pattern, where nodes nearer to the sink carry heavier traffic loads. Therefore, the nodes around the sink would deplete their energy faster, leading to what is known as an energy hole around the sink. The aim of this paper is to overcome the power constraints in WSN by wirelessly charging the nodes. We investigate both theoretically and through simulations whether the physical phenomenon of long-lifetime resonant electromagnetic states with localized slowly-evanescent field patterns can be used to transfer energy efficiently over multiple hops. We specify the hardware the modified sensor node needs in order to wirelessly transmit and receive energy and introduce a new layer called the charging layer into the sensor network protocol stack. Our results show that multi-hop wireless energy transfer can be done with an efficiency as high as 20% over 8 hops. The work in this paper is the first that addresses multi-hop wireless energy transfer in sensor networks and is the building block for our and other future research in this area. 相似文献
11.
《Journal of Parallel and Distributed Computing》1999,57(2):224-235
We present a parallel algorithm for solving thenext element search problemon a set of line segments, using a BSP-like model referred to as thecoarse grained multicomputer(CGM). The algorithm requiresO(1) communication rounds (h-relations withh=O(n/p)),O((n/p) log n) local computation, andO((n/p) log p) memory per processor, assumingn/p⩾p. Our result implies solutions to the point location, trapezoidal decomposition, and polygon triangulation problems. A simplified version for axis-parallel segments requires onlyO(n/p) memory per processor, and we discuss an implementation of this version. As in a previous paper by Develliers and Fabri (Int. J. Comput. Geom. Appl.6(1996), 487–506), our algorithm is based on a distributed implementation of segment trees which are of sizeO(n log n). This paper improves onop. cit.in several ways: (1) It studies the more general next element search problem which also solves, e.g., planar point location. (2) The algorithms require onlyO((n/p) log n) local computation instead ofO(log p*(n/p) log n). (3) The algorithms require onlyO((n/p) log p) local memory instead ofO((n/p) log n). 相似文献
12.
《Journal of Parallel and Distributed Computing》2000,60(9):1103-1124
We present a simple parallel algorithm for the single-source shortest path problem in planar digraphs with nonnegative real edge weights. The algorithm runs on the EREW PRAM model of parallel computation in O((n2ε+n1−ε) log n) time, performing O(n1+ε log n) work for any 0<ε<1/2. The strength of the algorithm is its simplicity, making it easy to implement and presumable quite efficient in practice. The algorithm improves upon the work of all previous parallel algorithms. Our algorithm is based on a region decomposition of the input graph and uses a well-known parallel implementation of Dijkstra's algorithm. The logarithmic factor in both the work and the time can be eliminated by plugging in a less practical, sequential planar shortest path algorithm together with an improved parallel implementation of Dijkstra's algorithm. 相似文献
13.
《Journal of Symbolic Computation》1998,26(3):339-341
Fix a finite commutative ringR. Letuandvbe power series overR, withv(0) = 0. This paper presents an algorithm that computes the firstnterms of the compositionu(v), given the firstnterms ofuandv, inn1 + o(1)ring operations. The algorithm is very fast in practice whenRhas small characteristic. 相似文献
14.
《Information and Computation》2007,205(7):1078-1095
Assume that G = (V, E) is an undirected graph, and C ⊆ V. For every v ∈ V, denote Ir(G; v) = {u ∈ C: d(u,v) ≤ r}, where d(u,v) denotes the number of edges on any shortest path from u to v in G. If all the sets Ir(G; v) for v ∈ V are pairwise different, and none of them is the empty set, the code C is called r-identifying. The motivation for identifying codes comes, for instance, from finding faulty processors in multiprocessor systems or from location detection in emergency sensor networks. The underlying architecture is modelled by a graph. We study various types of identifying codes that are robust against six natural changes in the graph; known or unknown edge deletions, additions or both. Our focus is on the radius r = 1. We show that in the infinite square grid the optimal density of a 1-identifying code that is robust against one unknown edge deletion is 1/2 and the optimal density of a 1-identifying code that is robust against one unknown edge addition equals 3/4 in the infinite hexagonal mesh. Moreover, although it is shown that all six problems are in general different, we prove that in the binary hypercube there are cases where five of the six problems coincide. 相似文献
15.
We address the problem of determining a complete set of extreme supported efficient solutions of biobjective minimum cost flow (BMCF) problems. A novel method improving the classical parametric method for this biobjective problem is proposed. The algorithm runs in O(Nn(m + nlogn)) time determining all extreme supported non-dominated points in the outcome space and one extreme supported efficient solution associated with each one of them. Here n is the number of nodes, m is the number of arcs and N is the number of extreme supported non-dominated points in outcome space for the BMCF problem. The memory space required by the algorithm is O(n + m) when the extreme supported efficient solutions are not required to be stored in RAM. Otherwise, the algorithm requires O(N + m) space. Extensive computational experiments comparing the performance of the proposed method and a standard parametric network simplex method are presented. 相似文献
16.
《Journal of Parallel and Distributed Computing》1999,56(1):47-70
In this paper we describe scalable parallel algorithms for building the convex hull and a triangulation ofncoplanar points. These algorithms are designed for thecoarse grained multicomputermodel:pprocessors withO(n/p)⪢O(1) local memory each, connected to some arbitrary interconnection network. They scale over a large range of values ofnandp, assuming only thatn⩾p1+ε(ε>0) and require timeO((Tsequential/p)+Ts(n, p)), whereTs(n, p) refers to the time of a global sort ofndata on approcessor machine. Furthermore, they involve only a constant number of global communication rounds. Since computing either 2D convex hull or triangulation requires timeTsequential=Θ(n log n) these algorithms either run in optimal time,Θ((n log n)/p), or in sort time,Ts(n, p), for the interconnection network in question. These results become optimal whenTsequential/pdominatesTs(n, p) or for interconnection networks like the mesh for which optimal sorting algorithms exist. 相似文献
17.
《Computer Networks》2008,52(16):3101-3118
Wireless sensor networks enhance our ability to monitor the physical world. Many recent researches on wireless sensor networks have focused on aspects such as routing, node cooperation, and energy consumption. In addition to these topics, the positioning service is also an important function in sensor networks. This paper presents a multiple power-level positioning algorithm, discusses its capabilities, and evaluates its performance in various environments. The simulation results show that the proposed algorithm exhibits better accuracy than do traditional single power-level methods. In critical situations such as reference node failure, unstable radio transmission range and beacon collision, the proposed algorithm still performs well. Finally, the positioning method is implemented on a sensor network test bed, and the actual measurements show that, the average estimation error is 2.5 m when three power-levels are used and adjacent reference nodes are 12 m apart in an outdoor environment. 相似文献
18.
In order to detect the installation compressive stress and monitor the stress relaxation between two bending surfaces on a defensive furnishment, a wireless compressive-stress/relaxation-stress measurement system based on pressure-sensitive sensors is developed. The flexible pressure-sensitive stress sensor array is fabricated by using carbon black-filled silicone rubber-based composite. The wireless stress measurement system integrated with this sensor array is tested with compressive stress in the range from 0 MPa to 3 MPa for performance evaluation. Experimental results indicate that the fractional change in electrical resistance of the pressure-sensitive stress sensor changes linearly and reversibly with the compressive stress, and its fractional change goes up to 355% under uniaxial compression; the change rate of the electrical resistance can track the relaxation stress and give out a credible measurement in the process of stress relaxation. The relationship between input (compressive stress) and output (the fractional change in electrical resistance) of the pressure-sensitive sensor is ΔR/R0 = σ × 1.2 MPa?1. The wireless compressive stress measurement system can be used to achieve sensitivity of 1.33 V/MPa to the stress at stress resolution of 920.3 Pa. The newly developed wireless stress measurement system integrated with pressure-sensitive carbon black-filled silicone rubber-based sensors has advantages such as high sensitivity to stress, high stress resolution, simple circuit and low energy consumption. 相似文献
19.
We introduce a GPU-based parallel vertex substitution (pVS) algorithm for the p-median problem using the CUDA architecture by NVIDIA. pVS is developed based on the best profit search algorithm, an implementation of vertex substitution (VS), that is shown to produce reliable solutions for p-median problems. In our approach, each candidate solution in the entire search space is allocated to a separate thread, rather than dividing the search space into parallel subsets. This strategy maximizes the usage of GPU parallel architecture and results in a significant speedup and robust solution quality. Computationally, pVS reduces the worst case complexity from sequential VS’s O(p · n2) to O(p · (n ? p)) on each thread by parallelizing computational tasks on GPU implementation. We tested the performance of pVS on two sets of numerous test cases (including 40 network instances from OR-lib) and compared the results against a CPU-based sequential VS implementation. Our results show that pVS achieved a speed gain ranging from 10 to 57 times over the traditional VS in all test network instances. 相似文献
20.
Anfeng Liu Deyu Zhang Penghui Zhang Guohua Cui Zhigang Chen 《Peer-to-Peer Networking and Applications》2014,7(3):255-273
In wireless sensor networks (WSNs), sensor nodes close to the sink consume more energy than others because they are burdened with heavier relay traffic destined for the sink and trend to die early, forming hotspots or energy holes in WSNs. It has a serious impact on network lifetime. In this paper, three optimization algorithms are proposed to mitigate hotspots and prolong network lifetime for adaptive Mary Phase Shift Keying (MPSK) based wireless sensor networks while transport delay and reliability can be still guaranteed. Based on the insight gained into the relationship between nodal data load and energy consumption in different regions, the first algorithm (GlobalSame) can extend considerably the network lifetime by selecting the optimal nodal transmission radius r, bit error rate ε and transmission rate allocations in bits per symbol (BPS) τ. The second algorithm (RingSame) can further improve network lifetime by comparison to the GlobalSame algorithm, which by selecting different ε i and τ i for nodes in different regions under constraints of total BER and transport delay . While the third algorithm (NodeDiff) can further improve the network lifetime by adopting different BER ε and BPS τ parameters of the same node for data packets received according to its distance to the sink. Extensive simulation studies show that our algorithms do considerably prolong the network lifetime. 相似文献