Distributed Topological Convex Hull Estimation of Event Region in Wireless Sensor Networks without Location Information

Peng Guo, Jiannong Cao, Kui Zhang

    Research output: Contribution to journalArticleAcademicpeer-review

    5 Citations (Scopus)

    Abstract

    In critical event (e.g., fire or gas) monitoring applications of wireless sensor networks (WSNs), convex hull of the event region is an efficient tool in handling the usual tasks like event report, routes reconstruction and human motion planning. Existing works on estimating convex hull of event region usually require location information of sensor nodes, which needs high communication cost or hardware cost. In this paper, to avoid the requirement of location information, we define topological convex hull (T-convex hull) which presents the convex contour of an event region directly with a route passing by nodes, and hence becomes more efficient in handling the above tasks. To obtain the T-convex hull of event region in the absence of locations, we propose a low-weight (in terms of computation and storage resource requirement) distributed algorithm, with which sensor nodes just need to count the hop counts from some nodes. The communication cost of the algorithm is also low and independent of the network size. Comprehensive and largescale simulations are conducted, showing the effectiveness and much lower communication cost of the proposed algorithm, compared with related method.
    Original languageUndefined
    Pages (from-to)85-94
    Number of pages10
    JournalIEEE transactions on parallel and distributed systems
    Volume26
    Issue number1
    DOIs
    Publication statusPublished - 1 Jan 2015

    Keywords

    • Wireless Sensor Network
    • EWI-24214
    • CR-C.2
    • Convex hull
    • IR-94680
    • Event Detection
    • METIS-312435

    Cite this

    @article{354251dfd90b4a2287a783a4a36e0ed9,
    title = "Distributed Topological Convex Hull Estimation of Event Region in Wireless Sensor Networks without Location Information",
    abstract = "In critical event (e.g., fire or gas) monitoring applications of wireless sensor networks (WSNs), convex hull of the event region is an efficient tool in handling the usual tasks like event report, routes reconstruction and human motion planning. Existing works on estimating convex hull of event region usually require location information of sensor nodes, which needs high communication cost or hardware cost. In this paper, to avoid the requirement of location information, we define topological convex hull (T-convex hull) which presents the convex contour of an event region directly with a route passing by nodes, and hence becomes more efficient in handling the above tasks. To obtain the T-convex hull of event region in the absence of locations, we propose a low-weight (in terms of computation and storage resource requirement) distributed algorithm, with which sensor nodes just need to count the hop counts from some nodes. The communication cost of the algorithm is also low and independent of the network size. Comprehensive and largescale simulations are conducted, showing the effectiveness and much lower communication cost of the proposed algorithm, compared with related method.",
    keywords = "Wireless Sensor Network, EWI-24214, CR-C.2, Convex hull, IR-94680, Event Detection, METIS-312435",
    author = "Peng Guo and Jiannong Cao and Kui Zhang",
    note = "eemcs-eprint-24214",
    year = "2015",
    month = "1",
    day = "1",
    doi = "10.1109/TPDS.2014.2308184",
    language = "Undefined",
    volume = "26",
    pages = "85--94",
    journal = "IEEE transactions on parallel and distributed systems",
    issn = "1045-9219",
    publisher = "IEEE Computer Society",
    number = "1",

    }

    Distributed Topological Convex Hull Estimation of Event Region in Wireless Sensor Networks without Location Information. / Guo, Peng; Cao, Jiannong; Zhang, Kui.

    In: IEEE transactions on parallel and distributed systems, Vol. 26, No. 1, 01.01.2015, p. 85-94.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - Distributed Topological Convex Hull Estimation of Event Region in Wireless Sensor Networks without Location Information

    AU - Guo, Peng

    AU - Cao, Jiannong

    AU - Zhang, Kui

    N1 - eemcs-eprint-24214

    PY - 2015/1/1

    Y1 - 2015/1/1

    N2 - In critical event (e.g., fire or gas) monitoring applications of wireless sensor networks (WSNs), convex hull of the event region is an efficient tool in handling the usual tasks like event report, routes reconstruction and human motion planning. Existing works on estimating convex hull of event region usually require location information of sensor nodes, which needs high communication cost or hardware cost. In this paper, to avoid the requirement of location information, we define topological convex hull (T-convex hull) which presents the convex contour of an event region directly with a route passing by nodes, and hence becomes more efficient in handling the above tasks. To obtain the T-convex hull of event region in the absence of locations, we propose a low-weight (in terms of computation and storage resource requirement) distributed algorithm, with which sensor nodes just need to count the hop counts from some nodes. The communication cost of the algorithm is also low and independent of the network size. Comprehensive and largescale simulations are conducted, showing the effectiveness and much lower communication cost of the proposed algorithm, compared with related method.

    AB - In critical event (e.g., fire or gas) monitoring applications of wireless sensor networks (WSNs), convex hull of the event region is an efficient tool in handling the usual tasks like event report, routes reconstruction and human motion planning. Existing works on estimating convex hull of event region usually require location information of sensor nodes, which needs high communication cost or hardware cost. In this paper, to avoid the requirement of location information, we define topological convex hull (T-convex hull) which presents the convex contour of an event region directly with a route passing by nodes, and hence becomes more efficient in handling the above tasks. To obtain the T-convex hull of event region in the absence of locations, we propose a low-weight (in terms of computation and storage resource requirement) distributed algorithm, with which sensor nodes just need to count the hop counts from some nodes. The communication cost of the algorithm is also low and independent of the network size. Comprehensive and largescale simulations are conducted, showing the effectiveness and much lower communication cost of the proposed algorithm, compared with related method.

    KW - Wireless Sensor Network

    KW - EWI-24214

    KW - CR-C.2

    KW - Convex hull

    KW - IR-94680

    KW - Event Detection

    KW - METIS-312435

    U2 - 10.1109/TPDS.2014.2308184

    DO - 10.1109/TPDS.2014.2308184

    M3 - Article

    VL - 26

    SP - 85

    EP - 94

    JO - IEEE transactions on parallel and distributed systems

    JF - IEEE transactions on parallel and distributed systems

    SN - 1045-9219

    IS - 1

    ER -