AbstractWireless sensor network (WSN) applications havebeen studied extensively in recent years. Such applica-tions involve resource-limited embedded sensor nodesthat have small size and low power requirements. Basedon the need for extended network lifetimes in WSNs interms of energy use, the energy efficiency of computa-tion and communication operations in the embeddedsensor nodes becomes critical. Digital signal processing (DSP) applications typi-cally require intensive data processing operations. Theyare difficult to apply directly in resource-limited WSNsbecause their operational complexity can stronglyinfluence the network lifetime. In this paper, we present a design methodology formodeling and implementing DSP applications appliedto wireless sensor networks. This methodology exploresefficient modeling techniques for DSP applications,including acoustic sensing and data processing; derivesformulations of energy-driven partitioning for distribut-ing such applications across wireless sensor networks;and develops efficient heuristic algorithms for findingpartitioning results that maximize the network lifetime.A case study involving a speech recognition systemdemonstrates the capabilities of our proposed method-ology.1. Introduction and related workIn a hierarchical wireless sensor network [11], sen-sor nodes are clustered into groups, and their roles aredivided into master (e.g. the cluster head) and slavenodes for more efficient structuring of network traffic.The master node is typically fully-featured — that is,the platform is equipped with a relatively high perfor-mance processor and transceiver, larger size memorystorage, and sizable energy source. Conversely, slavenodes are lean in terms of features — the platforms areequipped with simple processors (e.g., small microcon-trollers), simple transceivers, sensors, limited memorystorage, and relatively small energy resources. Thus,slave nodes are typically equipped to carry out simplecomputations and transmit only the required processeddata to the associated master nodes for more computa-tionally-intensive tasks. In this paper, the targeted wire-less sensor network structures are such single-hop,master-slave topologies. Such static configurations ofnetwork structure have simple routing characteristics,and protocol demands, and allow designers to optimizeeffectively for network lifetime in terms of energy con-sumption, as well as for scalability through hierarchicalorganization.Digital signal processing (DSP) applications areoften relevant to processing sensor data, and usuallyrequire intensive computation. The behavior of manyDSP applications can be characterized with regularcomputation patterns and modeled efficiently throughdataflow graphs. By analyzing a well-designed data-flow model of an application, operational efficiency canbe estimated and optimized accordingly (e.g., see [2,12]).In a typical WSN configuration, resource-limitedslave nodes are unable to handle computationally-inten-sive tasks due to lack of hardware and software support.In such a case, microcontrollers in slave nodes can per-form relatively light-weight computations. Withadvances in integrated circuit technology, slave nodescan be equipped with increasing amounts of computa-tional resources, such as digital signal processor sub-systems. Then the microcontrollers can performprotocol and control tasks, while the DSP processorsperform more intensive computational tasks.The energy consumption of the nodes in a wirelesssensor network must be carefully optimized to increasenetwork lifetime. Computation and communicationtasks that sensor nodes execute affect major energyconsumed. Especially, communication tasks on thetransceiver dominate overall power consumption on asensor node [5]. Thus, the amount of data to be trans-An Energy-driven Design Methodology for Distributing DSP Applications across Wireless Sensor NetworksChung-Ching Shen, William Plishker, Shuvra S. Bhattacharyya, and Neil GoldsmanDept. of Electrical and Computer Engineering, and Institute for Advanced Computer StudiesUniversity of Maryland at College Park, USA{ccshen, plishker, ssb, neil}@umd.eduIn Proceedings of the IEEE Real-Time Systems Symposium, Tucson, Arizona, December 2007.mitted across the wireless channel should be minimizeddue to the reduction of the turn-on time of the transceiv-ers. For distributing DSP computations to the WSN,this reduction is significant since DSP applications usu-ally process a large amount of data for their tasks. Inthis paper, we present an algorithm that addresses thisobjective for DSP applications that are modeled as data-flow graphs. Specifically, our algorithm finds an effi-cient trade-off between the workloads of computationand communication tasks in both master and slavenodes.Many useful approaches have been studied previ-ously to reduce the energy consumption of sensornodes. In [15], Singh discusses system-level trade-offsrelated to energy costs of WSN technologies. Shih [14]distributes the FFT function over a master node andassociated slave nodes to reduce energy consumption.Kumar [11] explores energy and latency trade-offs byconsidering different computational capabilities formaster and slave nodes. Wang [16] develops an approach that partitionsapplications between master and slave nodes, and alsoapplies dynamic voltage scaling to further reduce powerconsumption. In contrast to Wang’s approach, the parti-tioning method presented in this paper applies coarse-grain analysis of dataflow graphs, as well as integrationwithin a dataflow-based DSP design tool. This tool,called the DIF (dataflow interchange format) package,is introduced in [8]. Ko [10] introduces the general approach of reduc-ing data traffic across WSN nodes by determining andexploiting the lowest data token delivery points withinan application dataflow graph. This paper builds on theapproach and problem formulations introduced by Ko,and develops an efficient heuristic method that is moreefficient and scalable compared to the exhaustivesearch approach employed by Ko. We also go beyondthe developments of [10] in this paper by addressingboth homogeneous and heterogeneous network organi-zations; taking into account energy consumption inmore detail as well as real time latency constraints,based on measured and simulated task profiles; and asmentioned above, by integrating our partitioning meth-ods into the DIF package.2. Design flow overviewFigure 1 presents an overall design flow for