Complexity constrained sensor networks: achievable rates for two relay networks and generalizations

ABSTRACT

Motivated by limited computational resources in sensor nodes, the impact of complexity constraints on the communication efficiency of sensor networks is studied. A single-parameter characterization of processing limitation of nodes in sensor networks is invoked. Specifically, the relaying nodes are assumed to "donate" only a small part of their total processor time to relay other nodes information. The amount of donated processor time is modelled by the node's ability to decode a channel code reliably at given rate R. Focusingon a four node network, with two relays, prior work for a complexity constrained single relay network is built upon. In the proposed coding scheme, the transmitter sends a broadcast code such that the relays decode only the "coarse" information, and assist the receiver in removing ambiguity only in that information. Via numerical examples,the impact of different power constraints in the system, ranging from per node power bound to network wide power constraint is explored. As the complexity bound R increases, the proposed scheme becomes identical to the recently proposed achievable rate by Gupta & Kumar. Both discrete memoryless and Gaussian channels are considered.

REFERENCES

• 1: Mitra, U., Sabharwal, A.: On achievable rates of complexity constrained relay channels. In: Proceedings of the Allerton Conference, Monticello, IL (2003).
• 2: Cover, T.M., Gamal, A.E.: Capacity theorems for the relay channel. IEEE Info. Theory 25 (1979)572--584.
• 3: Laneman, J.N., Tse, D.N.C., Wornell, G.W.: Cooperative diversity in wireless networks: Efficient protocols and outage behavior. IEEE Info. Theory (2003) to appear.
• 4: Schein, B., Gallager, R.: The Gaussian parallel relay network. In: Proceedings of ISIT, Sorrento, Italy (2000) 22.
• 5: Gastpar, M., Vetterli, M.: On the capacity of wireless networks: The relay case. In: Proceedings of INFOCOM. Volume 3., New York, NY (2002) 1577--1586.
• 6: Zahedi, S., Mohseni, M., El Gamal, A.: On the capacity of AWGN relay channels with linear relaying functions. In: ISIT 2004, Chicago, IL (2004) submitted.
• 7: Savage, J.E.: Complexity of decoders: I-Classes of decoding rules. IEEE Transactions on Information Theory 15 (1969) 689--695.
• 8: Savage, J.E.: Complexity of decoders. Part II: computational work and decoding time. IEEE Transactions on Information Theory 17 (1971)77--85.
• 9: Dana, A., Gowaikar, R., Hassibi, B., Effros, M., Medard, M.: Should we break a wireless network into subnetworks? In: Proceedings of the Allerton Conference on Communication, Control and Computing, Pacific Grove, CA (2003)
• 10: Gupta, P., Kumar, P.R.: Towards and information theory of large networks: An achievable rate region. IEEE Info. Theory 49 (2003) 1877--1894.
• 11: Xie, L.L., Kumar, P.R.: A network infromation theory for wireless communication: Scaling laws and optimal operation. IEEE Info.Theory (2002) submitted.
• 12: Zeng, C.M., Kuhlman, F., Buzo, A.: Achievability proof of some multiuser channel coding theorems using backward decoding. IEEE Transactions on Information Theory 35 (1989) 1160--1165.
• 13: Reznik, A., Kulkarni, S.R., Verdú, S.: Capacity and optimal resource allocation in the degraded Gaussian relay channel with multiple relays. In: Proceedings of the Allerton Conference, Monticello, IL (2002).
• 14: Sendonaris, A., Erkip, E., Aazhang, B.: User cooperation diversity, Part I: System description. IEEE Trans. Commun. 51 (2003) 1927--1938.
• 15: Kramer, G., Gastpar, M., Gupta, P.: Capacity theorems for wireless relay channels. In: Proceedings of the Allerton Conference, Monticello, IL (2003).
• 16: Slepian, D., Wolf, J.K.: Noiseless coding of correlated information sources. IEEE Info. Theory 19 (1973) 471--480.
• 17: Cover, T.M.: An achievable rate region for the broadcast channel. IEEE Info. Theory 21 (1975) 399--404.
• 18: Gamal, H.E.: On the scaling laws of dense wireless sensor networks.submitted to IEEE Info. Theory (2003)

INDEX TERMS

General Terms:
Algorithms, Performance, Theory

Keywords:
achievable rates, ad hoc wireless networks, channel capacity, complexity constraints limited code rate, information theory, relay networks, sensor networks