Since LU decomposition-based key predistribution schemes can be compressed easily, they are very appropriate for source-limited sensor networks. But existing schemes have two flaws: (1) they all focus on key establishment without considering key or key material update, thus they can’t support extra nodes addition or deletion and their supported network size is limited; (2) they are vulnerable to LU attack. To conquer those drawbacks, a new LU decomposition-based key predistribution scheme for clustered heterogeneous sensor networks is proposed. Our scheme applies perturbation technology on matrices which are generated by LU decomposition, and establishes common bit-string between nodes by exchanging public vectors. These common bit-strings shared by nodes are randomly truncated and catenated one by one to form pairwise keys. When new nodes arrive or old nodes leave, this scheme updates key materials quickly by exploiting LU attack principle. Security and performance analysis show that our proposed scheme is feasible for sensor networks and has following two advantages: (1) It is robust to eavesdropping attack, Albrecht’s attack, LU attack and node capture attack; (2) It supports efficient key update for adding and deleting nodes while keeping original information about private matrix in secret.