An apparatus, method, and computer readable medium thereof for simultaneously establishing links with a plurality of nodes in a wireless network are provided. A processing module determines whether a mesh network configuration message of the apparatus has space to packet an information element and determines whether to transmit a Neighbor Link Establishment information element to one of the nodes. If the mesh network configuration message has space to packet an information element and the Neighbor Link Establishment information element needs to be transmitted to one of the nodes, the Neighbor Link Establishment information element will be packeted into the mesh network configuration message. Finally, a transmission module transmits the mesh network configuration message to the nodes in order to solve the problem of increasing time during link establishment and avoid deadlock among the nodes when the apparatus of the prior art establishes links with the nodes simultaneously.