Permissioned Blockchain (PBC) has become a prevalent data structure to ensure that the records are immutable and secure. However, PBC still has significant challenges before it can be realized in different applications. One of such challenges is the overhead of the communication which is required to execute the Byzantine Agreement (BA) protocol that is needed for consensus building. As such, it may not be feasible to implement PBC for resource constrained environments such as Internet-of-Things (IoT). In this paper, we assess the communication overhead of running BA in an IoT environment that consists of wireless nodes (e.g., Raspberry PIs) with meshing capabilities. As the the packet loss ratio is significant and makes BA unfeasible to scale, we propose a network coding based approach that will reduce the packet overhead and minimize the consensus completion time of the BA. Specifically, various network coding approaches are designed as a replacement to TCP protocol which relies on unicasting and acknowledgements. The evaluation on a network of Raspberry PIs demonstrates that our approach can significantly improve scalability making BA feasible for medium size IoT networks.