Academic
Publications
Computing and communicating functions over sensor networks

Computing and communicating functions over sensor networks,10.1109/JSAC.2005.843543,IEEE Journal on Selected Areas in Communications,Arvind Giridhar,P

Computing and communicating functions over sensor networks   (Citations: 136)
BibTex | RIS | RefWorks Download
In wireless sensor networks, one is not interested in downloading all the data from all the sensors. Rather, one is only interested in collecting from a sink node a relevant function of the sensor measurements. This paper studies the maximum rate at which functions of sensor measurements can be computedandcommunicatedtothesinknode. It focuses on symmetric functions, where only the data from a sensor is important, not its identity. The results incude the following. (i) The maximum rate of downloadingthefrequencyhistograminarandompla- narmulti-hopnetworkwithnnodesisO(1/logn).(ii)A subclassoffunctions,calledtype-sensitivefunctions,is maximallydi-culttocompute.Inacollocatednetwork theycanbecomputedatrateO(1/n),andinarandom planarmulti-hopnetworkatrateO(1/logn).Thisclass includes the mean, mode, median, etc. (iii) Another subclass of functions, called type-threshold functions, is exponentially easier to compute. In a collocated networktheycanbecomputedatrateO(1/logn),and inarandomplanarmulti-hopnetworkatrateO(1/log logn).Thisclassincludesthemax,min,range,etc. Theresultsalsoshowthearchitectureforprocessing informationacrosssensornetworks.
Journal: IEEE Journal on Selected Areas in Communications - JSAC , vol. 23, no. 4, pp. 755-764, 2005
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Fourth, we are interested in distributed function computation with a single instance of source data-vector (one-shot computation problem (Giridhar and Kumar 2005))...

    Samar Agnihotriet al. Worst-case asymmetric distributed function computation

    • ...Giridhar and Kumar [18] have stated: “In its most general form, computing a function in a network involves communicating possibly correlated messages, to a specific destination, at a desired fidelity with respect to a joint distortion criterion dependent on the given function of interest...
    • ...Other studies of computing in networks have been considered in [18], and [43], but these were restricted...
    • ...Divisible functions have been studied previously 5 by Giridhar and Kumar [18] and Subramanian, Gupta, and Shakkottai [43]...
    • ...Symmetric functions have been studied in the context of computing in networks by Giridhar et al. [18], Subramanian et al. [43], Ying et al. [50], and [26]...
    • ...5 The definitions in [18], [43] are similar to ours but slightly more restrictive...
    • ...RemarkI.12: Giridhar and Kumar [18] defined two classes of functions: type-threshold and type-sensitive functions...
    • ...However, [18] uses a model of interference for simultaneous transmissions and their results do not directly compare with ours...

    Rathinakumar Appuswamyet al. Network Coding for Computing: Cut-Set Bounds

    • ...Examples include sensor networks where sink nodes are tasked with calculating the average measurement value of all the sensors [1], [2], and multi-agent systems...

    Shreyas Sundaramet al. Distributed Function Calculation via Linear Iterative Strategies in th...

    • ...The pioneering work of Giridhar and Kumar [1] considers the function computation problem from the point of view of the capacity scaling for certain classes of functions...
    • ...Computation Model: We assume that the function f is divisible [1] (intuitively, this means that for any partition of the nodes, f can be computed by performing a local computation over each set in the partition, and then aggregating them together), and use fk to denote the function operating on k inputs, i.e., fk : X k ! R(f;k), where R(f;k) denotes the...

    Siddhartha Banerjeeet al. Towards a Queueing-Based Framework for In-Network Function Computation

    • ...Computation in large wireless sensor networks has been studied recently in [2]‐[4] but the model in these works excludes noise...
    • ...As in [2], [3], [10], we also study the class of symmetric functions...

    Nikhil Karamchandaniet al. Distributed function computation in networks: A joint delay-energy per...

Sort by: