ترغب بنشر مسار تعليمي؟ اضغط هنا

Distributed Planarization and Local Routing Strategies in Sensor Networks

261   0   0.0 ( 0 )
 نشر من قبل Florian Huc
 تاريخ النشر 2011
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

We present an algorithm which computes a planar 2-spanner from an Unit Disk Graph when the node density is sufficient. The communication complexity in terms of number of nodes identifier sent by the algorithm is $6n$, while the computational complexity is $O(nDelta)$, with $Delta$ the maximum degree of the communication graph. Furthermore, we present a simple and efficient routing algorithm dedicated to the computed graph. Last but not least, using traditional Euclidean coordinates, our algorithm needs the broadcast of as few as $3n$ nodes identifiers. Under the hypothesis of sufficient node density, no broadcast at all is needed, reducing the previous best known complexity of an algorithm to compute a planar spanner of an Unit Disk Graph which was of $5n$ broadcasts.



قيم البحث

اقرأ أيضاً

99 - Florian Huc , Aubin Jarry 2009
In order to make full use of geographic routing techniques developed for large scale networks, nodes must be localized. However, localization and virtual localization techniques in sensor networks are dependent either on expensive and sometimes unava ilable hardware (e.g. GPS) or on sophisticated localization calculus (e.g. triangulation) which are both error-prone and with a costly overhead. Instead of localizing nodes in a traditional 2-dimensional space, we intend to use directly the raw distance to a set of anchors to route messages in the multi-dimensional space. This should enable us to use any geographic routing protocol in a robust and efficient manner in a very large range of scenarios.
158 - Moufida Maimour 2008
In wireless sensor networks, bandwidth is one of precious resources to multimedia applications. To get more bandwidth, multipath routing is one appropriate solution provided that inter-path interferences are minimized. In this paper, we address the p roblem of interfering paths in the context of wireless multimedia sensor networks and consider both intra-session as well as inter-session interferences. Our main objective is to provide necessary bandwidth to multimedia applications through non-interfering paths while increasing the network lifetime. To do so, we adopt an incremental approach where for a given session, only one path is built at once. Additional paths are built when required, typically in case of congestion or bandwidth shortage. Interference awareness and energy saving are achieved by switching a subset of sensor nodes in a {em passive state} in which they do not take part in the routing process. Despite the routing overhead introduced by the incremental approach we adopt, our simulations show that this can be compensated by the overall achieved throughput and the amount of consumed energy per correctly received packet especially for relatively long sessions such as multimedia ones. This is mainly due to the fact that a small number of non-interfering paths allows for better performances than a large number of interfering ones.
One of the limitations of wireless sensor nodes is their inherent limited energy resource. Besides maximizing the lifetime of the sensor node, it is preferable to distribute the energy dissipated throughout the wireless sensor network in order to min imize maintenance and maximize overall system performance. Any communication protocol that involves synchronization of peer nodes incurs some overhead for setting up the communication. We introduce a new algorithm, e3D (energy-efficient Distributed Dynamic Diffusion routing algorithm), and compare it to two other algorithms, namely directed, and random clustering communication. We take into account the setup costs and analyze the energy-efficiency and the useful lifetime of the system. In order to better understand the characteristics of each algorithm and how well e3D really performs, we also compare e3D with its optimum counterpart and an optimum clustering algorithm. The benefit of introducing these ideal algorithms is to show the upper bound on performance at the cost of an astronomical prohibitive synchronization costs. We compare the algorithms in terms of system lifetime, power dissipation distribution, cost of synchronization, and simplicity of the algorithm. Our simulation results show that e3D performs comparable to its optimal counterpart while having significantly less overhead.
Multipath routing in WSN has been a long wish in security scenario where nodes on next-hop may be targeted to compromise. Many proposals of Multipath routing has been proposed in ADHOC Networks but under constrained from keying environment most seems ignorant. In WSN where crucial data is reported by nodes in deployment area to their securely located Sink, route security has to be guaranteed. Under dynamic load and selective attacks, availability of multiple secure paths is a boon and increases the attacker efforts by many folds. We propose to build a subset of neighbors as our front towards destination node. We also identified forwarders for query by base station. The front is optimally calculated to maintain the security credential and avail multiple paths. According to our knowledge ours is first secure multipath routing protocol for WSN. We established effectiveness of our proposal with mathematical analysis
225 - Zheng Sun 2008
A distributed spiral algorithm for distributed optimization in WSN is proposed. By forming a spiral-shape message passing scheme among clusters, without loss of estimation accuracy and convergence speed, the algorithm is proved to converge with a low er total transport cost than the distributed in-cluster algorithm.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا