http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
Collision-tolerant broadcast scheduling in duty-cycled wireless sensor networks
Le, Duc Tai,Le Duc, Thang,Zalyubovskiy, Vyacheslav V.,Kim, Dongsoo S.,Choo, Hyunseung Academic Press 2017 Journal of parallel and distributed computing Vol.100 No.-
<P><B>Abstract</B></P> <P>The minimum-latency broadcast problem in duty-cycled wireless sensor networks has received significant attention over the last few years. A common approach for the problem is to assign collision-free transmitting times to forwarding nodes for disseminating a message from one source node to all other nodes according to their given duty-cycle schedules and transmission ranges. However, preventing collision for all transmissions may increase latency in the broadcast schedules. This paper proposes a novel strategy of Collision-Tolerant Scheduling (CTS) that offers an opportunity to reduce broadcast latency by allowing collisions at non-critical nodes to speed up the broadcast process for critical ones. The completion of broadcast scheduling, i.e. all nodes receive a broadcast message, is ensured by additionally transmitting the message to non-critical nodes experiencing collision. We employ the scheduling strategy in two proposed broadcast schemes: Degree-based CTS (DCTS) and MIS-based CTS (MCTS), which select forwarding nodes based on the node degree and maximal independent set information, respectively. The results of both theoretical analysis and simulation reveal the remarkable advantages of CTS in minimizing broadcast latency in duty-cycled WSNs. DCTS and MCTS guarantee approximation ratios of ( Δ − 1 ) T and 12 T in terms of broadcast latency, where Δ and T denote the maximum node degree and the number of time slots in a working period, respectively. The two schemes reduce to at least 94 percent of the broadcast latency compared with existing schemes, while slightly increasing the number of transmissions due to the additional transmissions. Thanks to the latency reduction, the proposed schemes require 93 percent less energy than existing ones.</P> <P><B>Highlights</B></P> <P> <UL> <LI> A novel scheduling strategy for broadcast latency minimization in duty-cycled WSNs. </LI> <LI> Allowing collisions at non-critical nodes to speed up the broadcast process. </LI> <LI> The completion of broadcast scheduling is ensured by additional transmissions. </LI> <LI> Achieving significant improvement in both theoretical and simulation results. </LI> </UL> </P>
Le, Duc-Tai,Im, Giyeol,Le Duc, Thang,Zalyubovskiy, Vyacheslav V.,Kim, Dongsoo S.,Choo, Hyunseung WILEY INTERSCIENCE 2018 WIRELESS COMMUNICATIONS AND MOBILE COMPUTING Vol.2018 No.-
<P>Minimum latency scheduling has arisen as one of the most crucial problems for broadcasting in duty-cycled Wireless Sensor Networks (WSNs). Typical solutions for the broadcast scheduling iteratively search for nodes able to transmit a message simultaneously. Other nodes are prevented from transmissions to ensure that there is no collision in a network. Such collision-preventions result in extra delays for a broadcast and may increase overall latency if the delays occur along critical paths of the network. To facilitate the broadcast latency minimization, we propose a novel approach, critical-path aware scheduling (CAS), which schedules transmissions with a preference of nodes in critical paths of a duty-cycled WSN. This paper presents two schemes employing CAS which produce collision-free and collision-tolerant broadcast schedules, respectively. The collision-free CAS scheme guarantees an approximation ratio of <TEX>$ (\Updelta -\mathrm{1})T$</TEX> in terms of latency, where <TEX>$ \Updelta $</TEX> denotes the maximum node degree in a network. By allowing collision at noncritical nodes, the collision-tolerant CAS scheme reduces up to 10.2 percent broadcast latency compared with the collision-free ones while requiring additional transmissions for the noncritical nodes experiencing collisions. Simulation results show that broadcast latencies of the two proposed schemes are significantly shorter than those of the existing methods.</P>
무선센서네트워크에서 데이터 병합 트리를 위한 자기치유 방법
( Duc Tai Le ),( Thang Le Duc ),염상길 ( Sanggil Yeom ),( Vyacheslav V. Zalyubovskiy ),추현승 ( Hyunseung Choo ) 한국정보처리학회 2015 한국정보처리학회 학술대회논문집 Vol.22 No.1
Data aggregation is a fundamental problem in wireless sensor networks that has attracted great attention in recent years. On constructing a robust algorithm for minimizing data aggregation delay in wireless sensor networks, we consider limited transmission range sensors and approximate the minimum-delay data aggregation tree which can only be built in networks of unlimited transmission range sensors. The paper proposes an adaptive method that can be applied to maintain the network structure in case of a sensor node fails. The data aggregation tree built by the proposed scheme is therefore self-healing and robust. Intensive simulations are carried out and the results show that the scheme could adapt well to network topology changes compared with other approaches.
A provably tight delay-driven concurrently congestion mitigating global routing algorithm
Samanta, R.,Erzin, A.I.,Raha, S.,Shamardin, Y.V.,Takhonov, I.I.,Zalyubovskiy, V.V. Elsevier [etc.] 2015 Applied mathematics and computation Vol.255 No.-
Routing is a very important step in VLSI physical design. A set of nets are routed under delay and resource constraints in multi-net global routing. In this paper a delay-driven congestion-aware global routing algorithm is developed, which is a heuristic based method to solve a multi-objective NP-hard optimization problem. The proposed delay-driven Steiner tree construction method is of O(n<SUP>2</SUP>logn) complexity, where n is the number of terminal points and it provides n-approximation solution of the critical time minimization problem for a certain class of grid graphs. The existing timing-driven method (Hu and Sapatnekar, 2002) has a complexity O(n<SUP>4</SUP>) and is implemented on nets with small number of sinks. Next we propose a FPTAS Gradient algorithm for minimizing the total overflow. This is a concurrent approach considering all the nets simultaneously contrary to the existing approaches of sequential rip-up and reroute. The algorithms are implemented on ISPD98 derived benchmarks and the drastic reduction of overflow is observed.