The Experts below are selected from a list of 12894 Experts worldwide ranked by ideXlab platform

Ivan Stojmenovic - One of the best experts on this subject based on the ideXlab platform.

  • routing with Guaranteed Delivery in ad hoc wireless networks
    Wireless Networks, 2001
    Co-Authors: Prosenjit Bose, Ivan Stojmenovic, Pat Morin, Jorge Urrutia
    Abstract:

    We consider routing problems in ad hoc wireless networks modeled as unit graphs in which nodes are points in the plane and two nodes can communicate if the distance between them is less than some fixed unit. We describe the first distributed algorithms for routing that do not require duplication of packets or memory at the nodes and yet guarantee that a packet is delivered to its destination. These algorithms can be extended to yield algorithms for broadcasting and geocasting that do not require packet duplication. A by product of our results is a simple distributed protocol for extracting a planar subgraph of a unit graph. We also present simulation results on the performance of our algorithms.

  • loop free hybrid single path flooding routing algorithms with Guaranteed Delivery for wireless networks
    IEEE Transactions on Parallel and Distributed Systems, 2001
    Co-Authors: Ivan Stojmenovic
    Abstract:

    In a localized routing algorithm, each node makes forwarding decisions solely based on the position of itself, its neighbors, and its destination. In distance, progress, and direction-based approaches'(reported in the literature), when node A wants to send or forward message m to destination node D, it forwards m to its neighbor C which is closest to D (has best progress toward D, whose direction is closest to the direction of D, respectively) among all neighbors of A. The same procedure is repeated until D, if possible, is eventually reached. The algorithms are referred to as GEDIR, MFR, and DIR when a common failure criterion is introduced: The algorithm stops if the best choice for the current node is the node from which the message came. We propose 2-hop GEDIR, DIR, and MFR methods in which node A selects the best candidate node C among its 1-hop and 2-hop neighbors according to the corresponding criterion and forwards m to its best 1-hop neighbor among joint neighbors of A and C. We then propose flooding GEDIR and MFR and hybrid single-path/flooding GEDIR and MFR methods which are the first localized algorithms (other than full flooding) to guarantee the message Delivery (in a collision-free environment). We show that the directional routing methods are not loop-free, while the GEDIR and MFR-based methods are inherently loop free. The simulation experiments, with static random graphs, show that GEDIR and MFR have similar success rates, which is low for low degree graphs and high for high degree ones. When successful, their hop counts are near the performance of the shortest path algorithm. Hybrid single-path/flooding GEDIR and MFR methods have low communication overheads. The results are also confirmed by experiments with moving nodes and MAC layer.

  • internal node and shortcut based routing with Guaranteed Delivery in wireless networks
    International Conference on Distributed Computing Systems, 2001
    Co-Authors: Souptik Datta, Ivan Stojmenovic
    Abstract:

    Several distributed routing algorithms for wireless networks were described recently, based on location information of nodes available via Global Positioning System (GPS). In a greedy routing algorithm, the sender or node S currently holding the message m forwards m to one of its neighbors that is the closest to the destination. The algorithm fails if S does not have any neighbor that is closer to destination than S. The FACE algorithm guarantees the Delivery of m if the network, modeled by unit graph, is connected. The GFG algorithm combines greedy and FACE algorithms. We further improve the performance of the GFG algorithm, by reducing its average hop count. First we improve the FACE algorithm by adding a sooner-back procedure for earlier escape from FACE mode. Then we perform a shortcut procedure at each forwarding node S. Node S uses the local information available to calculate as many hops as possible and forwards the packet to the last known hop directly instead of forwarding it to the next hop. The second improvement is based on the concept of dominating sets. The network of internal nodes defines a connected dominating set, and each node must be either internal or directly connected to an internal node. We apply several existing definitions of internal nodes, namely the concepts of intermediate, inter-gateway and gateway nodes. We propose to run GFG routing, enhanced by shortcut procedure, on the dominating set, except possibly the first and last hops. We obtained localized routing algorithm that guarantees Delivery and has very low excess in terms of hop count compared to the shortest path algorithm. Experimental data show that the length of additional path can be reduced to about half that of existing GFG algorithm.

Elizabeth M Jewkes - One of the best experts on this subject based on the ideXlab platform.

  • customer lead time management when both demand and price are lead time sensitive
    European Journal of Operational Research, 2004
    Co-Authors: Saibal Ray, Elizabeth M Jewkes
    Abstract:

    Abstract In this paper, we model an operating system consisting of a firm and its customers, where the mean demand rate is a function of the Guaranteed Delivery time offered to the customers and of market price, where price itself is determined by the length of the Delivery time. Economies of scale are present. The firm’s objective is to maximize profits by selecting an optimal Guaranteed Delivery time taking into account that (i) reducing Delivery time will require investment, and (ii) the firm must be able to satisfy a pre-specified service level. We show that it is imperative for managers to know whether customers are price or lead time sensitive based on the simultaneous dependence of price and demand on Delivery time before selecting a time-based competitive strategy. We investigate the optimal policy and provide managerial insights based on our analysis. Examples where our insights are consistent with actual practical situations are also provided. We show that our model is different from those in the literature that assume price and Delivery time to be independent decision variables and present conditions under which ignoring the relation between price and Delivery time can lead managers to substantially sub-optimal decisions––with or without the presence of economies of scale.

Miao Jin - One of the best experts on this subject based on the ideXlab platform.

  • trace routing in 3d wireless sensor networks a deterministic approach with constant overhead
    Mobile Ad Hoc Networking and Computing, 2014
    Co-Authors: Su Xia, Miao Jin
    Abstract:

    We propose a distributed and deterministic routing algorithm with constant storage, communication and computation overhead, dubbed trace-routing, for strong-connected 3D wireless sensor networks. Its basic idea is to construct a virtual cutting plane that intersects boundary surface to yield a trace, along which a routing path with Guaranteed Delivery can be established. We prove the correctness of trace-routing under both continuous and discrete settings. We implement the trace-routing algorithm on Crossbow sensors and carry out extensive simulations to evaluate its routing efficiency.

  • deterministic greedy routing with Guaranteed Delivery in 3d wireless sensor networks
    Axioms, 2014
    Co-Authors: Su Xia, Xiaotian Yin, Miao Jin
    Abstract:

    With both computational complexity and storage space bounded by a small constant, greedy routing is recognized as an appealing approach to support scalable routing in wireless sensor networks. However, significant challenges have been encountered in extending greedy routing from 2D to 3D space. In this research, we develop decentralized solutions to achieve greedy routing in 3D sensor networks. Our proposed approach is based on a unit tetrahedron cell (UTC) mesh structure. We propose a distributed algorithm to realize volumetric harmonic mapping (VHM) of the UTC mesh under spherical boundary condition. It is a one-to-one map that yields virtual coordinates for each node in the network without or with one internal hole. Since a boundary has been mapped to a sphere, node-based greedy routing is always successful thereon. At the same time, we exploit the UTC mesh to develop a face-based greedy routing algorithm and prove its success at internal nodes. To deliver a data packet to its destination, face-based and node-based greedy routing algorithms are employed alternately at internal and boundary UTCs, respectively. For networks with multiple internal holes, a segmentation and tunnel-based routing strategy is proposed on top of VHM to support global end-to-end routing. As far as we know, this is the first work that realizes truly deterministic routing with constant-bounded storage and computation in general 3D wireless sensor networks.

  • deterministic greedy routing with Guaranteed Delivery in 3d wireless sensor networks
    Mobile Ad Hoc Networking and Computing, 2011
    Co-Authors: Su Xia, Xiaotian Yin, Miao Jin
    Abstract:

    With both computational complexity and storage space bounded by a small constant, greedy routing is recognized as an appealing approach to support scalable routing in wireless sensor networks. However, significant challenges have been encountered in extending greedy routing from 2D to 3D space. In this research we develop decentralized solutions to achieve greedy routing in 3D sensor networks. Our proposed approach is based on a unit tetrahedron cell (UTC) mesh structure. We propose a distributed algorithm to realize volumetric harmonic mapping of the UTC mesh under spherical boundary condition. It is a one-to-one map that yields virtual coordinates for each node in the network. Since a boundary has been mapped to a sphere, node-based greedy routing is always successful thereon. At the same time, we exploit the UTC mesh to develop a face-based greedy routing algorithm, and prove its success at internal nodes. To deliver a data packet to its destination, face-based and node-based greedy routing algorithms are employed alternately at internal and boundary UTCs, respectively. As far as we know, this is the first work that realizes truly deterministic greedy routing with constant-bounded storage and computation in 3D wireless sensor networks.

Saibal Ray - One of the best experts on this subject based on the ideXlab platform.

  • customer lead time management when both demand and price are lead time sensitive
    European Journal of Operational Research, 2004
    Co-Authors: Saibal Ray, Elizabeth M Jewkes
    Abstract:

    Abstract In this paper, we model an operating system consisting of a firm and its customers, where the mean demand rate is a function of the Guaranteed Delivery time offered to the customers and of market price, where price itself is determined by the length of the Delivery time. Economies of scale are present. The firm’s objective is to maximize profits by selecting an optimal Guaranteed Delivery time taking into account that (i) reducing Delivery time will require investment, and (ii) the firm must be able to satisfy a pre-specified service level. We show that it is imperative for managers to know whether customers are price or lead time sensitive based on the simultaneous dependence of price and demand on Delivery time before selecting a time-based competitive strategy. We investigate the optimal policy and provide managerial insights based on our analysis. Examples where our insights are consistent with actual practical situations are also provided. We show that our model is different from those in the literature that assume price and Delivery time to be independent decision variables and present conditions under which ignoring the relation between price and Delivery time can lead managers to substantially sub-optimal decisions––with or without the presence of economies of scale.

Su Xia - One of the best experts on this subject based on the ideXlab platform.

  • trace routing in 3d wireless sensor networks a deterministic approach with constant overhead
    Mobile Ad Hoc Networking and Computing, 2014
    Co-Authors: Su Xia, Miao Jin
    Abstract:

    We propose a distributed and deterministic routing algorithm with constant storage, communication and computation overhead, dubbed trace-routing, for strong-connected 3D wireless sensor networks. Its basic idea is to construct a virtual cutting plane that intersects boundary surface to yield a trace, along which a routing path with Guaranteed Delivery can be established. We prove the correctness of trace-routing under both continuous and discrete settings. We implement the trace-routing algorithm on Crossbow sensors and carry out extensive simulations to evaluate its routing efficiency.

  • deterministic greedy routing with Guaranteed Delivery in 3d wireless sensor networks
    Axioms, 2014
    Co-Authors: Su Xia, Xiaotian Yin, Miao Jin
    Abstract:

    With both computational complexity and storage space bounded by a small constant, greedy routing is recognized as an appealing approach to support scalable routing in wireless sensor networks. However, significant challenges have been encountered in extending greedy routing from 2D to 3D space. In this research, we develop decentralized solutions to achieve greedy routing in 3D sensor networks. Our proposed approach is based on a unit tetrahedron cell (UTC) mesh structure. We propose a distributed algorithm to realize volumetric harmonic mapping (VHM) of the UTC mesh under spherical boundary condition. It is a one-to-one map that yields virtual coordinates for each node in the network without or with one internal hole. Since a boundary has been mapped to a sphere, node-based greedy routing is always successful thereon. At the same time, we exploit the UTC mesh to develop a face-based greedy routing algorithm and prove its success at internal nodes. To deliver a data packet to its destination, face-based and node-based greedy routing algorithms are employed alternately at internal and boundary UTCs, respectively. For networks with multiple internal holes, a segmentation and tunnel-based routing strategy is proposed on top of VHM to support global end-to-end routing. As far as we know, this is the first work that realizes truly deterministic routing with constant-bounded storage and computation in general 3D wireless sensor networks.

  • deterministic greedy routing with Guaranteed Delivery in 3d wireless sensor networks
    Mobile Ad Hoc Networking and Computing, 2011
    Co-Authors: Su Xia, Xiaotian Yin, Miao Jin
    Abstract:

    With both computational complexity and storage space bounded by a small constant, greedy routing is recognized as an appealing approach to support scalable routing in wireless sensor networks. However, significant challenges have been encountered in extending greedy routing from 2D to 3D space. In this research we develop decentralized solutions to achieve greedy routing in 3D sensor networks. Our proposed approach is based on a unit tetrahedron cell (UTC) mesh structure. We propose a distributed algorithm to realize volumetric harmonic mapping of the UTC mesh under spherical boundary condition. It is a one-to-one map that yields virtual coordinates for each node in the network. Since a boundary has been mapped to a sphere, node-based greedy routing is always successful thereon. At the same time, we exploit the UTC mesh to develop a face-based greedy routing algorithm, and prove its success at internal nodes. To deliver a data packet to its destination, face-based and node-based greedy routing algorithms are employed alternately at internal and boundary UTCs, respectively. As far as we know, this is the first work that realizes truly deterministic greedy routing with constant-bounded storage and computation in 3D wireless sensor networks.