Security is an important concern in any modern network. This also applies to Wireless Sensor Networks (WSNs), especially those used in applications that monitor sensitive information (e.g., health care applications). However, the highly constrained nature of sensors impose a difficult challenge: their reduced availability of memory, processing power and energy hinders the deployment of many modern cryptographic algorithms considered secure. For this reason, the choice of the most memory-, processing- and energy-efficient security solutions is of vital importance in WSNs. To date, several authors have developed extensive analyses comparing different encryption algorithms and key management schemes, while very little attention has been given to message authentication mechanisms. In this paper, we address this issues by identifying Authenticated Encryption with Associated Data (AEAD) schemes suitable for WSNs and by evaluating their features and performance on TelosB sensor nodes. As a result of this analysis, we identify the recommended choices depending on the characteristics of the target network.