Recently, various wireless networks are emerging and it leads to spectrum congestions. Cognitive radio, which allows users of the emerging wireless networks to opportunistically utilize the unused bands of the existing primary systems, can alleviate this problem. As one of the emerging wireless networks, 802.16 networks are suggested to explore TV "White Space" and then it is necessary to study cognitive operations of this network. In this paper, we propose enhanced frame structure and new channel accessing algorithms to enable cognitive operation of the WiMAX Mesh networks. With the novel algorithms for dynamically accessing the frequency channels for the control messages transmissions, no extra common control channels and operations of mesh clusters are needed, thus the spectrum resource can be saved and the network operation becomes simpler. The performance of the algorithms and the MAC protocol are analyzed theoretically and evaluated numerically. Results show that our algorithms can achieve, e. g., 3 times gain, in getting control messages received by neighbors, when compared to the scheme of mesh clusters. It also shows that with the parameter values presented, the normalized saturation throughput can be, e. g., as high as 75%.